36-TM Encoding, Universal TM-22-04-2024

BCSE304L
Theory of Computation
Lecture 28
Dr. Saritha Murali
(SCOPE, VIT Vellore)
22-04-2024
Encoding of Turing machine
Let M = (Q, Σ, Γ, d, q1, B, F) where Q = {q1 , q2 , q3 , . . . , qn }, q1 – initial state,
Γ = { 0, 1, B} , Σ = { 0, 1}
1. Alphabet/Symbol Encoding: 3. State Encoding:

0 -> X1 q1 (initial state)
1 -> X2 q2
B -> X3 q3 , . . .
2. Direction encoding:
L -> D1
R -> D2
Consider the transition function:
d(qi , Xj ) = (qk , Xl , Dm )
• Transition function encoding:

d : 0i 1 0j 1 0k 1 0l 1 0m
• no occurrences of two or more consecutive 1's within the code for a

single transition.
A code for the entire TM M consists of all the codes for the transitions, in
some order, separated by pairs of 1’s:
where each of the C's is the code for one transition of M.

0i 1 0j 1 0k 1 0l 1 0m 11 0i 1 0j 1 0k 1 0l 1 0m 11 . . . 11 . . . 11 . . .
e.g., Consider the following Turing machine with alphabet { 0, 1, B} and
state set {q1 , q2 , q3 , q4 , q5 }, q1 is the initial state, q5 is the final state
and the transitions are
Encoding:
d(q1 , 0 ) = (q2 , 0 , R ) d(q3 , B ) = (q4 , 1 , R ) 0 -> X1
d(q2 , 0 ) = (q3 , 0 , R ) d(q4 , 0 ) = (q3 , 1 , L ) 1 -> X2
B -> X3
d(q3 , 0 ) = (q4 , 1 , R ) d(q4 , 1 ) = (q5 , 1 , R )
d(q3 , 1 ) = (q4 , 1 , L) d(q4 , B ) = (q3 , 1 , L) L -> D1
R -> D2
01 1 01 1 02 1 01 1 02 1102 1 01 1 03 1 01 1 02 11 03 1 01 1 04 1 02 1 02 11
03 1 02 1 04 1 02 1 01 11 03 1 03 1 04 1 02 1 02 11 04 1 01 1 03 1 02 1 01 11
04 1 02 1 05 1 02 1 02 11 04 1 03 1 03 1 02 1 01
Enumeration of Turing machine
111m111m2 11 m3 11 m411 m5 11 m611m711m8111
Each mi is of the form 0i 1 0j 1 0k 1 0l 1 0m
ith integer in binary represents ith Turing machine, say Ti
1 - T1
10 - T2 If the binary integer is not proper encoding, then the
11 - T3 respective TM will have no moves.
100 - T4
101 - T5
110 - T6
111 - T7
.....
Enumeration of Turing machine
• ith integer in binary represents ith TM
Many integers do not correspond to any TM at all

• 11001 does not begin with 0
• 0010111010010100 is not valid because it has three consecutive 1’s
• If wi is not a valid TM code, we shall take Mi to be the TM with one

state and no transitions. That is, for these values of i, Mi is a Turing
machine that immediately halts on any input.
• L(Mi) is ∅ if wi fails to be a valid TM code.
Universal Turing machine (U)
• Lu (universal language): the set of binary strings that encode a pair
(M,w), where
• M is a TM with the binary input alphabet
• w is a string in (0 + 1)*, such that w is in L(M).
• i.e., Lu is the set of strings representing a TM and an input accepted

