3 ms·
applying a concept from such a high abstraction level that it's fully unbound in time and space to a practical real world focused thing is fun but a bit silly a
by dathinab 2y ago
applying a concept from such a high abstraction level that it's fully unbound in time and space to a practical real world focused thing is fun but a bit silly and it often leads to funny questions like can you define MAX_SIZE, size_t etc. as infinite?
in context of IRL things the question of turning completeness is normally not "if it can be used to simulate any Turing machine" (wikipedia) but " if it can be used to simulate any Turing machine bound to some realistic size limit"
- ratorx 2y agoThat’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).