UNIT V:Turing
Machine
Prepared By
Mrs. A. B. Dhage
Devices of Increasing
Computational Power
• So far:
• Finite Automata – good for devices with small amounts of memory,
relatively simple control
• Pushdown Automata – stack-based automata
• Limitations:
1. Amount of Memory(Limited)
2. The way of accessing the memory (PDA can access only top of the
stack )
3. Input Tape (Finite)
4. Tape head is read only.
Who was Alan
Turing?
• Founder of computer science, mathematician,
philosopher,
code breaker.
• Introduced TM in 1936!
Turing
machine !
- models a “human computer”
(human writes/rewrites symbols on a sheet of paper, the human’s state of mind
changes based on what s/he has seen)
- The Turing machine is a mathematical model not of
computers, but of computation.
• His computer model –the Turing Machine– was
inspiration of the electronic computer that came
two decades later
Turing
Machines
• TM’s described in 1936 by Alen Turing
• Abstract model for today’s computers
Components of TM :
• Finite Control : A TM consists of a finite control (i.e. a finite
state automaton).
• Infinite tape : FC is connected to an infinite [Link] tape
consists of cells where each cell holds a symbol from the tape
alphabet. Initially each cell has blanks.
• Tape Head : Reads one cell at a time and moves to L/ R / N
• States : Initial State , Final State
T
M
States &
Transitions
Read
Writ
e Move Left
a/ b /
q1 L q2
Move Right
a/ b /
q1 R q2
Turing Machine
Details
•In one move the TM will:
1. Change state, which may be the same as
the current state
2. Write a tape symbol in the current cell,
which may be the same as the current
symbol
3. Move the tape head left or right one cell
4. The special states for rejecting and
accepting take effect immediately
Formal definition
of TM
• Formally, the TM is denoted by the 7-tuple:
• M = (Q, , Γ, δ, q0, B, qa)
Q = finite states of the control
= finite set of input symbols, which is a subset of Γ below
Γ = finite set of tape symbols
δ = transition function. δ(q,X)=(p,Y,D)
p,q ϵ Q and X,Y ϵ Γ and D
= ,L/R/N q0= start state for finite control
B = blank symbol. This symbol is in Γ but not
in . qaccept = set of final or accepting states of Q.
Turing Machine:
Input Tape
alphabet alphabet
States
M (Q , , , , q 0 , B ,
F )
Transitio Final
n
function states
Initial blank
state
Transition
function
X/Y/D
q p
Instantaneous
description
• processing of a string by TM can be shown
using the instantaneous description.
• The ID of TM includes :
1. All non-blank cells in the tape
2. Position of head.
3. Current state of machine
Instantaneous
Description (ID)
Turing Machines are deterministic
Allowed Not
Allowed
a b, R q2 a b, R q2
q1 q1
bd, q3 q3
ad,
L L
No empty move is allowed
Halting and
Acceptance
• The machine halts if there are no possible
transitions to follow.
• A i/p string is accepted by TM if scanning of the
string is completed from left to right and machine is
in the final State.
Transition
Table
I/P a B
State
q0 (q0,a,R) (q1,B,N)
q1 - -
Handr
un
• Let us trace “aa”
1. a a B
q0
2. a a B
q0
3. a a B
Accept
q1
TM for
calculations
• TMs can also be used for calculating values
• Like arithmetic computations
• Eg., addition, subtraction, multiplication, etc.
Equivalence of TM’s and
Computers
• In one sense, a real computer has a finite amount
of memory, and thus is weaker than a TM.
• But, we can postulate an infinite supply of tapes,
disks, or some peripheral storage device to
simulate an infinite TM tape. Additionally, we can
assume there is a human operator to mount disks,
keep them stacked neatly on the sides of the
computer, etc.
• Need to show both directions, a TM can simulate a
computer and that a computer can simulate a TM
Computer Simulate
a TM
• This direction is fairly easy - Given a computer with
a modern programming language, certainly, we can
write a computer program that emulates the finite
control of the TM.
• The only issue remains the infinite tape. Our
program must map cells in the tape to storage
locations in a disk. When the disk becomes full, we
must be able to map to a different disk in the stack
of disks mounted by the human operator.
TM Simulate a
Computer
• In this exercise the simulation is performed at the level of
stored instructions and accessing words of main
memory.
• TM has one tape that holds all the used memory locations and
their contents.
• Other TM tapes hold the instruction counter, memory address,
computer input file, and scratch data.
• The computer’s instruction cycle is simulated by:
1. Find the word indicated by the instruction counter on the
memory tape.
2. Examine the instruction code (a finite set of options), and
get the contents of any memory words mentioned in the
instruction, using the scratch tape.
3. Perform the instruction, changing any words' values as
needed, and adding new address-value pairs to the memory tape,
Turing Machine
Variants
• There are many variations we can make to the basic
TM
• Extensions can make it useful to prove a theorem or
perform some task
• However, these extensions do not add anything extra
the basic TM.
TM
variants
1. Multitape TM
2. Multitrack TM
3. Non deterministic TM
Multitape Turing
Machines
• A multitape Turing machine has several tapes
instead of one tape and each tape with a separate
head.
• Each head can move independently of the others
• The transition function is changed to allow for
reading, writing, and moving the heads on all the
tapes simultaneously.
• This means we could read on multiples tape and move
in different directions on each tape as well as write a
different symbol on each tape, all in one move.
Continu
e..
Multitape
Machine
… 0 1 0 1 0 B …
… a a a B …
M
… b a B …
Equivalent Single Tape Machine:
How a multitape TM
operates?
• Initially:
• The input is in tape #1 surrounded by blanks
• All other tapes contain only blanks
• The tape head for tape #1 points to the 1st symbol of the input
• The heads for all other tapes point at an arbitrary cell (doesn’t
matter because they are all blanks anyway)
• A move:
• Is a function (current state, the symbols pointed by all the
heads)
• After each move, each tape head can move independently (left
or right) of one another
Multitrack
TM
continu
e…
Deterministic and
Nondeterministic TM
• Deterministic : when the transition rules
represented as five-tuples (s, x, s’, are
where s, x are the current state and tape symbol, d),
x’, s’,
x’ are the next state and tape symbol, and d is the
move direction, then no two transition rules begin
with the same pair (s, x), i.e., the mapping
(s,x) → (s’, x’, d) is a function.
NT
M
• In a nondeterministic Turing machine there
maybe more that one transition rule beginning
with the same pair eg (q, X).
• A non-Deterministic Turing Machine allows more
than one possible action per given state-tape
symbol pair.
• A string w is accepted by TM if after being put on
the tape and letting TM run, TM eventually enters
qacc on some computation branch.
A Universal Turing
Machine
Prepared by Prof. [Link]
A limitation of Turing Machines:
Turing Machines are “hardwired”
they execute
only one
program
Real Computers are re-
programmable
Prepared by Prof. [Link]
Solution: Universal Turing
Machine
A Universal Turing Machine is a TM that
can simulate the behavior of any other
Turing Machine
Prepared by Prof. [Link]
Continue
• A universal … machine,
Turing a machine that
can do any computation if the appropriate
program is provided, was the first description
of a modern computer. It can be proved that
a very powerful computer and a universal
Turing machine can compute the same thing.
We need only provide the data and the
program—the description of how to do the
computation—to either machine.
• In fact, a universal Turing machine is capable
of computing anything that is computable.
Prepared by Prof. [Link]
Universal Turing Machine
simulates any Turing Machine
Input of Universal Turing
Machine:
Description of transitions M
of
Prepared by Prof. [Link]
Tape
Three 1
tapes
Description of M
Univers
Tape
al 2
Turing Tape Contents M
Machine of
Tape
3
Prepared by Prof. [Link] State of M
Tape
1
Description of M
We describe Turing machine M
as a string of symbols:
We encode M as a string of symbols
Prepared by Prof. [Link]
Alphabet
Encoding
Symbol a b c d
s:
Encodin 1 11 111 1111
g:
Prepared by Prof. [Link]
State Encoding
States: q1 q2 q3 q4
Encodin 1 11 111 1111
g:
Head Move
Encoding
Move
: L R
Encodin 1
Transition
Encoding
Transition (q1 , a) (q2 ,b,
:
L)
Encodin 1 0 1 0 11 0 11
g: 01
separato
r
Prepared by Prof. [Link]
Turing Machine
Encoding
Transitions
:
(q1 , a) (q2 ,b, (q2 ,b) (q3 , c,
L) R)
Encoding:
1 0 1 0 11 0 11 0 1 00 11 0 110 111 0 111
01
Tape 1 contents of Universal Turing
Machine:
binary encoding
of the simulated machine M
Tape 1
1 0 1 0 11 0 11 0 10011 0 1 10 111 0
111 0 1100 Prepared by Prof. [Link]
A Turing Machine is described with a
binary string of 0’s and 1’s
Therefore:
The set of Turing machines forms a
language:
each string of this language is the
binary encoding of a Turing Machine
Prepared by Prof. [Link]
Language of Turing
Machines
L= (Turing Machine
{ 010100101, 1)
001001001011 (Turing Machine
11, 2)
111010011110010 …
101, …
…… Prepared by Prof. [Link]
Halting
Given a Problem
program and an input to the program,
determine if the program will eventually stop
when it is given that input.
Prepared by Prof. [Link]
proof that the Halting
unsolvable
Problem is
This proof was devised by Alan Turing, 1936.
Suppose you have a solution to the halting problem
called H. H takes two inputs:
1. a program P and
2. an input I for the program P.
H generates an output "halt" if H determines that P
stops on input I or it outputs "loop" otherwise.
Prepared by Prof. [Link]
Continue
..
So now H can be revised to take P as both inputs (the
program and its input) and H should be able to
determine if P will halt on P as its input.
Let us construct a new, simple algorithm K that takes
H's output as its input and does the following :
1. if H outputs "loop" then K halts,
2. otherwise H's output of "halt" causes K to loop forever.
That is, K will do the opposite of H's output.
Prepared by Prof. [Link]
Continue
function ..
K() {
if (H()=="loop"){
return;
}else {
while(true); //loop forever
}
}
Since K
is a
progra
m, let
us use
K as
the Prepared by Prof. [Link]
Continue
..
• If H says that K halts then K itself would loop (that's
how
we constructed it).
• If H says that K loops then K will halt.
In either case H gives the wrong answer for K.
Thus H cannot work in all cases.
We've shown that it is possible to construct an input
that causes any solution H to fail.
Prepared by Prof. [Link]
Turing
Languages
• Three classes of languages:
• Turing-decidable or recursive: TM can accept the strings
in the language and tell if a string is not in the language.
Sometimes these are called decidable problems.
• Turing-recognizable or recursively enumerable : TM can
accept the strings in the language but cannot tell for
certain that a string is not in the language. Sometimes
these are called partially-decidable.
• Undecidable : no TM can even recognize ALL members
of the language.
Recursively Enumerable
Languages
• A TM accepts a string w if the TM halts in a final state. A
TM rejects a string w if the TM halts in a non final state or
the TM never halts.
• A language L is recursively enumerable if some TM accepts
it. Hence they are also called as Turing Acceptable L .
• Recursively Enumerable Languages are also
called
Recognizable
Recursive
Language
• Recursive Language : A language L is recursive if some
TM
accepts it and halts on every input.
• Recursive languages are also called Decidable Languages
because a Turing Machine can decide membership in those
languages (it can either accept or reject a string).
Undecidable
Languages
• undecidable language = not decidable language
• If there is no Turing Machine which accepts the
language and makes a decision (halts) for every
input string.
• Note : (machine may make decision for some input
strings)
• For an undecidable language, the corresponding
problem is undecidable (unsolvable):
Comparison with Previous
Models
Separat Read/Write Determinis
Device
e Data tic by
Input? Structure default?
FA Yes None Yes
PDA Yes LIFO Stack No
1-way infinite Yes
TM No tape.1 cell (but will
access per also allow