by that TM
• There is a Universal Turing Machine(U) such that Lu = L(U)
Universal Turing machine (U) as a multi-tape machine
• Universal TM is a TM which can
simulate any TM
• U has three tapes.
• Tape 1: has the encoding of TM, M and the
string w
• Tape 2: contain the input w, in its encoded
form. i.e., Tape symbol Xi of M will be
represented by 0i and tape symbols will be
separated by single 1’s
• Tape 3: Encoded state qi as 0i
Universal Turing machine (U)
1. Examine the input to make sure that the code for M is a legitimate code for some
TM. If not, U halts without accepting.
2. The second tape to contain the input w, in its encoded form.
3. To simulate a move of M, U searches on its first tape for a transition 0i 1 0j 1 0k 1
0l 1 0m such that 0i is the state on tape 3, and 0j is the tape symbol of M that begins
at the position on tape 2 scanned by U. This transition is the one M would next
make. U should:
(a) Change the contents of tape 3 to 0k; that is, simulate the state change
(b) Replace 0j on tape 2 by 0l; that is, change the tape symbol of M.
(c) Move the head on tape 2 to the position of the next 1 to the left or right
4. If M has no transition that matches the simulated state and tape symbol, then in
(3), no transition will be found. Thus, M halts
5. If M enters its accepting state, then U accepts.
In this manner, U simulates M on w. U accepts the coded pair (M,w) if and only if
M accepts w.
U simulates T on t
halts and accepts halts and rejects gets into a loop

Decidability
• A problem is said to be Decidable if we can always construct a
corresponding algorithm that can answer the problem correctly.
• e.g., Determining whether a number is even or odd
• A problem is said to be a Decidable problem if there exists a

corresponding Turing machine which halts on every input with an
answer- yes or no.
• These problems are termed as Turing Decidable since a Turing
machine always halts on every input, accepting or rejecting it.
Decidability
• Semi-Decidable Problems:
The problems for which a Turing machine halts on the input accepted
by it but it can either halt or loop forever on the input which is
rejected by the Turing Machine.
• Such problems are termed as Turing Recognisable problems.
Decidability
• Undecidable Problems:
The problems for which we cannot construct an algorithm that can
answer the problem correctly in finite time are termed as
Undecidable Problems.
• These problems may be partially decidable, but they will never be
decidable.
• That is there will always be a condition that will lead the Turing
Machine into an infinite loop without providing an answer at all.
e.g., There exist no algorithm which can check whether for the
ambiguity of a CFL. We can only say that if a particular string of the CFL
generates two different parse trees then the CFL is ambiguous.
Languages
Recursive language - TM will always halt
- Turing Decidable
Recursively enumerable - TM will halt sometimes and
language may not halt sometimes
- Turing Recognisable
- Partially decidable
Undecidable - No TM for the language

Turing Machines and Halting
• A TM halts if it enters a state, scanning a tape symbol X, and there is
no move in this situation
• Final states have no outgoing transitions. i.e., in a final state the
machine halts
• Those languages with Turing machines that halt eventually, regardless
of whether or not they accept, are called recursive
• Turing machines that always halt, regardless of whether or not they
accept, are a good model of an "algorithm."
Recursive and Recursively Enumerable Languages
• The language accepted by a Turing machine (TM) which halts on all
inputs is called recursive set (Rec).
• The language accepted by a Turing machine (TM) is called recursively

enumerable set (RE).
Chomsky Hierarchy
Non-recursively enumerable
Recursively-enumerable
Recursive
Context-sensitive
Context-free
Regular

36-TM Encoding, Universal TM-22-04-2024

Uploaded by

Copyright:

Available Formats

36-TM Encoding, Universal TM-22-04-2024

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

36-TM Encoding, Universal TM-22-04-2024

Uploaded by

Copyright:

Available Formats

BCSE304L

1. Alphabet/Symbol Encoding: 3. State Encoding:

• Transition function encoding:

• no occurrences of two or more consecutive 1's within the code for a

where each of the C's is the code for one transition of M.

Many integers do not correspond to any TM at all

• If wi is not a valid TM code, we shall take Mi to be the TM with one

• i.e., Lu is the set of strings representing a TM and an input accepted

halts and accepts halts and rejects gets into a loop

• A problem is said to be a Decidable problem if there exists a

Undecidable - No TM for the language

• The language accepted by a Turing machine (TM) is called recursively

You might also like