Monday, July 19, 2010

Turing Machine for Dummies


here's a short definition from a computer engineer buddy of mine (from an online conversation):

David: Suuuper simple

They are a thought experiment.

And are useful for proving things (ie, what a computer can and can't do)

David: basically a turing machine is a black box and a piece of tape

and the tape has writing on it

the box can read one character of writing at a time, then either move the tape left or right, replace the character it's reading, or do nothing

and that's pretty much it

but turing showed that that's all you need to do every computation a modern computer can do

David: so modern computers are modeled after the box

me: why is the infinite tape necessary?

David: there are a whole bunch of computations that you can't do with a turning machine

David: but the "tape" in a computer is 8.79609302 × 10^12 characters long, so essentially it’s the same as a Turing machine

for a more in-depth description from another computer scientist (who doesn't believe modern computers qualify as Turing machines!) click here

No comments:

Post a Comment