What is a Turing Machine?

For discussions about programming, programming questions/advice, and projects that don't really have anything to do with Puppy.
Post Reply
Message
Author
User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

What is a Turing Machine?

#1 Post by mahaju »

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

ICPUG
Posts: 1308
Joined: Mon 25 Jul 2005, 00:09
Location: UK

#2 Post by ICPUG »

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

User avatar
Moose On The Loose
Posts: 965
Joined: Thu 24 Feb 2011, 14:54

Re: What is a Turing Machine?

#3 Post by Moose On The Loose »

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.

User avatar
Lobster
Official Crustacean
Posts: 15522
Joined: Wed 04 May 2005, 06:06
Location: Paradox Realm
Contact:

#4 Post by Lobster »

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 . . . (multi-threading)

. . . and one day there will be Quantum computers, they do not follow the Turing model. Who would like to explain them?
:oops:
Puppy Raspup 8.2Final 8)
Puppy Links Page http://www.smokey01.com/bruceb/puppy.html :D

User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

#5 Post by mahaju »

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 ?

User avatar
Moose On The Loose
Posts: 965
Joined: Thu 24 Feb 2011, 14:54

#6 Post by Moose On The Loose »

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?
:oops:
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.

Post Reply