5 ms·

I think it is articles like this one which are misleading. The Turing Machine was never “built” because it is just a class of machines, i.e. particular machines

I think it is articles like this one which are misleading. The Turing Machine was never “built” because it is just a class of machines, i.e. particular machines are of the Turing Machine class, Turing-complete. Because the class of machine has an infinitely long “tape”, then finite machines can be created “under” it, or in that domain. Turing literally devised a method to create machines with a specific name, a number, and compute that number. Each and every one of your computers could be formalized to have a specific number, even if extremely large. Therefore, each of your computers are Turing Machines, unless of course you can show that you can run a program that the class of Turing Machines cannot. Edit: I think the surest example of this is in the term “binary”. When you compile a C program, you get an executable binary. Literally, you have a file of ones and zeroes. Well, that’s just an extremely large number in binary, exactly the same as the binary string “100001” being “33” in decimal.

daniel-cussen 3y ago
[dead]
russdill 3y ago
A Turing machine with a finite tape can be simulated with an FSM, and so is in a lower class.
- leroy-is-here 3y ago
  I thought about your comment a lot and here’s a way, way better illustration: You are completely correct that we can formalize any Turing Machine as a FSM but! this _must_ include input. Again, this is just pure simulation as you state. Again, we can write a _single_ Turing Machine program with a _single_ input baked in as an FSM and that input _must_ be finite. But that FSM is not capable of handling _any_ input like the the Turing Machine it is simulating. That’s kinda the big difference between Turing machines and machines of a lower class. Any FSM has limited input thus limited states, but a Turing Machine can run infinitely with finite input. So, one can simulate the Turing Machine _with_ input using a FSM up to state N. But the actual Turing Machine can execute up to N+1 without having to hard-code any inputs and is capable of handling other inputs. Again, your computer is a Turing Machine capable of accepting Turing Machines as input. We can hard-code any individual programs and make them into a physical computer chip — just as we did with our computers which can accept any input it can handle, limited only by its physical limitations. But these physical limitations are not an indicator of it being of a lower class because we can keep pushing those limitations back and still compute more of states of these programs. Anyway, I’m glad you mentioned all of this because I went and pulled out my books.
- leroy-is-here 3y ago
  Because the "tape" is infinite, then the possibilities to name individual machines are infinite. I can create the number of a machine which is just a simple non-deterministic finite automata using a Turing Machine description. My point is that we can always use more powerful machines to describe less powerful ones, but that isn't an indicator that they are then less powerful.
  - russdill 3y ago
    My point being is that from a computational complexity standpoint, your computer is not a Turing machine, just a very very very large FSM. So it's still very useful to think of it as a Turing machine.
    - leroy-is-here 3y ago
      Again, if your computer is not a Turing Machine, then it must be able to run programs that the Turing Machine class is not able.
      - russdill 3y ago
        I'm saying that a silicon computer a lower completely class than a theoretical Turing machine, not higher
        leroy-is-here 3y ago
        I think I agree with you, but maybe not for reasons you agree with. You see, the Turing Machine is a Form, in Plato's sense. I can formulate all of the programs and machines imaginable (at this current moment in our lifetime) with Turing's process for creating machines. The individual machines created from his process may not be able to run Turing-complete code, e.g. a calculator formalized as a Turing Machine. But our machines, our computers, are machines which can accept other machines as input. And even in this limited domain we cannot solve the Halting Problem, so I consider them a part of the Turing Machine class even if they are descendants of Turing's Form. Edit: In more concrete terms, one can design a very simple program in C, but that doesn't mean that C isn't capable of being used to design more complicated programs. It also isn't very useful to measure a _specific_ C program, especially a simple one, as a measure of what _all_ C programs may be able to do. Edit^2: After thinking about this more, I think a better argument is this: it is true that our physical machines must exist in some sort of finite state, but if our big problems (such as the Halting Problem) were merely symptoms of infinity, then we would have solved them by now in our limited and finite domain.

daniel-cussen 3y ago

[dead]

russdill 3y ago

A Turing machine with a finite tape can be simulated with an FSM, and so is in a lower class.

leroy-is-here 3y ago
I thought about your comment a lot and here’s a way, way better illustration: You are completely correct that we can formalize any Turing Machine as a FSM but! this _must_ include input. Again, this is just pure simulation as you state. Again, we can write a _single_ Turing Machine program with a _single_ input baked in as an FSM and that input _must_ be finite. But that FSM is not capable of handling _any_ input like the the Turing Machine it is simulating. That’s kinda the big difference between Turing machines and machines of a lower class. Any FSM has limited input thus limited states, but a Turing Machine can run infinitely with finite input. So, one can simulate the Turing Machine _with_ input using a FSM up to state N. But the actual Turing Machine can execute up to N+1 without having to hard-code any inputs and is capable of handling other inputs. Again, your computer is a Turing Machine capable of accepting Turing Machines as input. We can hard-code any individual programs and make them into a physical computer chip — just as we did with our computers which can accept any input it can handle, limited only by its physical limitations. But these physical limitations are not an indicator of it being of a lower class because we can keep pushing those limitations back and still compute more of states of these programs. Anyway, I’m glad you mentioned all of this because I went and pulled out my books.
leroy-is-here 3y ago
Because the "tape" is infinite, then the possibilities to name individual machines are infinite. I can create the number of a machine which is just a simple non-deterministic finite automata using a Turing Machine description. My point is that we can always use more powerful machines to describe less powerful ones, but that isn't an indicator that they are then less powerful.
- russdill 3y ago
  My point being is that from a computational complexity standpoint, your computer is not a Turing machine, just a very very very large FSM. So it's still very useful to think of it as a Turing machine.
  - leroy-is-here 3y ago
    Again, if your computer is not a Turing Machine, then it must be able to run programs that the Turing Machine class is not able.
    - russdill 3y ago
      I'm saying that a silicon computer a lower completely class than a theoretical Turing machine, not higher
      - leroy-is-here 3y ago
        I think I agree with you, but maybe not for reasons you agree with. You see, the Turing Machine is a Form, in Plato's sense. I can formulate all of the programs and machines imaginable (at this current moment in our lifetime) with Turing's process for creating machines. The individual machines created from his process may not be able to run Turing-complete code, e.g. a calculator formalized as a Turing Machine. But our machines, our computers, are machines which can accept other machines as input. And even in this limited domain we cannot solve the Halting Problem, so I consider them a part of the Turing Machine class even if they are descendants of Turing's Form. Edit: In more concrete terms, one can design a very simple program in C, but that doesn't mean that C isn't capable of being used to design more complicated programs. It also isn't very useful to measure a _specific_ C program, especially a simple one, as a measure of what _all_ C programs may be able to do. Edit^2: After thinking about this more, I think a better argument is this: it is true that our physical machines must exist in some sort of finite state, but if our big problems (such as the Halting Problem) were merely symptoms of infinity, then we would have solved them by now in our limited and finite domain.