Turing Machine

Posted By on April 29, 2016


Download PDF
Pushdown Automata & Parsing
Non-Deterministic Turing Machine

Download PDF

A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing.

Definition

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −

  • Q is a finite set of states
  • X is the tape alphabet
  • is the input alphabet
  • δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
  • q0 is the initial state
  • B is the blank symbol
  • F is the set of final states

Comparison with the previous automation

The following table shows a comparison of how a Turing machine differs from Finite Automaton and Pushdown Automaton.

Machine Stack Data Structure Deterministic?
Finite Automaton N.A Yes
Pushdown Automaton Last In First Out(LIFO) No
Turing Machine Infinite tape Yes

Example of Turing machine

Turing machine M = (Q, X, ∑, δ, q0, B, F) with

  • Q = {q0, q1, q2, qf}
  • X = {a, b}
  • ∑ = {1}
  • q0= {q0}
  • B = blank symbol
  • F = {qf }
  • δ is given by −
Tape alphabet symbol Present State ‘q0 Present State ‘q1 Present State ‘q2
a 1Rq1 1Lq0 1Lqf
b 1Lq2 1Rq1 1Rqf

Here the transition 1Rq1 implies that the write symbol is 1, the tape moves right, and the next state is q1. Similarly, the transition 1Lq2 implies that the write symbol is 1, the tape moves left, and the next state is q2.

Time and Space Complexity of a Turing Machine

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

Time complexity all reasonable functions −

T(n) = O(n log n)

TM’s space complexity −

S(n) = O(n)

A TM accepts a language if it enters into a final state for any input string w. A language is recursively enumerable (generated by Type-0 grammar) if it is accepted by a Turing machine.

A TM decides a language if it accepts it and enters into a rejecting state for any input not in the language. A language is recursive if it is decided by a Turing machine.

There may be some cases where a TM does not stop. Such TM accepts the language, but it does not decide it.

Designing a Turing Machine

The basic guidelines of designing a Turing machine have been explained below with the help of a couple of examples.

Example 1live streaming film Life 2017

Design a TM to recognize all strings consisting of an odd number of α’s.

Solution

The Turing machine M can be constructed by the following moves −

  • Let q1 be the initial state.
  • If M is in q1; on scanning α, it enters the state q2 and writes B (blank).
  • If M is in q2; on scanning α, it enters the state q1 and writes B (blank).
  • From the above moves, we can see that M enters the state q1 if it scans an even number of α’s, and it enters the state q2 if it scans an odd number of α’s. Hence q2 is the only accepting state.

Hence,

M = {{q1, q2}, {1}, {1, B}, δ, q1, B, {q2}}

where δ is given by −

Tape alphabet symbol Present State ‘q1 Present State ‘q2
a BRq2 BRq1

Example 2

Design a Turing Machine that reads a string representing a binary number and erases all leading 0’s in the string. However, if the string comprises of only 0’s, it keeps one 0.

Solution

Let us assume that the input string is terminated by a blank symbol, B, at each end of the string.

The Turing Machine, M, can be constructed by the following moves −

  • Let q0 be the initial state.
  • If M is in q0, on reading 0, it moves right, enters the stateq1 and erases 0. On reading 1, it enters the state q2 and moves right.
  • If M is in q1, on reading 0, it moves right and erases 0, i.e., it replaces 0’s by B’s. On reaching the leftmost 1, it enters q2 and moves right. If it reaches B, i.e., the string comprises of only 0’s, it moves left and enters the stateq3.
  • If M is in q2, on reading either 0 or 1, it moves right. On reaching B, it moves left and enters the state q4. This validates that the string comprises only of 0’s and 1’s.
  • If M is in q3, it replaces B by 0, moves left and reaches the final state qf.
  • If M is in q4, on reading either 0 or 1, it moves left. On reaching the beginning of the string, i.e., when it reads B, it reaches the final state qf.

Hence,

M = {{q0, q1, q2, q3, q4, qf}, {0,1, B}, {1, B}, δ, q0, B, {qf}}

where δ is given by −

Tape alphabet symbol Present State ‘q0 Present State ‘q1 Present State ‘q2 Present State ‘q3 Present State ‘q4
0 BRq1 BRq1 ORq2 OLq4
1 1Rq2 1Rq2 1Rq2 1Lq4
B BRq1 BLq3 BLq4 OLqf BRqf

Download PDF
Pushdown Automata & Parsing
Non-Deterministic Turing Machine

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com