Theory of computation

Lecture 6: Turing Machines

Adnane Saoud

Tuesday, November 14, 2023

1
 Summary of lectures 1-5

Lectures 1-5
§ Automata and regular languages
§ Context free grammars and Pushdown automatas

Lecture 6
§ Turing machines
§ Recognizers and deciders
§ Equivalence of variants of the Turing machine model
§ Church-Turing Thesis

2
Turing machines

3
 Turing Machines (TMs)

head
a b a b b ˽ ˽ ...
Finite
control read/write input tape

1) Head can read and write

2) Head is two way (can move left or right)
3) Tape is infinite (to the right)
4) Infinitely many blanks “˽“ follow input
5) Can accept or reject any time (not only at end of input)

4
 TM – example

TM recognizing 𝐵 = a! b! c! 𝑘 ≥ 0
1) Scan right until ˽ while checking if input is in a∗b∗c∗, reject if not.
2) Return head to left end.
3) Scan right, crossing off single a, b, and c.
4) If the last one of each symbol, accept.
5) If the last one of some symbol but not others, reject.
6) If all symbols remain, return to left end and repeat from (3).
head
input tape
Finite a a a b b b c c c ˽ ˽
control

accept

5
 TM – example

Exercise:
How do we get the effect of “crossing off” with a Turing machine?
a) We add that feature to the model.
b) We use a tape alphabet Γ = {a, b, c, a, b, c, ˽ }.
c) All Turing machines come with an eraser.

6
 TM – Formal Definition

Definition: A Turing Machine (TM) is a 7-tuple (𝑄, Σ, Γ, 𝛿, 𝑞", 𝑞acc , 𝑞rej)

Σ input alphabet
Γ tape alphabet (Σ ⊆ Γ)
𝛿: Q×Γ → 𝑄×Γ× {L, R} (L = Left, R = Right)
𝛿 𝑞, a = (𝑟, b, R)

On input 𝑤 a TM 𝑀 may halt (enter 𝑞acc or 𝑞rej)

or 𝑀 may run forever (“loop”).

So 𝑀 has 3 possible outcomes for each input 𝑤:

1. Accept 𝑤 (enter 𝑞acc )
2. Reject 𝑤 by halting (enter 𝑞rej )
3. Reject 𝑤 by looping (running forever)

7
 TM – Example

TM recognizing
1. Zig-zag across the tape to corresponding positions on either side of the #
symbol to check whether these positions contain the same symbol. If they do
not, or if no # is found, reject. Cross off symbols as they are checked to keep
track of which symbols correspond.
2. When all symbols to the left of the # have been crossed off, check for any
remaining symbols to the right of the #. If any symbols remain, reject; otherwise,
accept.

8
TM – Example

9
 TM Recognizers and Deciders

Let 𝑀 be a TM. Then 𝐿 𝑀 = 𝑤 𝑀

accepts 𝑤}.
Say that 𝑀 recognizes 𝐴 if 𝐴 = 𝐿(𝑀).
Definition: 𝐴 is Turing-recognizable if T-recognizable
𝐴 = 𝐿(𝑀) for some TM 𝑀.

Definition: TM 𝑀 is a decider if 𝑀 halts

T-decidable
on all inputs.
CFLs
Say that 𝑀 decides 𝐴 if 𝐴 = 𝐿(𝑀) and
𝑀 is a decider.
regular
Definition: 𝐴 is Turing-decidable if 𝐴 =
𝐿(𝑀) for some TM decider 𝑀.
10
Variants of Turing
machines

11
 Multi-tape Turing machines

input tape
Finite
control
} work tapes, initially blank

...
all tapes read/write

Theorem: 𝐴 is T-recognizable iff some multi-tape TM recognizes 𝐴

Proof: (→) immediate. (←) convert multi-tape to single tape:

12
 Multi-tape Turing machines

a a b b a ˽ ˽ ...
multi-tape 𝑀 1 0 1 ˽ ...

...
c c c a ˽ ...

single tape 𝑆 a a b b a # 1 0 1 # … # c c c a ˽ ˽

𝑆 simulates 𝑀 by storing the contents of multiple tapes on a single tape in “blocks”.

Record head positions with dotted symbols.
Some details of 𝑆:
1) To simulate each of 𝑀’s steps
a. Scan entire tape to find dotted symbols.
b. Scan again to update according to 𝑀’s 𝛿.
c. Shift to add room as needed.
2) Accept/reject if 𝑀 does.

13
 Nondeterministic Turing machines

A Nondeterministic TM (NTM) is similar to a Deterministic TM

except for its transition function 𝛿: Q×Γ → 𝒫( 𝑄×Γ× {L, R} ).
Theorem: 𝐴 is T-recognizable iff some NTM recognizes 𝐴
NTM
𝑁 a a b a ˽ ˽

Nondeterministic computation tree

for 𝑁 on input 𝑤.
...

accept
14
Church-Turing Thesis

15
 Church-Turing Thesis ~1936

Algorithm

Intuitive

• Algorithm: collection of simple instructions for carrying out some task

• Algorithms play an important role in the history of mathematics.

Ancient mathematical literature contains descriptions of algorithms for
a variety of tasks, such as finding prime numbers and greatest common
divisors.
• Even though algorithms have had a long history in mathematics, the
notion of algorithm itself was not defined precisely until the twentieth
century. Before that, mathematicians had an intuitive notion of what
algorithms were.
16
 Church-Turing Thesis ~1936

Algorithm = Turing
machine
Intuitive Formal

Instead of Turing machines,

can use any other “reasonable” model
Alonzo Church of unrestricted computation:
𝜆-calculus, random access machine, Alan Turing
1903–1995
1912–1954
your favorite programming language, …

17
 Hilbert’s 10th Problem
In 1900 David Hilbert posed 23 problems
#10) Give an algorithm for solving Diophantine equations.

Diophantine equations:
Equations of polynomials where solutions must be integers.
Example: 3𝑥 " − 2𝑥𝑦 − 𝑦 " 𝑧 = 7 solution: 𝑥 = 1, 𝑦 = 2, 𝑧 = −2

Let 𝐷 = 𝑝 polynomial 𝑝 𝑥# , 𝑥" , … , 𝑥$ = 0 has a solution in integers)

Hilbert’s 10th problem: Give an algorithm to decide 𝐷.
Matiyasevich proved in 1970: 𝐷 is not decidable.

Note: 𝐷 is T-recognizable.

18
 Hilbert’s 10th Problem

Exercise:
Consider the set

Here is a TM that recognizes D1:

If p has an integral root, M1 eventually will find it and accept. If p does not have an
integral root, M1 will run forever. For the multivariable case, we can present a similar
TM M that recognizes D. Here, M goes through all possible settings of its variables to
integral values.
19
Summary

20
 Summary

1. Turing machines
2. Recognizers and deciders
3. Equivalence of variants of the Turing machine model
4. Church-Turing Thesis

21