Crazy Turing Machine

Written on Saturday, May 03, 2008 by Ennah, the comsci student

Imagine some decades ago, the only mathematical machine that people are using is the Turing Machine. Gosh, I imagined their life to be miserable because my life was miserable because of this machine problem. It was really VERY HARD. and complicated.

Post here my research 2 about Turing Machine. In which it really helped me to understand it better and I actually come up with its replica in VB.Net and Java. If you need help in building one, I can help you.

What is a Turing Machine?

A Turing machine is a computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

What is its Purpose?

A Turing machine is a theoretical computing machine that serves as an idealized model for mathematical calculation. Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do.

There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:

• read (i.e. identify) the symbol currently under the head
• write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
• move the tape left one square
• move the tape right one square
• change state
• halt.

What is the mechanical parts of a Turing Machine?

• an Input/Output Tape,
• the Turing Machine itself,
• and a Rule List

The Input/Output Tape is like the roll of paper you find on some printing calculators, only this roll of paper is infinitely long and is stretched like a scroll between two rollers so it can be wound forwards and backwards. The tape is divided into cells. The cells contain the input and output symbols and change frequently as a program is running.

The Turing Machine itself is some kind of mechanical 'black box' that sits above the tape and reads in symbols one at a time from its Read/Write head. The machine is always in a particular internal State indicated by a number on the box.

The Rule List is what determines the Machine's move at any particular point. The rule looks at the state of the head, and the color of the cell that the head is on. Then it specifies what the new state of the head should be, what color the head should "write" onto the tape, and whether the head should move left or right.

How it works

A Turing machine has a finite number of states, and, at any point in time, a Turing machine is in one of these states. A Turing machine begins its operation in the start state. A Turing machine halts when it moves into one of the halt states.

When a Turing machine begins running, it is in its start state and its tape head is positioned over one of the cells on the tape; the symbol on this cell is the current symbol.

The operation of a Turing machine proceeds as follows:

1. The Turing machine reads the tape symbol that is under the Turing machine's tape head. This symbol is referred to as the current symbol.
2. The Turing machine uses its transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.
3. The Turing machine changes its state to the next state, which was returned by the transition function.
4. The Turing machine overwrites the current symbol on the tape with the next symbol, which was returned by the transition function.
5. The Turing machine moves its tape head one symbol to the left or to the right, or does not move the tape head, depending on the value of the 'movement' that is returned by the transition function.
6. If the Turing machine's state is a halt state, then the Turing machine halts. Otherwise, repeat sub-step #1.

The Turing Machine reads a symbol from the Input/Output Tape and consults its Rule List. It then performs two actions.

1. It modifies its internal state
2. It writes a symbol on the tape
   Or Moves its R/W head left or right.

Example:

Suppose the machine is in State 10 and the Read/Write head is positioned on the letter 'A'. The Turing Machine would consult its Rule List and possibly find the following rule:
10 A 12 > This rule says: If you are in State 10 and reading an 'A' change to State 12 and advance the tape head to the right.

References:
http://www.wolframscience.com/prizes/tm23/turingmachine.html
http://plato.stanford.edu/entries/turing-machine/#Describing
http://en.wikipedia.org/wiki/Turing_machine
http://www.unidex.com/turing/tm_intro.htm

Posted in computer science, principles of programming |

If you enjoyed this post Subscribe to our feed