CS303 Theory of Computation

R. Kabaleeshwaran

November 1, 2023

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 1 / 12

Outline

Recap - Closure Properties of CFL

▶ Substitution
▶ Union
▶ Concatenation
▶ Closure (∗, +)
Today
▶ Turing Machine
⋆ Introduction
⋆ History
⋆ Definition
⋆ Examples

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 2 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve
TM is essentially a finite automaton that has a single tape of infinite
length on which it may read and write data

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve
TM is essentially a finite automaton that has a single tape of infinite
length on which it may read and write data
TM is represented using its configuration precisely, (like the ID of a
PDA)

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve
TM is essentially a finite automaton that has a single tape of infinite
length on which it may read and write data
TM is represented using its configuration precisely, (like the ID of a
PDA)
▶ Instantaneous Description (ID) is an informal notation of how a PDA
“computes” a input string and make a decision that string is accepted
or rejected.

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve
TM is essentially a finite automaton that has a single tape of infinite
length on which it may read and write data
TM is represented using its configuration precisely, (like the ID of a
PDA)
▶ Instantaneous Description (ID) is an informal notation of how a PDA
“computes” a input string and make a decision that string is accepted
or rejected.
▶ ID is a triple (q, w , α), where q is the current state, w is the remaining
input and α is the top of a stack.

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Introduction to Turing Machines
Turing Machine (TM) - formalism for computers
TM is used to develop a theory of undecidable problems that is,
problems that no computer can solve
TM is essentially a finite automaton that has a single tape of infinite
length on which it may read and write data
TM is represented using its configuration precisely, (like the ID of a
PDA)
▶ Instantaneous Description (ID) is an informal notation of how a PDA
“computes” a input string and make a decision that string is accepted
or rejected.
▶ ID is a triple (q, w , α), where q is the current state, w is the remaining
input and α is the top of a stack.
Using the Turing machine notation, certain problems are proved
undecidable, that appear unrelated to programming
For e.g. Post Correspondence Problem, Halting Problem.

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 3 / 12

Historical Note

20th century - the mathematician D.Hilbert asked whether it was

possible to find an algorithm for determining the truth or falsehood of
any mathematical proposition
In 1931, K Godel published his famous incompleteness theorem
He constructed a formula in the predicate calculus applied to integers,
which asserted that the formula itself could be neither proved nor
disproved within the predicate calculus
In 1936, Alan M. Turing proposed the Turing machine as a model of
any possible computation
Alonzo Church created a method for defining functions called the
λ-calculus

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 4 / 12

The Turing Machine

The machine consists of a finite control, which can be in any of a

finite set of states
There is a tape divided into squares or cells each cell can hold any
one of a finite number of symbols
Initially, the input, which is a finite length string of symbols chosen
from the input alphabet, is placed on the tape
All other tape cells, extending infinitely to the left and right, initially
hold a special symbol called the blank
▶ The blank is a tape symbol, but not an input symbol
There is a tape head that is always positioned at one of the tape cells
The Turing machine is said to be scanning that cell
Initially, the tape head is at the leftmost cell that holds the input

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 5 / 12

The Turing Machine
A move of the Turing machine is a function of the state of the finite
control and the tape symbol scanned
In one move, the Turing machine will
1 Change state. The next state optionally may be the same as the
current state.
2 Write a tape symbol in the cell scanned.
This tape symbol replaces what ever symbol was in that cell.
3 Move the tape head left or right.
Formally, a move is required and do not allow the head to remain
stationary.

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 6 / 12

The Turing Machine
Formal notation we shall use for a Turing machine (TM) is similar to
that used for finite automata or PDA
A TM is described by the 7-tuple M = (Q, Σ, Γ, δ, q0 , B, F )
Q: The finite set of states of the finite control
Σ: The finite set of input symbols
Γ: The complete set of tape symbols; Σ is always a subset of Γ
δ: The transition function
The arguments of δ(q, X ) are a state q and a tape symbol X. The
value of δ(q, X ), if defined, is a triple (p, Y , D), where
p is the next state, in Q.
Y is the symbol, in Γ written in the cell being scanned, replacing whatever
symbol was there.
D is the direction, either L or R, standing for left or right respectively, and
telling us the direction in which the head moves
q0 : The start state
B: The blank symbol that appears initially in all but the finite number of
initial cells that hold input symbols.
This symbol is in Γ but not in Σ
F: The set of final or accepting states, a subset of Q
Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 7 / 12
Example 1

A Turing machine to accept L1 = {0n 1n | n ≥ 1} is

M1 = {{q0 , q1 , q2 , q3 , q4 }, {0, 1}, {0, 1, X , Y , B}, δ, q0 , B, {q4 }}

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 8 / 12

Example 2

A Turing machine to accept L2 = {ai b j c k | i, j, k ≥ 1, i = j + k} is

M2 =
{{q0 , q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 }, {a, b, c}, {a, b, c, X , Y , Z , B}, δ, q0 , B, {q8 }}
Idea
Matching a and b:
▶ M2 start reading ‘a’ and change it to X and moves to right
▶ When it sees ‘b’, M2 change it to Y and moves left
Matching a and c: Same as above, except that M2 changes c into Z
and move left.
M2 accepts when no. of a’s = no. of b’s and c’s.

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 9 / 12

Example 3

A Turing machine which accepts the set of all palindromes over {0, 1}∗

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 10 / 12

Example 3 - Transition diagram
A Turing machine which accepts the set of all palindromes over {0, 1}∗

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 11 / 12

Dr. R. Kabaleesh CS303 Theory of Computation 31 October 2023 12 / 12