Intelligentedu.com
Home
> Learn
About Computers and Information Technology 


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”.
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”.