Author 
Message 
mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Tue 15 Mar 2011, 02:03 Post subject:
What is a Turing Machine? 

What is this Turing machine thing actually?
How is it supposed to be able to solve any problem that can be solved algorithmically?

Back to top



ICPUG
Joined: 24 Jul 2005 Posts: 1301 Location: UK

Posted: Tue 15 Mar 2011, 09:30 Post subject:


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

Back to top



Moose On The Loose
Joined: 24 Feb 2011 Posts: 668

Posted: Tue 15 Mar 2011, 09:46 Post subject:
Re: What is a Turing Machine? 

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? 
See the other reply first.
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.

Back to top



Lobster
Official Crustacean
Joined: 04 May 2005 Posts: 15205 Location: Paradox Realm

Posted: Tue 15 Mar 2011, 10:17 Post subject:


Quote:  What is this Turing machine thing actually? 
Turing machines as I understand it, do one bit of computation after another. Multicores and modern computers can do several bits at a time . . . (multithreading)
. . . and one day there will be Quantum computers, they do not follow the Turing model. Who would like to explain them?
_________________ Tmxxine Open Source InterDimensional Travel

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Tue 15 Mar 2011, 20:49 Post subject:


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 ?

Back to top



Moose On The Loose
Joined: 24 Feb 2011 Posts: 668

Posted: Tue 15 Mar 2011, 21:15 Post subject:


Lobster wrote:  Quote:  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?

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.
[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.

Back to top



