Type 0 Formalism:
Turing Machine (TM)
PREPARED BY,
NEENA V V
2
Turing Machine (TM)
► A Turing machine is a mathematical model of computation that defines
an abstract machine, which manipulates symbols on a strip of tape according to
a table of rules.
► The Turing machine was invented in 1936 by Alan Turing.
► This machine can simulate ANY computer algorithm, no matter how
complicated it is
3
Turing Machine (TM)
► A Turing machine is a tool for studying computability of mathematical
function.
► A function is computable if and only if it can be computed by TM.
► The purpose of theory of TM is to prove that certain specific languages have no
algorithm.
► A programming language is Turing complete, if it is equivalent to a TM.
4
Turing Machine (TM)
► A Turing machine consists of a tape of
infinite length on which read and writes
operation can be performed.
► The tape consists of infinite cells on
which each cell either contains input
symbol or a special symbol called blank.
► It also consists of a head pointer which
points to cell currently being read and it
can move in both directions.
5
Turing Machine (TM)
► In one move the TM will:
► Change state, which may be the same as the current state
► Write a tape symbol in the current cell, which may be the same as the
current symbol
► Move the tape head left or right one cell
6
Formal definition-Turing Machine (TM)
► Turing Machine M is denoted by the 7-tuple:
► M = (Q, ∑, Γ, δ, q0, B, F) where,
► Q - A finite set of states
► ∑ - finite set of input symbols
► Γ - finite set of tape symbols, ∑ Г
► δ - transition function.
► q0 – Initial state, q0 Q
► B - blank symbol. This symbol is in Γ but not in ∑.
► F – Finite set of final states , F Q
7
Formal definition-Turing Machine (TM)
► The transition function of TM δ is of the form:
8
Formal definition-Turing Machine (TM)
9
Instantaneous Description(ID) of TM
► Initially, a TM has a tape consisting of a string of input symbols surrounded by an infinity of
blanks in both directions.
► The TM is in the start state, and the head is at the leftmost input symbol.
► An instantaneous description or configuration of a Turing machine requires :
► The current state
► The content of the tape
► The position of the tape head on the tape
10
Instantaneous Description(ID) of TM
► An ID is a string αqβ, where ,
► q is the current state
► αβ is the symbols in tape between the leftmost and rightmost blanks.
► The head points to the first character of the substring β.
► The initial ID denoted by qαβ, where q is the start state and head points to the
first character of the substring α.
► The final ID is denoted by αβqB, where qЄF, and the head points to the blank
character denoted by B.
11
Instantaneous Description(ID) of TM
12
Instantaneous Description(ID) of TM
13
Languages of a TM
► A TM defines a language by final state.
► Let M = (Q, ∑, Γ, δ, q0, B, F) be a TM, then the language accepted by TM is:
► The language accepted by a Turing Machine is called Recursively Enumerable
language.
14
Turing machine as Language
Acceptors
15
Turing machine Design
► Design a TM that accepts the language over all strings over the alphabet ∑ =
{a,b} where second letter is ‘b’.
16
Turing machine Design
► Design a TM that accepts the language over all strings over the alphabet ∑ =
{a,b} where second letter is ‘b’.
17
18
19
20
21
Turing machine – Language Acceptors
► Design a TM that accepts all the strings that has even number of 1’s.
L ={1n | n is even}.
22
23
Turing machine – Language Acceptors
► Design a TM that accepts all the strings that has even number of 1’s.
L ={1n | n is even}.
24
25
Turing machine – Language Acceptors
► Design a TM that accepts all the strings over {0,1} that has even number of
1’s.
26
Turing machine – Language Acceptors
► Design a TM that accepts all the strings over {0,1} that has even number of
1’s.
27
28
Turing machine – Language Acceptors
► Design a TM that accepts all the strings over {0,1} that has odd number of 1’s.
29
Turing machine – Language Acceptors
► Design a TM that accepts all the strings over {0,1} that has odd number of 1’s.
30
31
32
33
Turing machine – Language Acceptors
► Design a TM that accepts L={0n1n |n >0} over {0,1} .
34
Turing machine – Language Acceptors
► Design a TM that accepts L={0n1n |n >0} over {0,1} .
35
36
37
38
39
40
Turing machine – Language Acceptors
► Design a TM that accepts L={anbncn|n >0} over {0,1} .
41
42
43
Turing machine – Language Acceptors
► Design a TM that accepts L={anbncn|n >0} over {0,1} .
44
45
46
Turing machine – Language Acceptors
► Design a TM that accepts L={anb2n|n >0} over {0,1} .
47
48
49
Turing machine – Language Acceptors
► Design a TM that accepts L={a2nbn|n >0} over {0,1} .
50
51
52
Construction of TM from given DFA
► Steps :
► 1. Change the edge label of DFA a and b as a/a-> and b/b->
► 2. Add a new final state
► 3. Add an arc B/B-> from old final state to new final state.
53
54
55
56