Turing Machines?

[In My Memory]

I have heard of "Turing Machines", but unfortunately when I've tried to read what are, I cannot make sense of what the language and concepts are supposed to represent. At the very best, the descriptions of a Turing Machine I've come across only allow me to visualize an extremely complicated abacus as the closest thing representation of the basic function of a Turing Machine, but I suspect that such a visualization isnt terribly accurate.

 

I have heard that the ability to build and use a Turing Machine has many scientific applications and philosophical implications, so naturally I am very interested to find out what they are, but I have yet to find a good resource that can explain what these machines are, what they do, how they process data, etc. in language and terms that make sense to a laymen individual.

 

Apparently these machines have something to do with processing information in much the same way as a computer can - I know how to make my computer do the things I want it to do, but I lack the relevant knowledge to be able to explain exactly what the processes going on at the 1s and 0s level is doing or even means. As a consequence, Wikipedia's article and similar articles on Turing Machines featuring charts of binary data sets and comparisons to a computer's "stack" do not have any meaning to me.

 

Thanks in advance for any information that can help me make sense of the obscure underlying principles behind Turing Machines

[matt grime]

They don't actually (have to) exist: it is just a way of thinking abuot doing algorithms. THink of it as a black box, if you will. The questions are: is there a black box that can take in information and give out information. INformation is naturally discrete bits and we we care when or when not an answer can be returned IN THEORY.

[Guest olaan]

I have heard of "Turing Machines", but unfortunately when I've tried to read what are, I cannot make sense of what the language and concepts are supposed to represent. At the very best, the descriptions of a Turing Machine I've come across only allow me to visualize an extremely complicated abacus as the closest thing representation of the basic function of a Turing Machine, but I suspect that such a visualization isnt terribly accurate.

 

It's not as bad as you might think. You can think of a TM as a collection of states and a tape which can be read from and written to (there are version which keep the input and output on distinct tapes as well.) In each state there are some rules for what the TM should do depending on what's on the tape. For exemple, it could be "if the symbol on the tape is 0, write 1, move right to the next symbol, change to state 2". The symbols on the tape could be anything, it doesn't have to be just 0's and 1's, though this is often the case.

 

The most interesting thing about Turing machines is the fact that you can construct a universal TM, which can take other TMs as input and then run them. (In effect, a computer.)

 

They keyword in the Wikipedia article is 'abstract' - it's an abstract model of computation. Building a universal TM is not really feasible since one of the main features of a TM is that the tape is infinite in length, but there is nothing stopping you from constructing TMs for specific problems (provided you limit the size of the input, just as with a regular computer.)

 

Thanks in advance for any information that can help me make sense of the obscure underlying principles behind Turing Machines

 

In computer science, TMs are mostly used implicitly. In complexity theory, for example, the definition of the complexity classes is usually expressed in terms of Turing machines, but you rarely see someone write algorithms using TMs. It is a lot easier to analyse an algorithm written in a programming language, and as long as the PL is Turing equivalent (can compute anything a TM can), then there's no need to go deeper.

 

Most programming languages can simulate the infinite tape (using recursion for example), but I've been told one early version of Fortran was limited in that respect, and wasn't Turing equivalent.

 

As for the philosophical implications, I have no idea.

 

-o