UNIT - III

Push Down Automata, Turing Machines, Undecidability

Push Down Automata: Definition of the Pushdown Automaton : the Languages of a PDA, Equivalence of
PDA and CFG's, Acceptance by final state

Turing Machines: Introduction to Turing Machine, Formal Description, Instantaneous description, the
language of a Turing machine

Undecidability: Undecidability, A Language that is Not Recursively Enumerable, An Undecidable

Problem That is RE, Undecidable Problems about Turing Machines

Introduction of Pushdown Automata

Pushdown automata is a way to implement a CFG in the same way we design DFA for a regular grammar.
A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of
information.
Pushdown automata is simply an NFA augmented with an "external stack memory".
The addition of stack is used to provide a last-in-first-out memory management capability to Pushdown
automata.
Pushdown automata can store an unbounded amount of information on the stack.
It can access a limited amount of information on the stack.
A PDA can push an element onto the top of the stack and pop off an element from the top of the stack.
To read an element into the stack, the top elements must be popped off and are lost.
A PDA is more powerful than FA.
Any language which can be acceptable by FA can also be acceptable by PDA.
PDA also accepts a class of language which even cannot be accepted by FA. Thus PDA is much more superior to
FA.

PDA Components:
Input tape: The input tape is divided in many cells or symbols.
The input head is read-only and may only move from left to right, one symbol at a time.
Finite control: The finite control has some pointer which points the current symbol which is to be read.
Stack: The stack is a structure in which we can push and remove the items from one end only.
It has an infinite size.
In PDA, the stack is used to store the items temporarily.
Formal definition of PDA:
The PDA can be defined as a collection of 7 components:
Q: the finite set of states
∑: the input set
Γ: a stack symbol which can be pushed and popped from the stack
q0: the initial state
Z: a start symbol which is in Γ.
F: a set of final states
δ: mapping function which is used for moving from current state to next state
the items temporarily.

Instantaneous Description (ID)

Instantaneous Description (ID) is an informal notation of how a PDA “
computes” an input string and makes a decision whether that string is accepted or rejected.
An ID is a triple (q, w, α), where:
1. q is the current state.
2. w is the remaining input.
3.α is the stack contents, top at the left.

Turnstile Notation
⊢ sign is called a “turnstile notation” and represents
one move.
⊢* sign represents a sequence of moves.

Eg- (p, b, T) ⊢ (q, w, α)

This implies that while taking a transition from state p to state q, the input symbol ‘b’ is consumed, and the top
of the stack ‘T’ is replaced by a new string 'α'

Example : Define the pushdown automata for language {anbn | n > 0}

Solution : M = where Q = { q0, q1 } and Σ = { a, b } and Γ = { A, Z } and δ is given by :

δ( q0, a, Z ) = { ( q0, AZ ) }
δ( q0, a, A) = { ( q0, AA ) }
δ( q0, b, A) = { ( q1, ∈) }
δ( q1, b, A) = { ( q1, ∈) }
δ( q1, ∈, Z) = { ( q1, ∈) }

Let us see how this automata works for aaabbb.

Explanation : Initially, the state of automata is q0 and symbol on stack is Z and the input is aaabbb as shown
in row 1. On reading 'a' (shown in bold in row 2), the state will remain q0 and it will push symbol A on stack.
On next 'a' (shown in row 3), it will push another symbol A on stack. After reading 3 a’s, the stack will be
AAAZ with A on the top. After reading 'b' (as shown in row 5), it will pop A and move to state q1 and stack
will be AAZ. When all b’s are read, the state will be q1 and stack will be Z. In row 8, on input symbol '∈' and
Z on stack, it will pop Z and stack will be empty. This type of acceptance is known as acceptance by empty
stack.
PDA Acceptance

A language can be accepted by Pushdown automata using two approaches:

1. Acceptance by Final State: The PDA is said to accept its input by the final state if it enters any final state in
zero or more moves after reading the entire input.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as: L(PDA) =
{w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}

2. Acceptance by Empty Stack: On reading the input string from the initial configuration for some PDA, the
stack of PDA gets empty.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as:
N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}

Equivalence of Acceptance by Final State and Empty Stack

If L = N(P1) for some PDA P1, then there is a PDA P2 such that L = L(P2). That means the language accepted
by empty stack PDA will also be accepted by final state PDA.
If there is a language L = L (P1) for some PDA P1 then there is a PDA P2 such that L = N(P2). That means
language accepted by final state PDA is also acceptable by empty stack PDA.

Construct Pushdown Automata for given languages

Prerequisite - Pushdown Automata, Pushdown Automata Acceptance by Final State
A push down automata is similar to deterministic finite automata except that it has a few more properties than a
DFA.The data structure used for implementing a PDA is stack. A PDA has an output associated with every
input. All the inputs are either pushed into a stack or just ignored. User can perform the basic push and pop
operations on the stack which is use for PDA. One of the problems associated with DFAs was that could not
make a count of number of characters which were given input to the machine. This problem is avoided by PDA
as it uses a stack which provides us this facility also.

A Pushdown Automata (PDA) can be defined as -

M = (Q, Σ, Γ, δ, q0, Ζ, F) where
 Q is a finite set of states
 Σ is a finite set which is called the input alphabet
 Γ is a finite set which is called the stack alphabet
 δ is a finite subset of Q X ( Σ ∪ {ε} X Γ X Q X Γ*) the transition relation.
 q0 ∈ Q is the start state
 Ζ ∈ Γ is the initial stack symbol
 F ⊆ Q is the set of accepting states

Representation of State Transition -

Representation of Push in a PDA -

Representation of Pop in a PDA -

Representation of Ignore in a PDA -

Example 1: Design a PDA for accepting a language {anb2n | n>=1}.

Solution: In this language, n number of a's should be followed by 2n number of b's.

Hence, we will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the stack.
As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the stack.
The ID can be constructed as follows:
δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,
δ(q0, b, a) = (q1, ε)
Thus this process of popping 'b' will be repeated unless all the symbols are read.
Note that popping action occurs in state q1 only.
δ(q1, b, a) = (q1, ε)
After reading all b's, all the corresponding a's should get popped.
Hence when we read ε as input symbol then there should be nothing in the stack.
Hence the move will be:
δ(q1, ε, Z) = (q2, ε)
Where
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

We can summarize the ID as:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)
Now we will simulate this PDA for the input string "aaabbbbbb".

δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)

⊢ δ(q0, abbbbbb, aaaaZ)

⊢ δ(q0, bbbbbb, aaaaaaZ)

⊢ δ(q1, bbbbb, aaaaaZ)

⊢ δ(q1, bbbb, aaaaZ)

⊢ δ(q1, bbb, aaaZ)

⊢ δ(q1, bb, aaZ)

⊢ δ(q1, b, aZ)

⊢ δ(q1, ε, Z)
⊢ δ(q2, ε)
ACCEPT

Example 2: Design a PDA for accepting a language {0n1m0n | m, n>=1}.

Solution: In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's.

Hence the logic for design of such PDA will be as follows:

Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and on each
read of 0, pop one 0 from the stack.
This scenario can be written in the ID form as:

δ(q0, 0, Z) = δ(q0, 0Z)

δ(q0, 0, 0) = δ(q0, 00)

δ(q0, 1, 0) = δ(q1, 0)

δ(q0, 1, 0) = δ(q1, 0)

δ(q1, 0, 0) = δ(q1, ε)

δ(q1, ε, Z) = δ(q2, Z) (ACCEPT state)

Now we will simulate this PDA for the input string "0011100".

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)

⊢ δ(q0, 11100, 00Z)

⊢ δ(q0, 1100, 00Z)

⊢ δ(q1, 100, 00Z)

⊢ δ(q1, 00, 00Z)

⊢ δ(q1, 0, 0Z)

⊢ δ(q1, ε, Z)

⊢ δ(q2, Z)

ACCEPT
Example: Design PDA for Palindrome strips.

Solution:

Suppose the language consists of string L = {aba, aa, bb, bab, bbabb, aabaa, ......]. The string can be odd
palindrome or even palindrome. The logic for constructing PDA is that we will push a symbol onto the stack till
half of the string then we will read each symbol and then perform the pop operation. We will compare to see
whether the symbol which is popped is similar to the symbol which is read. Whether we reach to end of the
input, we expect the stack to be empty.

This PDA is a non-deterministic PDA because finding the mid for the given string and reading the string from
left and matching it with from right (reverse) direction leads to non-deterministic moves.

Here is the ID

Simulation of abaaba
δ(q1, abaaba, Z) Apply rule 1
⊢ δ(q1, baaba, aZ) Apply rule 5
⊢ δ(q1, aaba, baZ) Apply rule 4
⊢ δ(q1, aba, abaZ) Apply rule 7
⊢ δ(q2, ba, baZ) Apply rule 8
⊢ δ(q2, a, aZ) Apply rule 7
⊢ δ(q2, ε, Z) Apply rule 11
⊢ δ(q2, ε) Accept

CFG to PDA Conversion

The first symbol on R.H.S. production must be a terminal symbol. The following steps are used to obtain PDA
from CFG is:
Step 1: Convert the given productions of CFG into GNF.
Step 2: The PDA will only have one state {q}.
Step 3: The initial symbol of CFG will be the initial symbol in the PDA.
Step 4: For non-terminal symbol, add the following rule:
δ(q, ε, A) = (q, α)
Where the production rule is A → α
Step 5: For each terminal symbols, add the following rule:
δ(q, a, a) = (q, ε) for every terminal symbol

Example 1: Convert the following grammar to a PDA that accepts the same language.
S → 0S1 | A
A → 1A0 | S | ε
Solution:
The CFG can be first simplified by eliminating unit productions:
S → 0S1 | 1S0 | ε
Now we will convert this CFG to GNF:
S → 0SX | 1SY | ε
X→1
Y→0
The PDA can be:
R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}
R2: δ(q, ε, X) = {(q, 1)}
R3: δ(q, ε, Y) = {(q, 0)}
R4: δ(q, 0, 0) = {(q, ε)}
R5: δ(q, 1, 1) = {(q, ε)}
Example 2: Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA.
S → 0BB
B → 0S | 1S | 0
Solution:
The PDA can be given as: A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}
The production rule δ can be:
R1: δ(q, ε, S) = {(q, 0BB)}
R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}
R3: δ(q, 0, 0) = {(q, ε)}
R4: δ(q, 1, 1) = {(q, ε)}
Testing 0104 i.e. 010000 against PDA:
δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)
⊢ δ(q, 10000, BB) R1
⊢ δ(q, 10000,1SB) R3
⊢ δ(q, 0000, SB) R2
⊢ δ(q, 0000, 0BBB) R1
⊢ δ(q, 000, BBB) R3
⊢ δ(q, 000, 0BB) R2
⊢ δ(q, 00, BB) R3
⊢ δ(q, 00, 0B) R2
⊢ δ(q, 0, B) R3
⊢ δ(q, 0, 0) R2
⊢ δ(q, ε) R3
ACCEPT
Thus 0104 is accepted by the PDA.

Example 3: Draw a PDA for the CFG given below:

S → aSb
S→a|b|ε
Solution:
The PDA can be given as:
P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}
The mapping function δ will be:
R1: δ(q, ε, S) = {(q, aSb)}
R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}
R3: δ(q, a, a) = {(q, ε)}
R4: δ(q, b, b) = {(q, ε)}
R5: δ(q, ε, z0) = {(q, ε)}
Simulation: Consider the string aaabb
δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
⊢ δ(q, εaabb, Sb) R1
⊢ δ(q, aabb, aSbb) R3
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT

Non-deterministic Pushdown Automata

The non-deterministic pushdown automata is very much similar to NFA. We will discuss some CFGs which
accepts NPDA.

The CFG which accepts deterministic PDA accepts non-deterministic PDAs as well. Similarly, there are some
CFGs which can be accepted only by NPDA and not by DPDA. Thus NPDA is more powerful than DPDA

