3 ms·
And Turing machines have unbounded memory. That's usually ignored when talking about Turing completeness, but it's nevertheless true that physical computers can
by Scarblac 3y ago
And Turing machines have unbounded memory. That's usually ignored when talking about Turing completeness, but it's nevertheless true that physical computers cannot simulate all Turing machines.
- Dylan16807 3y agoWhat makes you say a physical computer doesn't have unbounded memory? Is it making assumptions about the real world that we have to make?
- kweingar 3y ago> it's nevertheless true that physical computers cannot simulate all Turing machines Right, I wasn’t arguing that physical computers can be Turing machines, but instead that sets of operations can be Turing complete. There are sets of operations with which one can compose a program that perfectly simulates a Turing machine. The problem is that physical computers cannot always run these programs accurately, due to memory constraints. But the set of operations is itself Turing complete.