3 ms·

I'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,

I'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 ago
Right, 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.