Remix.run Logo
skybrian 5 hours 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.”

chongli 40 minutes ago | parent | next [-]

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).

dnautics 4 hours ago | parent | prev [-]

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.