Hold on, this is my area of study.

A Turing machine has two components: a tape, and a head. You also need a bunch of "states", which are exactly what you think they are, for example "currently checking if player is in this room". The tape is made out of an infinite number of squares, starting at square 0 (the beginning square, which is always blank), then 1, 2, 3, 4, etc. It goes on forever, but this is just a mathematical way of saying "we can't run out of memory", since that would complicate things. Practically we don't use the infinity of the tape. Anyhow, in each of the squares there can be a symbol, or it can be blank. Typically we use 0 and 1 as symbols.

Now, the head is in a certain state, (roughly) meaning it's performing a certain task. It reads the symbol on the tape, and then based on the symbol it read and the state it's in, it writes another (not necessarily a different) symbol on the current square, goes into another (not necessarily different) state (moves onto another taks) and either moves a square to the left or to the right. The Turing machine ends it computation when it doesn't know what to do.

To begin with, we put an unbroken string of symbols on the tape, starting from square one. This means we cannot use spaces and square 0 has to be blank.

An example of a Turing machine might be a machine that converts 1's to 0's and vice versa. We have states q_0 (I just awoke and haven't done anything, the beginning state) and q_1 (currently converting 1's to 0's and 0's to 1's). Now, since the head of the tape starts at a blank square (the beginning square is always blank), we need it to move to the right to start converting the input. We also don't need to do anything to the blank space, so we write a blank (we'll use the letter B ). For the state, we know the input starts at square one, so we want to be ready for that as we'll end up on square one, so we go to state q_1. Quickly put:

(q_0,B ) -> (q_1,B,R)

Mean if in state q_0 encountering symbol B, go to state q_1, write symbol B and go one step to the right.

Alright, suppose we are in state q_1 (currently converting). Say we read a 0. Then we need to convert this to a 1 (so write a 1) and go to the right to see if there's more to convert. That also means we should remain in q_1. With reading a 1 we need to write a 0. Thus we get:

(q_1,0) -> (q_1,1,R)

(q_1,1) -> (q_1,0,R)

Now, what happens if we reach the end of the input? We'll encounter a blank square, and at this point the Turing machine does not know what to do, so it quits. The end result is that all the 1's and 0's on the tape have been converted (the input had to be unbroken) and the Turing machine has done its job.

Does that make more sense?

Like I said above, the infinite thing is just so you can say you never run out of room. You can use a finite room with a finite amount of light switches as input (it's not required to be able to write blanks), then a guard as the tape head and have him move to the next object based on his state or whatever. It's probably complete. Most things are.

**Edited by 161803398874989, 08 July 2014 - 12:54 PM.**