Free Computer Courses Training Tutorials Intelligentedu.com Home  ->  Learn About Computers and Information Technology



Turing Machines: Examples



A Turing machine is a purely logical construct and consists on a tape divided on cells (the medium) and a processing head. The medium is supposed to be both the input and output; the input is entered before starting the machine and the result is the reading on the same tape.

The head’s pointer can do two things: it can move either left or right, or it can change its internal state to one of a given set of states. There’s where set theory comes handy for computer science. Processing ends when reaching a value from a subset of the States set called End States.

I’ll list the examples used in class for: a) a complement function (01011 becomes 10100, etc); b) a “marbles” addition function (1+11 becomes 111); c) a “match pattern” decision function

The notation used will be the following: ‘0X 1YR’ means “when the head is on state 0 and reads a symbol “X”, change to state 1, write a symbol “Y” and move to the right”.


Example 1: Complement function

Symbols = {0, 1} and {B}
States = {0, 1}
End States = {1}

00 01R; When reading a "0" write a "1", move ahead
01 00R; When reading a "1" write a "0", move ahead
0B 1BS; When reading a blank (end of the string) change state to an End State.

That’s all, the head travels through the tape turning each “0″ it finds to “1″ and each “1″ to “0″, Once it reads a blank the state changes to “finalize”.


Example 2: Marbles addition

The model input chain will be “11….111+111….1111″ and the result will have to be the addition of both sides of the “+” symbol. It’s equivalent to having two bowls filled with marbles, and having to determine the total number by placing all of them together. It’s quite simple too.

Symbols = {1, +} and {B}
States = {0, 1, 2}
End States = {2}

01 01R; As long as there are only “1″ move to the right, don’t change anything
0+ 01R; Found the sign, set it to “1″ (dirty trick)
0B 1BR; Finished travelling the string; let’s erase the last “1″ because it was lent at the sign
11 2BS; At state “1″ we know the end was already reached. When we find the first “1″ we delete it and set an End State (we’re done).


Example 3: Identify a pattern

This function is what is known as “decision”; it should set an end state if what was asked resulted true, and a different one if it was false. In this case the function will answer the question, “Does the input string has a pattern formed by a number of a symbol “0″ and exactly the same number of “1″ following it”?; for example, “0011″ returns “yes”, “0100″ returns “no”, “11110000″ returns “no”, etc.

Symbols = {0, 1, x, y, z} and {B}
States = {0, 1, 2, 3, 4, YES, NO}
End States = {YES, NO}

; Initial functions
00 1xR; Replace “0″ by “x” as a mark, move ahead
01 NO; the string begins with a “1″… Can’t match, end right away

; Move functions
10 10R; Found a “0″ right after another, keep travelling right until finding a “1″
1y 1yR; Found a “y” after a “0″, it’s an already marked “1″, skip
2y 2yL; Same as “1y”, but we’re travelling to the left in state 2 (see “11″)
3y 3yR; Same as “1y”
40 40L; See “20″, just go on to find the corner and the first “0″.

; Misc.
11 2yL; Found the first “1″ available when going to the right, mark it, turn around
2x 3xR; Got an “x” mark when going to the left; turn around (it’s as good as the left side limit of the string)
20 40L; Found the first “0″ while traveling to the left. Just go on until finding an “x” mark.
4x 0xR; Just like on “00″, but after a few turns.

; End conditions
3B YES; The whole string is marked, get here from natural “10″, “1y” and “3y” conditions.
31 NO; We found a “1″ when looking for a “0″, there are more “1″ than “0″ or the string is interleaved.
01 NO; The string begins with a “1″, see above in “initial functions”.

How does it work: Find a “0″, mark it “x”; find a “1″, mark it “y”; repeat the process until running out of “0″, in that case, if there’s still a “1″ unmarked, answer “NO”; if we run out of “1″ first, we find that the program is incomplete (tee hee - not my program…); if only marks or a B can be found, answer “YES”.



Song of Time - שיר הזמן Copyright © 2004, 2005 Jaime Soffer. My content is available under the terms of the Creative Commons Attribution-NoDerivs License 2.0 plus an exception for literal translation. All quoted content belong to its owner.