What is this Turing machine thing actually?
How is it supposed to be able to solve any problem that can be solved algorithmically?
What is a Turing Machine?
The Turing Machine is not an actual device but more of a thought experiment.
I would suggest a look at the Wikipedia entry for more info, but it is quite complex:
http://en.wikipedia.org/wiki/Turing_machine
I would suggest a look at the Wikipedia entry for more info, but it is quite complex:
http://en.wikipedia.org/wiki/Turing_machine
- Moose On The Loose
- Posts: 965
- Joined: Thu 24 Feb 2011, 14:54
Re: What is a Turing Machine?
See the other reply first.mahaju wrote:What is this Turing machine thing actually?
How is it supposed to be able to solve any problem that can be solved algorithmically?
The Turing machine is part of a thought experiment that shows that all nontrivial computers are able to do the same thing.
It is a good point because it also proves that Puppy Linux need not only be run on x86 machines. Any other nontrivial machine could run it. An ARM has been suggested in this forum. I could also suggest that a machine like an 8052 could be used.
- Lobster
- Official Crustacean
- Posts: 15522
- Joined: Wed 04 May 2005, 06:06
- Location: Paradox Realm
- Contact:
Turing machines as I understand it, do one bit of computation after another. Multicores and modern computers can do several bits at a time . . . (multi-threading)What is this Turing machine thing actually?
. . . and one day there will be Quantum computers, they do not follow the Turing model. Who would like to explain them?
So Turing machine is a 1 bit microprocessor with 1 bit bus and no registers?
If it can only handle a single 1 bit number at a time what kind of ALU is it supposed to have?
What does it mean by able to go forward/backward on a tape and add or erase bits actually? What relationship does having those properties have with Turing Machine being able to implement "any" algorithm ?
If it can only handle a single 1 bit number at a time what kind of ALU is it supposed to have?
What does it mean by able to go forward/backward on a tape and add or erase bits actually? What relationship does having those properties have with Turing Machine being able to implement "any" algorithm ?
- Moose On The Loose
- Posts: 965
- Joined: Thu 24 Feb 2011, 14:54
Quantum computers process more than one Qbit[1] at a time so they are a little like the multicore processor. I think that they will be limited in size by decoherence so that they will be a very fast way to solve problems within the grasp of brute force methods and hence never be of much use.Lobster wrote:What is this Turing machine thing actually?
. . . and one day there will be Quantum computers, they do not follow the Turing model. Who would like to explain them?
[1] Qbit this is an amount of information that is by the nature of quantum physics is always limited. A great example is the polarization of light. A photon only remembers whether it was correctly aligned to go through the last polarizer it met. If you put two linear polarizers in the path a rotate the second one 90 degrees to the first, no light gets through the second one. If you now insert a 3rd polarizer between the first two and rotate it to 45 degrees, light gets through. The photon passing through this middle polarizer must forget all about the first one as it learns about this one. It can't remember both. We can get to compute stuff that is otherwise very hard to do.