Turing Machines and

Algorithms
Sources of slides (with additions and modifications) :
[Link] by Shachar Lovett
[Link] by Dr. Gary Weiss

1
 What is an Algorithm?
n How would you describe an algorithm?
n An algorithm is a finite sequence of precise
instructions for performing a computation or
for solving a problem
n A procedure or recipe
n Algorithms abound in mathematics and have for
thousands of years
n Ancient algorithms for finding prime numbers and
greatest common divisors

2
 Hilbert’s Problems
n In 1900 David Hilbert proposed 23 mathematical
problems for the next century
n Hilbert’s 10th problem:
n Devise an algorithm for determining if a polynomial has an
integral root i.e., polynomial will evaluate to 0 with this root.
n Instead of using the word algorithm, Hilbert said “a process
by which it can be determined by a finite number of
operations”
n For example, 6x3yz2 + 3xy2 – x3 -10 has integral root x=5,
y=3, and z=0.
n Hilbert assumed that a method exists to find integral roots.
n He was wrong 3
 Church-Turing Thesis
n It could not really be proved that an algorithm did not
exist without a clear definition of what an algorithm is.
n Definition of an Algorithm was provided in 1936 in
n Alonzo Church’s λ-calculus and
n Alan Turing’s Turing Machines
n The two definitions (λ-calculus and Turing
Machines) were shown to be equivalent

4
 Church-Turing Thesis
n Connection between the informal notion of an
algorithm and the precise definition is called the
Church-Turing thesis
n The intuitive notion of algorithms equals Turing
machine algorithms
n In 1970 it was shown that no algorithm exists for
testing whether a polynomial has integral roots
n It is important that we have an answer now.

5
 Church-Turing Thesis

Anything that can be computed by algorithm

(in our intuitive sense of the term
“algorithm”)
can be computed by a Turing Machine.
 More on Hilbert’s 10th Problem
n Hilbert essentially asked if the language D is decidable
(not just Turing-recognizable)
n D = {p| p is a polynomial with an integral root}
n Can you come up with a procedure to answer this question?
n Try all possible integers. Start at 0 and loop through: 0, 1, -1, 2, -2, …
n For multivariate case, just lots of combinations
n Is it Turing decidable, Turing recognizable, or neither?
n What is the problem here?
n May never terminate
n You will never know whether it will not terminate or will accept shortly
n Therefore, it is Turing-recognizable but not decidable

7
 More on Hilbert’s 10th Problem
n For univariate case, there is actually an upper
bound on the root of the polynomial
n So in this case there is an algorithm and the problem is
decidable
n For multivariate cases, it has been proven that it is not
decidable
n Think about how significant it is that you can
prove something cannot be computed
n Doesn’t mean that you are not smart or clever enough

8
 More on Hilbert’s 10th Problem
n D = {p| p is a polynomial with an integral root}
n D1 = {p| p is a polynomial over x with an integral root}
n A TM M1 that recognizes D1
n M1 = “On input <p>: where p is a polynomial over the variable x.
n Evaluate p with x set successively to the values 0, 1, −1, 2, −2, 3,−3, . . . .
If at any point the polynomial evaluates to 0, accept.
n If p has an integral root, M1 will find it and accept. If p does not
have an integral root, M1 will run forever.
n M1is a recognizer but not a decider.
n M1 can be converted to a decider for D1 because
n we can calculate bounds within which the roots of a single variable
polynomial must lie and restrict the search to these bounds.
9
 Turing machine merely
serves as a precise model for
the definition of algorithm.

10
 Describing Turing Machines
n A Turing Machine may be described at different levels of
details
1. Formal description that spells out in full the
Turing machine’s states, transition function, and so
on.
2. Implementation description uses English prose to
describe the way the Turing machine moves its head
and the way it stores data on its tape.
3. High-level description, wherein we use English
prose to describe an algorithm, ignoring the
implementation details. 11
Turing Machine: Formal Description
2n
A= {0 |n≥0}

12
Turing Machine: Implementation Description
2n
A = {0 |n≥0}

13
 Turing Machine: High-level Description

Let B be the language of all strings representing graphs that are

connected (i.e., any node can be reached by any other).
B = {<G>| G is a connected undirected graph}.

14
Hierarchy of Classes of Languages

Turing recognizable languages

Turing decidable languages

Context-free languages

Regular languages

15
 Closure
Theorem: The class of decidable languages over
fixed alphabet Σ is closed under union.

Proof: Let L1 and L2 be languages over Σ and

suppose M1 and M2 are TMs deciding these
languages. We will define a new TM, M, via a
high-level description. We will then show that
L(M) = L1 U L2 and that M always halts.
 Closure
Theorem: The class of decidable languages over fixed alphabet
Σ is closed under union.

Proof: Let L1 and L2 be languages and suppose M1 and M2 are

TMs deciding these languages. Construct the TM M as
"On input w,
[Link] M1 on input w. If M1 accepts w, accept. Otherwise, go
to step 2.
[Link] M2 on input w. If M2 accepts w, accept. Otherwise,
reject.”

L(M) = L1 U L2 and M is a decider.

 Closure
The class of Turing The class of Turing
decidable languages is recognizable languages is
closed under closed under
n Union nUnion

n Concatenation nConcatenation

n Intersection nIntersection

n Star nStar

n Complement
 References

• Introduction to the Theory of Computation 3rd

Edition by Michael Sipser
• Introduction to Automata, Theory, Languages
and Computation (3rd edition) by John E.
Hopcroft, Rakeev Motwani, Jeffrey D. Ullman
• All images taken from the book Introduction to
the Theory of Computation 3rd Edition by
Michael Sipser