Abstract: The foundation of modern computer science is built on the theory of Turing machine. In this article I am trying to explain the construction of Turing machine. After reading this article you will be able to construct your own Turing machine.
Precautions: Don’t just read it. Work out exercise before proceeding. Think a little bit before going to the solution.
Motivation: I have heard about Turing machine from many speakers which make me curious. So, the main motivation is the curiosity.
Introduction: This section introduces some important terminology. If you are already aware of these terminologies then you can skip this part.
1) Computable Numbers: The numbers whose decimals are calculable by finite means.
2) Automatic machine: If at each stage the motion of a machine is completely determined by the configuration, we shall call the machine an “Automatic machine”.
3) Computing machine:
What is Turing machine?
(For better understanding I am defining the Turing machine mathematically first latter I will give the other definitions.)
Definition: A Turing machine is an abstract computing machine consisting of finite control, an infinitely long tape divided into cells holding a finite set of symbols, and a tape head which reads/ writes on the tape.
| …… | B | 1 | 0 | 0 | 1 | B | ….. | ….. | …… |
It can be described by a 6 tuple (Q , A , B , S , q0 , qa ) where
Q = {qa, q0, q1, q2, …., qm) is a finite set of control states.
A = { a1, a2, a3, a4,……..an) the alphabets , is a finite set of distinct symbols.
B Є A is blank symbol.
S : Q × A → Q × A × {L,R} is the transition function describes the rules for the moves of the Turing machine , where “L” and “R” stand for the tape head moving left and right by one cell respectively.
q0 Є Q is the initial state
qa Є Q is the accepting state (the state which declares that the job is done)
What is the meaning of construction of Turing machine?
The construction of Turing machine means define the 6 tuple which will do the given work.
Now, you are ready to construct your own Turing machine.
EXERCISE 1: We want to construct a Turing machine which will add one to the given binary number.
Guidelines: Now, you should construct the Turing machine. I am going to tell you how to proceed.
Step 1: Addition of binary number.
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10
Add the following binary Numbers.
1) 101 + 10 = 111
2) 100110 + 100001 = 1000111
3) 1000000 + 1 = 1000001
4) 100010 + 1 = 100011
5) 101111 + 1 = 110000
6) 11111 + 1 = 100000
One important observation: Adding one to a binary number is equivalent to search for the first 0 from right in the number. Replace that 0 by 1, Replace all the digits right to that 0 by 0 and leave all the digit left to that zero as it is.
Step 2: Now consider this situation
John and Ron are friends. They have assigned to a work. There are rooms in a row each room contains one digit of a given binary number from left to right. The room where first blank appear indicates the end of the number. They know the room from where number start (left most digit). Using all the information given to them they need to add 1 to the given number. They also know how to add binary number. How will they accomplish this job?
Analogy to Turing machine: you have given a tape which contains a number. Blank indicates the end off the number. You know where the number start (initial state q0 )
First they will search for the end of the number that means maintaining the same state they will move to the next Room until they find the first blank. After getting the first blank they should move back with the change of there state and add 1 to the value in the room. Carry the numbers from each room and keep moving back until they get the carry zero. When carry becomes zero they should stop and declare that the job is done.
Now you are ready to construct the Turing machine. Before proceeding further you may now construct the Turing machine.
Turing machine the first hypothetical computer:
An Abstract computing machine, which move from one state to another using a precise finite set of rules, given by a finite table, and depending on a single symbol it read from a tape.
Universal Turing machine:
Which can be made to do the work of any special-purpose machine, that is to say to carry out any piece of computing if a tape bearing suitable “instruction “ is inserted into it.
EXERCISE 2: Who defined the Turing machine first time?
Solutions:
Ex1: Q = { qa, q0, q1 }
A = { 0, 1, B }
S ( q0 , 0 )= q0 , 0 , R S ( q0 , 1 )= q0 , 1 , R S ( q0 , B )= q1 , B , L
S ( q1 , 0 )= qa , 1 , R S ( q1 , 1 )= q1 , 0 , L S ( q1 , B )= qa , 1 , L
Ex2: Alan Turing
References:
1) Wikipedia
2) Does God Created integer
