3 ms·
This is computer science 201. You enumerate all possible Turing Machines (possible because they are countably infinite), then diagonalize their execution. For a
by jerf 11y ago
This is computer science 201. You enumerate all possible Turing Machines (possible because they are countably infinite), then diagonalize their execution. For any execution state that any Turing Machine reaches in any finite period of time, this simulation will also reach it in a finite period of time. A very large "amount" of time, sure, but "time" in a Turing Machine is an abstraction anyhow.
Also in Computer Science 201, you should encounter the Church-Turing thesis. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis