Turing Machines

(1)

CS310 : Automata Theory 2020

Lecture 26: Turing Machines and Computability

Instructor: S. Akshay

IITB, India

Spring 2020

(2)

Topics covered till now in this course

I. Finite state automata

1. Deterministic finite-state automata (DFA)

2. Non-determinism, the subset construction, -transitions.

3. Regular expressions and equivalence with DFA 4. Regular languages and their properties

5. Pumping lemma

6. Myhill-Nerode and minimization II. Finite state automata with a stack

1. Pushdown automata (PDA)

2. Context-free grammars (CFG) and Parse trees 3. Equivalence of PDA and CFG, deterministic PDA

(3)

This lecture

Turing Machines

In this lecture we will cover

I Definition of Turing machines, examples of Turing machines I Configurations of Turing Machines

I Language accepted by a Turing Machine I Turing recognizability and decidability I The Church-Turing thesis and Alan Turing

Reading Material

I Section 8.2, Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullman

I Chapter 3, Introduction to the Theory of Computation, Michael Sipser

(4)

This lecture

Turing Machines

In this lecture we will cover

I Definition of Turing machines, examples of Turing machines I Configurations of Turing Machines

I Language accepted by a Turing Machine I Turing recognizability and decidability I The Church-Turing thesis and Alan Turing

Reading Material

I Section 8.2, Introduction to Automata Theory, Languages and

(5)

From finite to infinite memory

Finite instruction machine with finite memory (Finite State Automata)

start S C

no coin coin

ready dispense not ready

Finite instruction machine with unbounded memory (Turing machine)

. . . b

a . . . t

P Q

b/a,R

b/a,R a/a,L

a/a,L

(6)

From NFA and PDA to Turing Machines

. . . b

a . . . t

P Q

b/a,R

b/a,R a/a,L

a/a,L

1. PDA are obtained from NFA by adding a stack

2. Turing machines are obtained from NFA by adding an infinite tape.

3. A Turing machine can both write on the tape and read from it. 4. The read-write head can move both to left and right.

5. Initially all cells have special blank symbol, except where input is written. 6. Once accept/reject states are reached, computation terminates.

(7)

From NFA and PDA to Turing Machines

. . . b

a . . . t

P Q

b/a,R

b/a,R a/a,L

a/a,L

3. A Turing machine can both write on the tape and read from it.

4. The read-write head can move both to left and right.

5. Initially all cells have special blank symbol, except where input is written. 6. Once accept/reject states are reached, computation terminates.

(8)

From NFA and PDA to Turing Machines

. . . b

a . . . t

P Q

b/a,R

b/a,R a/a,L

a/a,L

3. A Turing machine can both write on the tape and read from it.

4. The read-write head can move both to left and right.

(9)

Example

Consider the language B ={w#w |w ∈ {0,1}^∗}.

I Is it regular?

I How does one check if a given (really long) string is of this form?

How would you solve this if this was a programming assignment? How can we use a Turing machine to accept this language:

1. Scan the input once to make sure it does contain a single #. Else reject. 2. Repeatedly do: Mark the first “unmarked” symbol from beginning and

zig-zag across the tape to its corresponding position on the other side of

# symbol to check if it is the same. If not, reject.

3. Stop when there are no unmarked symbols remaining to the left of #. If there are still symbols left on right, then reject. Else accept.

In general, we use the finite control to process the symbols that are being read on tape. How does one formalize this?

(10)

Example

I Is it regular?

How would you solve this if this was a programming assignment?

How can we use a Turing machine to accept this language:

(11)

Example

I Is it regular?

(12)

Example

I Is it regular?

1. Scan the input once to make sure it does contain a single #. Else reject.

2. Repeatedly do: Mark the first “unmarked” symbol from beginning and zig-zag across the tape to its corresponding position on the other side of

(13)

Example

I Is it regular?

(14)

Example

I Is it regular?

(15)

Example

I Is it regular?

(16)

Formal definition of a Turing Machine

Definition

A Turing Machine is a 7-tuple (Q,Σ,Γ, δ,q₀,q_acc,q_rej) where 1. Q is a finite set ofstates,

2. Σ is afinite input alphabet,

3. Γ is afinite tape alphabet wheret ∈Γ and Σ⊆Γ, 4. q₀ is the startstate,

5. qacc is the acceptstate, 6. qrej is the rejectstate,

7. δ :Q×Γ→Q×Γ× {L,R}is the transition function.

For aq ∈Q,a∈Γ if δ(q,a) = (q⁰,b,L), then I q⁰ is the new state of the machine,

I b is the letter which replacesaon the tape, I the head moves to Left of the current position.

(17)

Formal definition of a Turing Machine

Definition

A Turing Machine is a 7-tuple (Q,Σ,Γ, δ,q₀,q_acc,q_rej) where 1. Q is a finite set ofstates,

2. Σ is afinite input alphabet,

3. Γ is afinite tape alphabet wheret ∈Γ and Σ⊆Γ, 4. q₀ is the startstate,

5. qacc is the acceptstate, 6. qrej is the rejectstate,

7. δ :Q×Γ→Q×Γ× {L,R}is the transition function.

For aq ∈Q,a∈Γ if δ(q,a) = (q⁰,b,L), then I q⁰ is the new state of the machine,

I b is the letter which replacesaon the tape, I the head moves to Left of the current position.

(18)

Example: TM for B = {w #w | w ∈ {0, 1}

^∗

}?

From Sipser’s book: What isQ,Σ,Γ, δ, etc.?

(This picture is taken from Sipser’s book.)

(19)

Example: TM for B = {w #w | w ∈ {0, 1}

^∗

}?

From Sipser’s book: What is Q,Σ,Γ, δ, etc.?

(This picture is taken from Sipser’s book.)

(20)

Configurations of a Turing machine

A configuration is a snapshot of the system during computation.

For a Turing machine, this is described by:

current state,tape contentsand current head location.

Notation: C =uqv

where,uv is the tape content, current state isq and head is at start of v We defineC₁ yields C₂ if the TM can move fromC₁ toC₂ in one step:

I left move: u a q_i b v yields u q_j a c v ifδ(q_i,b) = (q_j,c,L) I right move: u a qi b v yields u a c qj v ifδ(qi,b) = (qj,c,R)

I left-end: qi b v yields (1)qj c v if transition is left moving or (2) c qj v if it is right moving

I right-end: assume thatu a qi is the same asu a qi tas tape has blanks to the right.

(21)

Configurations of a Turing machine

For a Turing machine, this is described by: current state,tape contentsand current head location.

Notation: C =uqv

where,uv is the tape content, current state isq and head is at start of v We defineC₁ yields C₂ if the TM can move fromC₁ toC₂ in one step:

(22)

Configurations of a Turing machine

Notation: C =uqv

where, uv is the tape content, current state is q and head is at start of v

We defineC₁ yields C₂ if the TM can move fromC₁ toC₂ in one step: I left move: u a q_i b v yields u q_j a c v ifδ(q_i,b) = (q_j,c,L) I right move: u a qi b v yields u a c qj v ifδ(qi,b) = (qj,c,R)

(23)

Configurations of a Turing machine

Notation: C =uqv

where, uv is the tape content, current state is q and head is at start of v We define C₁ yields C₂ if the TM can move fromC₁ toC₂ in one step:

(24)

Configurations of a Turing machine

Notation: C =uqv

(25)

Configurations of a Turing machine

Notation: C =uqv

I left-end: qi b v yields (1)qj c v if transition is left moving or (2)c qj v if it is right moving

(26)

Computation of a Turing Machine

I We define start (q0,w), accepting (∗q_acc∗), rejecting (∗q_rej∗) and halting configurations.

I A Turing Machine computation on a given input may not halt!

I A TM M acceptsinput word w if there exists a sequence of configurationsC₁,C₂, . . . ,C_k (called a run) such that

I C1is the start configuration I eachCi yieldsCi+1

I Ck is an accepting configuration

I Language of TMM, denotedL(M), is the set of strings accepted by it.

(27)

Computation of a Turing Machine

I A TM M acceptsinput word w if there exists a sequence of configurationsC₁,C₂, . . . ,C_k (called a run) such that

I C1is the start configuration I eachCi yieldsCi+1

(28)

Computation of a Turing Machine

I A TMM acceptsinput word w if there exists a sequence of configurationsC₁,C₂, . . . ,C_k (called a run) such that

I C1 is the start configuration I eachCi yieldsCi+1

(29)

Computation of a Turing Machine

I A TMM acceptsinput word w if there exists a sequence of configurationsC₁,C₂, . . . ,C_k (called a run) such that

I C1 is the start configuration I eachCi yieldsCi+1

(30)

Turing recognizable and decidable languages

Turing recognizable or Recursively enumerable (r.e)

A language is Turing recognizable or r.eif there is a Turing machine accepting it.

Turing decidable or recursive

A language isdecidable(or recursive) if there is a Turing machine accepting it, which has the additional property that it halts on all possible inputs.

Every decidable language is Turing recognizable, but is the converse true?

(31)

Turing recognizable and decidable languages

A language is decidable(or recursive) if there is a Turing machine accepting it, which has the additional property that it halts on all possible inputs.

(32)

Turing recognizable and decidable languages

A language is decidable(or recursive) if there is a Turing machine accepting it, which has the additional property that it halts on all possible inputs.

(33)

Another example of a Turing Machine

A TM as a computer of integer functions

I Compute max{m−n,0}: construct TMM that starts with 0^m10ⁿ and halts with 0^max{m−n,0} on tape.

(34)

Another example of a Turing Machine

Same as defining B ={a^mbⁿc^max{m−n,0} |m,n≥0} and asked for a TM which accepts language B.

(35)

Another example of a Turing Machine

I M repeatedly replaces leading 0 by blank, then searches right for a 1 followed by 0 and changes 0 to 1.

I Then, M moves left until it encounters a blank and repeats this cycle.

(36)

Another example of a Turing Machine

I The repetition ends if

1. searching right for 0,M encounters a blank.

I Then alln0’s in 0^m10ⁿhave been changed to 1 andn+ 1 ofm0’s changed to blank. M replacesn+ 1 1’s by a 0 andnblanks leavingm−n 0’s on the tape.

(37)

Another example of a Turing Machine

I The repetition ends if

1. searching right for 0,M encounters a blank.

I Then alln0’s in 0^m10ⁿhave been changed to 1 andn+ 1 ofm0’s changed to blank. M replacesn+ 1 1’s by a 0 andnblanks leavingm−n 0’s on the tape.

2. beginning the cycle,M cannot find a 0 to change to a blank, because first m0’s have already been changed.

I Thenn≥m, so max{m−n,0}= 0. M replaces remaining 1’s, 0’s by blanks.

(38)

More examples/exercises

Exercises

1. C ={0²ⁿ |n ≥0}, i.e., all strings of 0’s whose length is a power of 2.

I Give a high level description of a TM that acceptsC. I Give the formal TM construction and state-diagram.

2. D ={aⁱb^jc^k |i∗j =k andi,j,k ≥1}. Give a (high level description of) a TM that accepts D.

(39)

More examples/exercises

Exercises

1. C ={0²ⁿ |n ≥0}, i.e., all strings of 0’s whose length is a power of 2.

I Give a high level description of a TM that acceptsC. I Give the formal TM construction and state-diagram.

2. D ={aⁱb^jc^k |i∗j =k andi,j,k ≥1}. Give a (high level description of) a TM that accepts D.

(40)

Why Turing Machines?

I Robust model of computation

I Equivalence with other such models of computation, with reasonable assumptions (e.g., only finite amount of work is possible in 1 step).

I Thus, though there are several computational models, the class of algorithms (or procedures) they describe is the same.

I Can do everything a computer can do and vice versa. But takes a lot more time. Is not practical and indeed its not what is implemented in today’s computer. After all who wants to write 100 lines to do subtraction or check something that a 4-year old can do?

I So then again, why Turing? Why is the top-most nobel-equivalent award in computer science called Turing award and not Bill Gates award?

(41)

Why Turing Machines?

(42)

Why Turing Machines?

(43)

Why Turing Machines?

(44)

Turing Machines: a lesson from history

Hilbert’s problems

I In 1900, David Hilbert listed out 23 problems as challenges for 20th century at the Int. Cong. of Mathematicians in Paris.

I 10th problem: Devise an algorithm (a process doable using a finite no.

of operations) to test if a given polynomial has integral roots.

I Now we know that no such algorithm exists. But how to prove this without a mathematical definition of an algorithm?

(45)

Turing Machines: a lesson from history

Hilbert’s problems

I In 1900, David Hilbert listed out 23 problems as challenges for 20th century at the Int. Cong. of Mathematicians in Paris.

I 10th problem: Devise an algorithm (a process doable using a finite no.

of operations) to test if a given polynomial has integral roots.

I Now we know that no such algorithm exists. But how to prove this without a mathematical definition of an algorithm?

(46)

The Entscheidungsproblem

A challenge... in 1928

Is there analgorithmto decide whether any given statement is provable from the axioms using the rules of logic?

(47)

The Church-Turing Thesis

Alonso Church

(1903–1995) Alan Turing

(1912–1954)

(48)

The Church-Turing Thesis

Alonso Church (1903–1995)

Alan Turing (1912–1954)

(49)

The Church-Turing Thesis

I The Church-Turing Thesis provides the definition of algorithm necessary to resolve Hilbert’s tenth problem.

The Church-Turing Thesis

Our intuitive understanding of algorithms coincides with Turing machine algorithms.

I Thus, Turing machines capture our intuitive idea of computation. I Indeed, we are more interested in algorithms themselves. Once we

believe that TMs precisely capture algorithms, we will shift our focus to algorithms rather than low-level descriptions of TMs.

(50)

The Church-Turing Thesis

I The Church-Turing Thesis provides the definition of algorithm necessary to resolve Hilbert’s tenth problem.

The Church-Turing Thesis

Our intuitive understanding of algorithms coincides with Turing machine algorithms.

I Thus, Turing machines capture our intuitive idea of computation.

I Indeed, we are more interested in algorithms themselves. Once we believe that TMs precisely capture algorithms, we will shift our focus to algorithms rather than low-level descriptions of TMs.

(51)

More on the Church-Turing Thesis

Lambda Calculus

I In 1936, Church introduced Lambda Calculus as a formal description of all computable functions.

I Independently, Turing had introduced his A-machines in 1936 too.

I Turing also showed that his A-machines were equivalent to Lambda Calculus of Church.

I So, can a Turing machine do everything? In other words are there algorithms to solve every question. Godel’s incompleteness result asserts otherwise.

I If there is TM solving a problem, does there exist an equivalent TM that halts?

(52)

What else did Turing do?

I Alan Turing characterized computable functions by building a machine.

Though theoretical this gave rise to the idea of computers.

I But Turing also worked on ideas and concepts that later made profound impact in AI and cryptography.

I “Father” of modern computers and computer science.

(53)

What else did Turing do?

I Alan Turing characterized computable functions by building a machine.

Though theoretical this gave rise to the idea of computers.

I But Turing also worked on ideas and concepts that later made profound impact in AI and cryptography.

I “Father” of modern computers and computer science.