3 ms·

Does 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 inn

Does 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 ago
This 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 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 ago
    1: 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 ago
      Chaotic functions of continuous real variables are not computable. Computable physics assumes a discrete lattice, which the universe is not proven to be.
      - drdeca 11y ago
        Hm, 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 ago
        There's also no proof (or even evidence) that the universe is not discrete.
      - Natanael_L 11y ago
        Can'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 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
  - eli_gottlieb 11y ago
    https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect...
  - FeepingCreature 11y ago
    https://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 https://en.wikipedia.org/wiki/Dovetailing_%28computer_scienc...

j2kun 11y ago

This 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 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 ago
  1: 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 ago
    Chaotic functions of continuous real variables are not computable. Computable physics assumes a discrete lattice, which the universe is not proven to be.
    - drdeca 11y ago
      Hm, 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 ago
      There's also no proof (or even evidence) that the universe is not discrete.
    - Natanael_L 11y ago
      Can'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 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
- eli_gottlieb 11y ago
  https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect...
- FeepingCreature 11y ago
  https://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 https://en.wikipedia.org/wiki/Dovetailing_%28computer_scienc...