NPDA for accepting the language L = {anbm cn | m,n>=1

Problem
The problem can be solved if you have prior knowledge about NPDA.
Design a non deterministic PDA for accepting the language L = {an bm cn | m, n >= 1}, i.e.,
L = { abc, abbc, abbbc, aabbcc, aaabccc, aaaabbbcccc, ...... }
In each of the string, the number of a's is equal to number of c's and the number of b's is independent of
the number of a's and c's.
Explanation
Here, we need to maintain the order of a’s, b's and c’s. That is, all the a's are coming first and then all the b's
and then c's are coming. Thus, we need a stack along with the state diagram. The count of a’s and c’s is
maintained by the stack. The number of a's is exactly equal to the number of c's We will take 2 stack
alphabets:
ΓΓ = { a, z }
Where, Γ Γ = set of all the stack alphabet z = stack start symbol
Approach used in the construction of PDA
As we want to design a NPDA, thus every time 'a' comes before 'b'. When ‘a’ comes then push it in stack and
if again ‘a’ comes then also push it.
For 'b', we will do nothing in the stack only change the state in state diagram and keep skipping b's.
When ‘c’ comes then pop one 'a' from the stack each time .So, at the end if the stack becomes empty then we
can say that the string is accepted by the PDA.
Stack Transition Functions
δδ(q0, a, z) ⊢⊢ (q0, az)
δδ(q0, a, a) ⊢⊢ (q0, aa)
δδ(q0, b, a) ⊢⊢ (q1, a)
δδ(q1, b, a) ⊢⊢ (q1, a)
δδ(q1, c, a) ⊢⊢ (q2, ϵϵ )
δδ(q2, c, a) ⊢⊢ (q2, ϵϵ )
δδ(q2, ϵϵ, z) ⊢⊢ (qf, z )
Where, q0 = Initial state qf = Final state ϵ ϵ = indicates pop

operation So, this is

our required non deterministic PDA for accepting the language L = {an bm cn | m, n >= 1}.

NPDA for accepting the language L = {an bn cm | m,n>=1}

Prerequisite: Basic Knowledge of Pushdown Automata.
Problem
Design a non deterministic PDA for accepting the language L = {anbncm | m, n>=1}, i.e.,
L = { abc, abcc, abccc, aabbc, aaabbbcc, aaaabbbbccccc, ...... }
In each of the string, the number of a's is equal to number of b's and the number of c's is independent of
the number of a's and b's.
Explanation
This problem is quite similar to the NPDA for accepting the language L = {anbn | n>=1 }. The only difference
is that here we add cm.
Here, we need to maintain the order of a’s, b's and c’s. That is, all the a's are coming first and then all the b's
and then c's are coming. Thus, we need a stack along with the state diagram. The count of a’s and b’s is
maintained by the stack. We will take 2 stack alphabets:
Γ = { a, z }
Where,
 Γ = set of all the stack alphabet
 z = stack start symbol
Approach used in the construction of PDA
As we want to design a NPDA, thus every time 'a' comes before 'b'. When ‘a’ comes then push it in stack and
if again ‘a’ comes then also push it. After that, when ‘b’ comes then pop one 'a' from the stack each time .
Then for 'c', we will do nothing. So, at the end if the stack becomes empty then we can say that the string is
accepted by the PDA.
Stack transition functions
𝝳 (q0, a, z) ├ (q0, az)
𝝳 (q0, a, a) ├ (q0, aa)
𝝳 (q0, b, a) ├ (q1, 𝝐 )
𝝳 (q1, b, a) ├ (q1, 𝝐)
𝝳 (q1, c, z) ├ (qf, z )
𝝳 (qf, c, z) ├ (qf, z )
Where,
 q0 = Initial state
 qf = Final state
 𝝐 indicates pop operation
PDA for accepting the language L = {abncm | m, n>=1}

So, this is our required non deterministic PDA for accepting the language L = {anbncm | m, n>=1}.

NPDA for accepting the language L = {anbn | n>=1}

Prerequisite: Basic knowledge of pushdown automata.
Problem :
Design a non deterministic PDA for accepting the language L = {an bn | n>=1}, i.e.,
L = {ab, aabb, aaabbb, aaaabbbb, ......}
In each of the string, the number of a's are followed by equal number of b's.
Explanation
Here, we need to maintain the order of a’s and b’s. That is, all the a's are coming first and then all the b's are
coming. Thus, we need a stack along with the state diagram. The count of a’s and b’s is maintained by the
stack. We will take 2 stack alphabets:
𝛤= { a, z }
Where, 𝛤= set of all the stack alphabet, z = stack start symbol

Approach used in the construction of PDA

As we want to design a NPDA, thus every time 'a' comes before 'b'. When ‘a’ comes then push it in stack and
if again ‘a’ comes then also push it.
After that, when ‘b’ comes then pop one 'a' from the stack each time. So, at the end if the stack becomes empty
then we can say that the string is accepted by the PDA.
Stack transition functions
𝝳 (q0, a, z) ├ (q0, az) [ push a on empty stack]
𝝳 (q0, a, a) ├ (q0, aa) [push a's ]
𝝳 (q0, b, a) ├ (q1, 𝝐 ) [pop a when b comes(state change)]
𝝳 (q1, b, a) ├ (q1, 𝝐 ) [pop a for each b]
𝝳 (q1, 𝝐 , z) ├ (qf, z) [final state]
Where, q0 = Initial state qf = Final state ϵ ϵ = indicates pop operation

PDA𝝳

So, this is our required non deterministic PDA for accepting the language L = { an bn | n>=1}

Recursive and Recursive Enumerable Languages in TOC

Recursive Enumerable (RE) or Type -0 Language

RE languages or type-0 languages are generated by type-0 grammars. An RE language can be accepted or
recognized by Turing machine which means it will enter into final state for the strings of language and may or
may not enter into rejecting state for the strings which are not part of the language. It means TM can loop forever
for the strings which are not a part of the language. RE languages are also called as Turing recognizable
languages.
Recursive Language (REC)
A recursive language (subset of RE) can be decided by Turing machine which means it will enter into final state
for the strings of language and rejecting state for the strings which are not part of the language. e.g.; L=
{anbncn|n>=1} is recursive because we can construct a turing machine which will move to final state if the string
is of the form anbncn else move to non-final state. So the TM will always halt in this case. REC languages are
also called as Turing decidable languages. The relationship between RE and REC languages can be shown in
Figure 1.
Closure Properties of Recursive Languages
 Union: If L1 and If L2 are two recursive languages, their union L1?L2 will also be recursive
because if TM halts for L1 and halts for L2, it will also halt for L1?L2.
 Concatenation: If L1 and If L2 are two recursive languages, their concatenation L1.L2 will also
be recursive. For Example:
L1= {anbncn|n>=0}
L2= {dmemfm|m>=0}
L3= L1.L2
= {anbncndm emfm|m>=0 and n>=0} is also recursive.
 L1 says n no. of a’s followed by n no. of b’s followed by n no. of c’s. L2 says m no. of d’s
followed by m no. of e’s followed by m no. of f’s. Their concatenation first matches no. of a’s,
b’s and c’s and then matches no. of d’s, e’s and f’s. So it can be decided by TM.
 Kleene Closure: If L1is recursive, its kleene closure L1* will also be recursive. For Example:
L1= {anbncn|n>=0}
L1*= { anbncn||n>=0}* is also recursive.
 Intersection and complement: If L1 and If L2 are two recursive languages, their intersection L1 ?
L2 will also be recursive. For Example:
L1= {anbncndn|n>=0 and m>=0}
L2= {anbncndn|n>=0 and m>=0}
L3=L1 ? L2
= { anbncndn |n>=0} will be recursive.

L1 says n no. of a’s followed by n no. of b’s followed by n no. of c’s and then any no. of d’s. L2 says any no. of
a’s followed by n no. of b’s followed by n no. of c’s followed by n no. of d’s. Their intersection says n no. of a’s
followed by n no. of b’s followed by n no. of c’s followed by n no. of d’s. So it can be decided by turing
machine, hence recursive.
Similarly, complement of recursive language L1 which is ?*-L1, will also be recursive.

Turing Machine in TOC

Turing machine was invented in 1936 by Alan Turing. It is an accepting device which accepts Recursive
Enumerable Language generated by type 0 grammar.

There are various features of the Turing machine:

It has an external memory which remembers arbitrary long sequence of input.
It has unlimited memory capability.
The model has a facility by which the input at left or right on the tape can be read easily.
The machine can produce a certain output based on its input. Sometimes it may be required that the same input
has to be used to generate the output.

So in this machine, the distinction between input and output has been removed. Thus a common set of alphabets
can be used for the Turing machine.

Formal definition of Turing machine

A Turing machine can be defined as a collection of 7 components:

Q: the finite set of states

∑: the finite set of input symbols
T: the tape symbol
q0: the initial state
F: a set of final states
B: a blank symbol used as a end marker for input
δ: a transition or mapping function.

Basic Model of Turing machine

The turning machine can be modelled with the help of the following representation.

1. The input tape is having an infinite number of cells, each cell containing one input symbol and thus the input
string can be placed on tape. The empty tape is filled by blank characters.

2. The finite control and the tape head which is responsible for reading the current input symbol. The tape head
can move to left to right.

3. A finite set of states through which machine has to undergo.

4. Finite set of symbols called external symbols which are used in building the logic of turing machine.

Example: Turing Machine

We construct a Turing Machine (TM) for the language L = {0ⁿ1ⁿ | n ≥ 1}, which accepts strings of equal 0s
followed by equal 1s.
Components:
 Q = {q₀, q₁, q₂, q₃} (q₀ is the initial state)
 T = {0,1,X,Y,B} (B represents blank, X and Y mark processed symbols)
 Σ = {0,1} (input symbols)
 F = {q₃} (final state)

Transition Table:

Illustration
Let us see how this turing machine works for 0011. Initially head points to 0 which is underlined and state is
q0 as:

The move will be δ(q0, 0) = (q1, X, R). It means, it will go to state q1, replace 0 by X and head will move to
right as:

The move will be δ(q1, 0) = (q1, 0, R) which means it will remain in same state and without changing any
symbol, it will move to right as:

The move will be δ(q1, 1) = (q2, Y, L) which means it will move to q2 state and changing 1 to Y, it will move
to left as:

Working on it in the same way, the machine will reach state q3 and head will point to B as shown:

Using move δ(q3, B) = halt, it will stop and accepted.

Note:
 In non-deterministic turing machine, there can be more than one possible move for a given state
and tape symbol, but non-deterministic TM does not add any power.
 Every non-deterministic TM can be converted into deterministic TM.
 In multi-tape turing machine, there can be more than one tape and corresponding head pointers, but
it does not add any power to turing machine.
 Every multi-tape TM can be converted into single tape TM.
Question: A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The
tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to
indicate end of an input string. The transition function of M is described in the following

table.
The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is
in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head
one position to the right and transitions to state q1. Which of the following statements is true about M?
1. M does not halt on any string in (0 + 1)+
2. M does not halt on any string in (00 + 1)*
3. M halts on all string ending in a 0
4. M halts on all string ending in a 1
Solution: Let us see whether machine halts on string ‘1’. Initially state will be q0, head will point to 1 as:

Using δ(q0, 1) = (q1, 1, R), it will move to state q1 and head will move to right as:

Using δ(q1, B) = (q0, B, L), it will move to state q0 and head will move to left as:

It will run in the same way again and again and not halt.

Option D says M halts on all string ending with 1, but it is not halting for 1. So, option D is incorrect.

Let us see whether machine halts on string ‘0’. Initially state will be q0, head will point to 1 as:

Using δ(q0, 0) = (q1, 1, R), it will move to state q1 and head will move to right as:

Using δ(q1,B)=(q0,B,L), it will move to state q0 and head will move to left as:

It will run in the same way again and again and not halt.

Option C says M halts on all string ending with 0, but it is not halting for 0. So, option C is incorrect.

Option B says that TM does not halt for any string (00 + 1)*. But NULL string is a part of (00 + 1)* and TM
will halt for NULL string. For NULL string, tape will be,

Using δ(q0, B) = halt, TM will halt. As TM is halting for NULL, this option is also incorrect.
So, option (A) is correct.

Example: Construct TM for the language L ={0n1n} where n>=1.

Solution:
We have already solved this problem by PDA. In PDA, we have a stack to remember the previous symbol. The
main advantage of the Turing machine is we have a tape head which can be moved forward or backward, and
the input tape can be scanned.
The simple logic which we will apply is read out each '0' mark it by A and then move ahead along with the
input tape and find out 1 convert it to B. Now, repeat this process for all a's and b's.
Now we will see how this turing machine work for 0011.
The simulation for aabb can be shown as below:
Transition Functions (B denotes blank)
δ(q0,a)→(q1,X,R)
δ(q1,a)→(q1,a,R)
δ(q1,b)→(q2,Y,L)
δ(q2,a)→(q2,a,L)
δ(q2,X)→(q0,X,R)
δ(q1,Y)→(q1,Y,R)
δ(q2,Y)→(q2,Y,L)
δ(q0,Y)→(q3,Y,R)
δ(q3,Y)→(q3,Y,R)
δ(q3,B)→(q4,B,H)

Explanation of Transition Functions

 It starts in state q0 and replaces the first 'a' with 'X'.
 It moves right, keeping 'a's unchanged, until it finds the first 'b'.
 It replaces the first 'b' with 'Y' and moves left.
 It moves left until it finds 'X', then goes back to step 1.
 If it finds 'Y' instead of 'b', it moves right until it finds a blank, then halts in an accepting state.
Example 1: Turing Machine for WWR
Let us look at a Turing Machine that accepts the language L = {WWR, where W ∈ (a, b)+}. Here,
WR is the reverse of W.

Turing Machine processes the string "abaaaaba"

(q0, abaaaaba) → (q1, Xbaaaaba) → (q1, Xbaaaaba) → (q1, XbaaaabB) →
(q2, XbaaaabB) → (q3, XbaaaabX) → (q3, XbaaaabX) → (q0, XbaaaabX) →
(q4, XYaaaabX) → (q4, XYaaaabX) → (q5, XYaaaabX) → (q6, XYaaaaYX) →
(q0, XYaaaaYX) → (q1, XYXaaaYX) → (q1, XYXaaaYX) → (q2, XYXaaaYX) →
(q3, XYXaaXYX) → (q0, XYXaaXYX) → (q1, XYXXAXYX) → (q2, XYXXAXYX) →
(q3, XYXXXXYX) → (q0, XYXXXXYX) → (qf, XYXXXXYX) [Halt]
The Turing Machine accepts the string "abaaaaba" as it is of the form WWR.
Transition Table

Transition Diagram

Explanation of the Turing Machine

• It replaces the first symbol (a or b) with X or Y.
• It moves to the end of the string.
• It checks if the last symbol matches the first one.
• It moves back to the start and repeats the process for the next symbol.
• If all symbols match, it accepts the string.
 Example 2: Turing Machine for Palindrome

State a b B

q1 (q2, B, R) (q5, B, R) (q7, B, H)

q2 (q2, a, R) (q2, b, R) (q3, B, L)

q3 (q4, B, L) - (q7, B, H)

q4 (q4, a, L) (q4, b, L) (q1, B, R)

q5 (q5, a, R) (q5, b, R) (q6, B, L)

q6 - (q4, B, L) (q7, B, H)

Last one is similar to the palindrome but in real case, a palindrome could be of odd length or even length.
Let us see the Turing Machine that accepts the language L = {set of all palindromes over a, b}.

Null String
(q1,B)→(q7,B)[Halt]
The null string is accepted as a palindrome.
String "a"
(q1,aB)→(q2,BB)→(q3,BB)→(q7,BB)[Halt]
The string "a" is accepted as a palindrome.
String "aba"
(q1,abaB)→(q2,BbaB)→(q2,BbaB)→(q3,BbaB)→(q4,BBBB)→(q1,BBBB)→(q7,BBBB)[Halt]

The string "aba" is accepted as a palindrome.

String "baab"

(q1,baabB)→(q5,BaabB)→(q5,BaabB)→(q6,BaaB)→(q4,BaBB)→(q1,BaBB)→(q2,BBaBB)→(q3,BBABB)→(q7,BBBB
B)[Halt]

The string "baab" is accepted as a palindrome

Last one is similar to the palindrome but in real case, a palindrome could be of odd length or even length. Let us see the
Turing Machine that accepts the language L = {set of all palindromes over a, b}.

Transition Diagram
Explanation of the Turing Machine

 It replaces the first symbol with a blank (B).

 It moves to the end of the string.
 It checks if the last symbol matches the first one.
 It replaces the last symbol with a blank and moves back to the start.
 It repeats this process until all symbols are checked.
 If all symbols match, it accepts the string as a palindrome

Example 3: Turing Machine for an bn cn

This language is context-sensitive. It consists of strings with equal numbers of 'a', 'b', and 'c' in that order. The
number of each symbol must be at least 1.
Transition Table

State a b c B X Y Z

q1 (q2, X, R) - - - - (q5, Y, R) -

q2 (q2, a, R) (q3, Y, R) - - - (q2, Y, R) -

q3 - (q3, b, R) (q4, Z, L) - - - (q3, Z, R)

q4 (q4, a, L) (q4, b, L) - - (q1, X, R) (q4, Y, L) (q4, Z, L)

q5 - - - - - (q5, Y, R) (q6, Z, R)

q6 - - - (qf, B, H) - - (q6, Z, R)

Transition Diagram
Construct a Turing Machine for language L = {0n1n2n | n≥1}
Prerequisite - Turing Machine The language L = {0n1n2n | n≥1} represents a kind of language where we use only
3 character, i.e., 0, 1 and 2. In the beginning language has some number of 0's followed by equal number of 1's
and then followed by equal number of 2's. Any such string which falls in this category will be accepted by this
language. The beginning and end of string is marked by $ sign.
Examples -
Input : 0 0 1 1 2 2
Output : Accepted

Input : 0 0 0 1 1 1 2 2 2 2
Output : Not accepted
Assumption: We will replace 0 by X, 1 by Y and 2 by Z Approach used - First replace a 0 from front by X,
then keep moving right till you find a 1 and replace this 1 by Y. Again, keep moving right till you find a 2,
replace it by Z and move left. Now keep moving left till you find a X. When you find it, move a right, then
follow the same procedure as above. A condition comes when you find a X immediately followed by a Y. At this
point we keep moving right and keep on checking that all 1's and 2's have been converted to Y and Z. If not then
string is not accepted. If we reach $ then string is accepted.
Step-1: Replace 0 by X and move right, Go to state Q1.
Step-2: Replace 0 by 0 and move right, Remain on same state Replace Y by Y and move right,
Remain on same state Replace 1 by Y and move right, go to state Q2.
Step-3: Replace 1 by 1 and move right, Remain on same state Replace Z by Z and move right,
Remain on same state Replace 2 by Z and move right, go to state Q3.
Step-4: Replace 1 by 1 and move left, Remain on same state Replace 0 by 0 and move left, Remain
on same state Replace Z by Z and move left, Remain on same state Replace Y by Y and move left,
Remain on same state Replace X by X and move right, go to state Q0.
Step-5: If symbol is Y replace it by Y and move right and Go to state Q4 Else go to step 1
Step-6: Replace Z by Z and move right, Remain on same state Replace Y by Y and move right,
Remain on same state If symbol is $ replace it by $ and move left, STRING IS ACCEPTED, GO TO
FINAL STATE Q5

Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}

The language L = {wwres | w ∈ {0, 1}} represents a kind of language where you use only 2 character, i.e., 0 and
1. The first part of language can be any string of 0 and 1. The second part is the reverse of the first part.
Combining both these parts a string will be formed. Any such string that falls in this category will be accepted by
this language. The beginning and end of the string are marked by a $ sign. For example, if the first part w = 1 1 0
0 1 then the second part wr = 1 0 0 1 1. It is clearly visible that wr is the reverse of w, so the string 1 1 0 0 1 1 0 0
1 1 is a part of a given language. It can also be said that the strings which are palindrome of even length will be
accepted by this language.
 Examples:

Input : 0 0 1 1 1 1 0 0
Output : Accepted
Input : 1 0 1 0 0 1 0 1
Output : Accepted
Input: 0 1 0
Output: Not Accepted

Basic Representation
Approach 1: Two Pointers
Start from the beginning of the input tape. If the symbol is 0, replace it with Y and move right, or if it's 1, replace
it with X and move right.
Once at the end of the string, move back to the position next to the symbol replaced at the beginning and repeat
the process.
In the new state, check if the symbol at the corresponding position from the end matches the one at the
beginning. If they match, continue; otherwise, reject the string.
Move left and repeat the process until the entire string is processed.
If all symbols match as expected, accept the string.
Assumption: We will replace 0 by Y and 1 by X.
Approach Used - First check the first symbol, if it's 0 then replace it by Y and by X if it's 1. Then go to the end
of string. So last symbol is same as first. We replace it also by X or Y depending on it. Now again come back to
the position next to the symbol replace from the starting and repeat the same process as told above. One
important thing to note is that since wr is reverse of w of both of them will have equal number of symbols. Every
time replace a nth symbol from beginning of string, replace a corresponding nth symbol from the end.
 Step-1: If symbol is 0 replace it by Y and move right, Go to state Q2 If symbol is 1 replace it by
X and move right, Go to state Q1
 Step-2: If symbol is 0 replace it by 0 and move right, remain on same state If symbol is 1 replace
it by 1 and move right, remain on same state ------------------------------------------------------------------- If symbol is
X replace it by X and move right, Go to state Q3 If symbol is Y replace it by Y and move right, Go to state Q3 If
symbol is $ replace it by $ and move right, Go to state Q3
 Step-3: If symbol is 1 replace it by X and move left, Go to state Q4 If symbol is 0 replace it by Y
and move left, Go to state Q5
 Step-4: If symbol is 1 replace it by 1 and move left If symbol is 0 replace it by 0 and move left
Remain on same state
 Step-5: If symbol is X replace it by X and move right If symbol is Y replace it by Y and move
right Go to state Q0
  Step-6: If symbol is X replace it by X and move right If symbol is Y replace it by Y and move
right Go to state Q6 ELSE Go to step 1
 Step-7: If symbol is X replace it by X and move right, Remain on same state If symbol is Y
replace it by Y and move right, Remain on same state If symbol is $ replace it by $ and move left, STRING IS
ACCEPTED, GO TO FINAL STATE Q7

Construct a Turing Machine for language L = {ww | w ∈ {0,1}}

Prerequisite - Turing Machine
The language L = {ww | w ∈ {0, 1}} tells that every string of 0's and 1's which is followed by itself falls under
this language. The logic for solving this problem can be divided into 2 parts:

1. Finding the mid point of the string

2. After we have found the mid point we match the symbols

Example - Lets understand it with the help of an example. Lets string 1 0 1 1 0 1, so w = 1 0 1 and string
is of form (ww).
The first thing that we do is to find the midpoint. For this, we convert 1 in the beginning into Y and move
right till the end of the string. Here we convert 1 into y.

Now our string would look like Y 0 1 1 0 Y. Now move left till, find a X or Y. When we do so, convert
the 0 or 1 right of it to X or Y respectively and then do the same on the right end. Now our string would
look like Y X 1 1 X Y. Thereafter, convert these 1's also and finally it would look like Y X Y Y X Y.

At this point, you have achieved the first objective which was to find the midpoint. Now convert all X
and Y on the left of midpoint into 0 and 1 respectively, so string becomes 1 0 1 Y X Y. Now, convert the
1 into Y and move right till, find Y in the beginning of the right part of the string and convert this Y into
a blank (denoted by B). Now string looks like Y 0 1 B X Y.

Similarly, apply this on 0 and x followed by 1 and Y. After this string looks like Y X Y B B B. Now that
you have no 0 and 1 and all X and Y on the right part of the string are converted into blanks so our string
will be accepted.

Assumption: We will replace 0 by X and 1 by Y.

Approach Used -
 The first thing is to find the midpoint of the string, convert a 0 or 1 from the beginning of the string into
X or Y respectively and a corresponding 0 or 1 into X or Y from the end of the string. After continuously
doing it a point is reached when all 0's and 1's have been converted into X and Y respectively. At this
point, you are on the midpoint of the string. So, our first objective is fulfilled.

Now, convert all X's and Y's on the left of the midpoint into 0's and 1's. At this point the first half the
string is in the form of 0 and 1. The second half of the string is in the form of X and Y.

Now, start from the beginning of the string. If you have a 0 then convert it into X and move right till
reaching the second half, here if we find X then convert it into a blank(B). Then traverse back till find an
X or a Y. We convert the 0 or 1 on the right of it into X or Y respectively and correspondingly, convert
its X or Y in the second half of string into a blank(B).

Keep doing this till converted all symbols on the left part of the string into X and Y and all symbols on
the right of string into blanks. If any one part is completely converted but still some symbols in the other
half are left unchanged then the string will not be accepted. If you did not find an X or Y in the second
half for a corresponding 0 or 1 respectively in the first half. Then also string will not be accepted.

Examples:

Input : 1 1 0 0 1 1 0 0

Output : Accepted

Input : 1 0 1 1 1 0 1

Output : Not accepted

Step-1:
If the symbol is 0 replace it by X and move right
If the symbol is 1 replace it by Y and move right,
Go to state Q1 and step 2
If the symbol is X replace it by X and move left or
If the symbol is Y replace it by Y and move left,
Go to state Q4 and step 5

Step-2:
If the symbol is 0 replace it by 0 and move right, remain on the same state
If the symbol is 1 replace it by 1 and move right, remain on the same state
If the symbol is X replace it by X and move left or
If the symbol is Y replace it by Y and move left or
If the symbol is $ replace it by $ and move left, Go to state Q2 and step 3
Step-3:
If symbol is 0 replace it by X and move left, or
If symbol is 1 replace it by Y and move left,
Go to state Q3 and step 4
Step-4:
If the symbol is 0 replace it by 0 and move left, remain on the same state
If the symbol is 1 replace it by 1 and move left, remain on the same state
---------------------------------------------
If the symbol is X replace it by X and move right or
If the symbol is Y replace it by Y and move right,
Go to state Q0 and step 1
Step-5:
If symbol is X replace it by X and move left or
If symbol is Y replace it by Y and move left
Go to state Q4 and step 6
Step-6:
If symbol is X replace it by 0 and move left, remain on same state
If symbol is Y replace it by 1 and move left, remain on same state
- - - - - - - - - -- - - - - - - - - - --
If symbol is $ replace it by $ and move right
Go to state Q4 and step 7
Step-7:
If symbol is 0 replace it by X and move right, go to state Q6 and step 8
If symbol is 1 replace it by Y and move right, go to state Q7 and step 9
- - - - - - - - - -- - - - - - - - - - --
If symbol is B replace it by B and move left, STRING ACCEPTED, GO TO FINAL STATE Q9
Step-8:
If symbol is 0 replace it by 0 and move right, remain on same state
If symbol is 1 replace it by 1 and move right, remain on same state
If symbol is B replace it by B and move right, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is X replace it by B and move left
Go to state Q8 and step 10
Step-9:

If symbol is 0 replace it by 0 and move right, remain on same state

If symbol is 1 replace it by 1 and move right, remain on same state
If symbol is B replace it by B and move right, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is Y replace it by B and move left
Go to state Q8 and step 10
Step-10:
If symbol is 0 replace it by 0 and move left, remain on same state
If symbol is 1 replace it by 1 and move left, remain on same state
If symbol is B replace it by B and move left, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is Y replace it by Y and move right or
If symbol is X replace it by X and move right
Go to state Q5 and step 7
 Decidable and Undecidable Problems in Theory of Computation
In the Theory of Computation, problems can be classified into decidable and undecidable categories based on
whether they can be solved using an algorithm. A decidable problem is one for which a solution can be found in
a finite amount of time, meaning there exists an algorithm that can always provide a correct answer. While
an undecidable problem is one where no algorithm can be constructed to solve the problem for all possible
inputs. In this article, we will discuss Decidable and Undecidable problems in detail.

What are Decidable Problems?

A problem is said to be Decidable if we can always construct a corresponding algorithm that can answer the
problem correctly. We can intuitively understand Decidable issues by considering a simple example. Suppose we
are asked to compute all the prime numbers in the range of 1000 to 2000. To find the solution to this problem,
we can easily construct an algorithm that can enumerate all the prime numbers in this range.
Now talking about Decidability in terms of a Turing machine, a problem is said to be a Decidable problem if
there exists a corresponding Turing machine that halts on every input with an answer- yes or no. It is also
important to know that these problems are termed Turing Decidable since a Turing machine always halts on
every input, accepting or rejecting it.

Semi Decidable Problems

Semi-decidable problems are those for which a Turing machine halts on the input accepted by it but it can either
halt or loop forever on the input which the Turing Machine rejects. Such problems are termed as Turing
Recognisable problems.

Example
We will now consider some few important Decidable problems:
 Are two regular languages L and M equivalent: We can easily check this by using Set
Difference operation. L-M =Null and M-L =Null. Hence (L-M) U (M-L) = Null, then L,M are equivalent.
 Membership of a CFL: We can always find whether a string exists in a given CFL by using an
algorithm based on dynamic programming.
 Emptiness of a CFL By checking the production rules of the CFL we can easily state whether
the language generates any strings or not.
What are Undecidable Problems?
The problems for which we can’t 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.
We can understand Undecidable Problems intuitively by considering Fermat's Theorem, a popular
Undecidable Problem which states that no three positive integers a, b and c for any n>2 can ever satisfy the
equation: a^n + b^n = c^n. If we feed this problem to a Turing machine to find such a solution which gives a
contradiction then a Turing Machine might run forever, to find the suitable values of n, a, b and c. But we are
always unsure whether a contradiction exists or not and hence we term this problem as an Undecidable
Problem.

Example
These are few important Undecidable Problems:
 Whether a CFG generates all the strings or not: As a Context Free Grammar (CFG) generates
infinite strings, we can’t ever reach up to the last string and hence it is Undecidable.
 Whether two CFG L and M equal: Since we cannot determine all the strings of any CFG, we can
predict that two CFG are equal or not.
 Ambiguity of CFG: There exist no algorithm which can check whether for the ambiguity of a
Context Free Language (CFL). We can only check if any particular string of the CFL generates two different
parse trees then the CFL is ambiguous.
 Is it possible to convert a given ambiguous CFG into corresponding non-ambiguous CFL: It is
also an Undecidable Problem as there doesn’t exist any algorithm for the conversion of an ambiguous CFL to
non-ambiguous CFL.
 Is a language Learning which is a CFL, regular: This is an Undecidable Problem as we can not
find from the production rules of the CFL whether it is regular or not.
The most well-known undecidable problem is the Halting Problem, which asks whether a given
program will stop running (halt) or continue running forever for a particular input. It has been proven that no
algorithm can solve this problem for all programs and inputs.
Some more Undecidable Problems related to Turing machine:
 Membership problem of a Turing Machine
 Finiteness of a Turing Machine
 Emptiness of a Turing Machine
 Whether the language accepted by Turing Machine is regular or CFL

Difference Between Decidable and Undecidable Problems

Aspect Decidable Problems Undecidable Problems

Problems that can be solved by an Problems where no algorithm can

Definition algorithm that always gives a correct give a solution for all possible
answer in a finite time. cases.

Always solvable using a step-by-step Cannot be solved for all inputs

Solvability
process (algorithm). using a single algorithm.

Algorithm There is an algorithm that works for No algorithm can solve the problem
 Aspect Decidable Problems Undecidable Problems

every input and always finishes with for every input.

an answer.

The algorithm stops (halts) and gives The algorithm might never stop for
Halting
an answer for every input. some inputs, or no algorithm exists.

Problems like checking if a number is Examples include the Halting

even or odd, or if a string belongs to a Problem, where you can’t always
Examples
regular language (like finding a match tell if a program will finish running
in a search). or run forever.

Decision There’s a clear method to always No guaranteed method exists to

Procedure reach a correct conclusion. solve the problem in every case.

May be complex but can always be Too complex to compute in general,

Complexity
computed. and no universal solution exists.

Useful in practical computing tasks Helps understand the limits of what

Applications like compiling code or searching for computers can do, showing what
text patterns. problems are beyond computation.
Undecidability and the Halting Problem

Introduction
Undecidability is a fundamental concept in computability theory, referring to problems that cannot be solved
by a Turing machine or any other computational model. The Halting Problem is a classic example of an
undecidable problem.

The Halting Problem

The Halting Problem is a decision problem that asks whether a given program will halt (stop running) for a
particular input. In other words, it tries to determine whether a program will run forever or eventually
terminate.

Formal Definition
Formally, the Halting Problem can be defined as follows:
Given a program P and an input x, determine whether P will halt when run on x.
More precisely, we can define a halting oracle H that takes a pair (P, x) as input and returns:

- 1 if P halts on x
- 0 if P does not halt on x

The Halting Problem is undecidable because there cannot exist a general algorithm (Turing machine) that can
determine, given an arbitrary program P and input x, whether P will halt on x.

Example
Consider a simple program that takes a positive integer n as input and runs an infinite loop if n is even, but
halts if n is odd:
def halting_problem(n):
if n % 2 == 0:
while True:
pass
else:
return

Given this program and an input n, the Halting Problem would ask whether the program will halt. However,
there is no general algorithm that can determine this for all possible inputs n.

Implications
The undecidability of the Halting Problem has significant implications for computer science:

- Limits of Computation: It highlights the fundamental limits of computation, demonstrating that there are
problems that cannot be solved by any algorithm.
- Verification and Validation: It shows that verifying the correctness of programs is a challenging task, and
there cannot exist a general algorithm to determine whether a program will halt or produce the correct output.
- Artificial Intelligence: The Halting Problem has implications for artificial intelligence, as it demonstrates
the limitations of automated reasoning and decision-making.

The undecidability of the Halting Problem is a profound result that has far-reaching implications for the theory
and practice of computation.

Recursively Enumerable (RE) and Non-RE Languages

Recursively Enumerable (RE) Languages

A language is recursively enumerable (RE) if there exists a Turing machine that can enumerate all strings in
the language. In other words, a language is RE if there is an algorithm that can generate all valid strings in the
language, although it may run forever.

Example of an RE Language
The language of all valid mathematical proofs is RE. A Turing machine can be designed to generate all
possible proofs by systematically exploring all possible combinations of axioms and inference rules.

Non-RE Languages
A language is non-RE if there is no Turing machine that can enumerate all strings in the language. In other
words, a language is non-RE if there is no algorithm that can generate all valid strings in the language.

Example of a Non-RE Language

The language of all Turing machines that do not halt on a given input is non-RE. This is because there is no
general algorithm that can determine whether a Turing machine will halt or run forever on a given input,
which is the Halting Problem.

Justification
The justification for these examples lies in the definitions of RE and non-RE languages:

- The language of all valid mathematical proofs is RE because we can systematically generate all possible
proofs using a Turing machine.
- The language of all Turing machines that do not halt on a given input is non-RE because the Halting Problem
is undecidable, and there is no general algorithm to determine whether a Turing machine will halt or run
forever.

These examples illustrate the difference between RE and non-RE languages, highlighting the limitations of
computation and the importance of understanding the theoretical foundations of computer science.

Decidable vs. Undecidable Problems

Decidable Problems
A decidable problem is a decision problem that can be solved by a Turing machine that halts on all inputs. In
other words, a decidable problem is one for which there exists an algorithm that can determine the answer (yes
or no) for any given input.

Undecidable Problems
An undecidable problem is a decision problem that cannot be solved by a Turing machine that halts on all
inputs. In other words, an undecidable problem is one for which there is no algorithm that can determine the
answer (yes or no) for any given input.

Examples of Undecidable Problems about Turing Machines

1. The Halting Problem: Given a Turing machine M and an input w, determine whether M will halt on w.

- Example: Consider a Turing machine M that takes a string w as input and runs an infinite loop if w
contains the substring "ab", but halts otherwise. The Halting Problem would ask whether M will halt on a
given input string w. There is no general algorithm to determine this.

2. The Emptiness Problem for Turing Machines: Given a Turing machine M, determine whether the
language accepted by M is empty (L(M) = ∅).

- Example: Consider a Turing machine M that accepts all strings that contain the substring "hello". The
Emptiness Problem would ask whether M accepts any strings. While this specific example can be solved, the
general problem is undecidable.

Implications
The existence of undecidable problems has significant implications for computer science:

- Limits of Computation: Undecidable problems highlight the fundamental limits of computation,

demonstrating that there are problems that cannot be solved by any algorithm.
- Verification and Validation: Undecidable problems show that verifying the correctness of programs or
Turing machines is a challenging task, and there cannot exist a general algorithm to determine certain
properties.

Understanding the difference between decidable and undecidable problems is crucial for appreciating the
theoretical foundations of computer science and the limitations of computation

Showing Undecidability using Reduction

Reduction Method
To show that a problem is undecidable using reduction, we can use the following approach:

1. Choose a known undecidable problem (e.g., the Halting Problem).

2. Reduce the known undecidable problem to the problem in question.
3. If the problem in question were decidable, then the known undecidable problem would also be decidable,
which is a contradiction.

Example: Reducing the Halting Problem to the Problem of Determining whether a Turing Machine Accepts a
Given String
Let's consider the problem of determining whether a Turing machine M accepts a given string w. We can
reduce the Halting Problem to this problem as follows:

1. Given a Turing machine M' and an input w', construct a new Turing machine M that simulates M' on w' and
accepts if M' halts on w'.
2. If M' halts on w', then M accepts w'.
3. If we had a decider for the problem of determining whether M accepts w', we could use it to solve the
Halting Problem for M' and w'.

Implications
If we assume that the problem of determining whether M accepts w' is decidable, then we can use this decider
to solve the Halting Problem, which is known to be undecidable. This contradiction implies that the problem
of determining whether M accepts w' is also undecidable.