4 ms·
> The value multistack is flat and is modeled by a map from stack name to value stack. Makes sense for a real implementation, of course. It's nice to have a th
by Twisol 5y ago
> The value multistack is flat and is modeled by a map from stack name to value stack.
Makes sense for a real implementation, of course. It's nice to have a theoretical reduction, though, so we know there's no semantic difference between using multiple stacks and using a single stack.
- smaddox 5y agoI'm not sure if such a reduction is possible, in general, without explicitly modeling a map from stack names to stacks (which you could certainly do in the UCC, but it would be quite verbose). For specific programs you can always do a such reduction, of course.
- Twisol 5y agoRight, for sure. I think Turing reductions tend to be in terms of a concrete Turing machine, anyway; I don't think there's any claim being made here of a universal multistack machine, which is what you might be touching on.