3 ms·
That’s not the way to get around it. “Turing Machine with bounded tape” is a provably different class of automata to a Turing Machine (https://en.m.wikipedia.or
by ratorx 2y ago
That’s not the way to get around it. “Turing Machine with bounded tape” is a provably different class of automata to a Turing Machine (https://en.m.wikipedia.org/wiki/Linear_bounded_automaton https://en.m.wikipedia.org/wiki/Linear_bounded_automaton)
For a “useful” proof, I think you have to do a bit of reading between the lines of separating the “essence” from the specification even if the language you end up with is not exactly as specified but can e.g. be implemented in the language given the right primitives. I don’t think a low-level language specification can be Turing complete.
Maybe a LISP would be, or pretty much anything that don’t specify pointer sizes (as in this post).