3 ms·
If the answer is "there is such a program that reproduces the universe," then I have already found one such program that does it. Here it is: interleave the sim
by j2kun 11y ago
If the answer is "there is such a program that reproduces the universe," then I have already found one such program that does it. Here it is: interleave the simulation of individual steps of every Turing machine in lexicographic order. That is, if the Turing machines are enumerated T_1, T_2, T_3, ... you do the following:
i = 1
while True:
j = 1
while j <= i:
simulate step j of Turing machine T_i
j += 1
i += 1
If there is some program, it will be in the list.
This is the pitfall you get into when you only care about finding extremely short programs and don't think about efficiency. Similar pitfalls are in the philosophy of artificial intelligence. You get no useful information or theory or model if you ignore computational complexity.
- Pharaoh2 11y agoDoes this set of all turing machines contain the given turing machine? If yes, then it would seem that you can never simulate even a single iteration of the inner loop. If no, then you are not actually simulating all the programs are you? This goes a little beyond NP hard complexity, I believe.
- j2kun 11y agoThis set of Turing machines is the set of all Turing machines. But you misunderstand, I am only simulating a single step (constant time) of a finite number of Turing machines in any given iteration of the inner loop. It goes arbitrarily far beyond NP hard complexity, which is my point. Wolfram ignores complexity entirely, and that means this algorithm is fair game.
- Pharaoh2 11y ago1. 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.
- infogulch 11y agoI think you mean "simulate step i of Turing machine T_j"
- j2kun 11y agoQuite right. It's sad I can't edit even slightly old comments.