Comment by skybrian
1 day ago
A Turing machine has an unlimited tape. You can’t emulate it with a fixed amount of memory.
It’s mostly a theoretical issue, though, because all real computer systems have limits. It’s just that in languages that assume unlimited memory, the limits aren’t written down. It’s not “part of the language.”
If we get REALLY nitpicky, zig currently (but not in the future) allows unbounded function recursion with "theoretically" assumes unlimited stack size, so it's potentially "still technically theoretically turing complete". For now.
What about IO? Just because I have a statically allocated program with a fixed amount of memory doesn’t mean I can’t do IO. My fixed memory can just be a cache / scratchpad and the unlimited tape can work via IO (disk, network, etc).
Yes, good point.