3 ms·
1. Why are the number of turing machines finite. 2. But to simulate a single step of the turing machine, you will have to simulate this turing machine too, so
by Pharaoh2 11y ago
1. Why are the number of turing machines finite.
2. But to simulate a single step of the turing machine, you will have to simulate this turing machine too, so what you will end up doing is recursively simulating the first step of this machine to infinity.
3. Why do you assume all the programs in the world are turing computable.
- drdeca 11y ago1: they aren't. They don't need to be, and they cannot be. Simulate the first step of the first machine, then the first step of the second machine, then the second step of the first machine, then the first step of the third machine, then the second of the second, then the third of the first, then the first of the fourth, and so on. Every step of every program/machine is eventually reached. For the same reason that the pairs of integers can be put into bijection with the integers. 2) that is not a problem. The first step of that is not to run a step of a program it simulates. The "simulating a single step of a given machine" is not a single step. It is many steps. As such, there is no such recursive problem like you describe. Simulating a single step of a machine always finishes, regardless of what that step "represents". Even if the step being simulated is part of some simulator machine, simulating it is still done in the same way, and doesn't take longer. 3) Any programs for any computer we have can be simulated by a Turing machine. They are quite general. You might claim that some physical process is not computable, but that has not been demonstrated for any physical process (well, except for maybe consciousness, but that is contentious), and most ideas of how physics works are computable, so there would be a significant burden of proof. So, it seems like any program we can run can be simulated by a Turing machine.
- knughit 11y agoChaotic functions of continuous real variables are not computable. Computable physics assumes a discrete lattice, which the universe is not proven to be.
- drdeca 11y agoHm, I was not aware of that. What about for, uh... It occurs to me that I'm not exactly sure what a chaotic function of continuous real variables is. Is it like, one where iterating it gives chaotic results, or? What if, instead of variables over the reals, using variables over the computable reals?
- j2kun 11y agoThere's also no proof (or even evidence) that the universe is not discrete.
- Natanael_L 11y agoCan't find any proof of that claim. So far it seems more likely that all physical systems are computable. Although you may need infinite time to achieve perfect accuracy when computing them in a simulation, but matematically that's still computable. Computability makes no assumption on the geometry, only on the rules the system follows.
- jerf 11y agoThis 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
- eli_gottlieb 11y agohttps://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect...
- FeepingCreature 11y agohttps://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 https://en.wikipedia.org/wiki/Dovetailing_%28computer_scienc...