Chapter 9

Turing Machines, 11/12/03

  • Problem:Simple languages like {anbncn} and {ww} are not context-free.

Goal:How to define a family of languages which is a super set of CFL’s and contains examples such as these:

  • Define an automaton more powerful than an NPDA

Q:What is the ultimate in automatons?

What is the limit of computation?

  • This leads to the concept of the Turing machine and Turing thesis:

Which says that any computational process which can be done on a “general purpose” digital machine could be done on a Turing machine

  • Definition 9.1

A Turing machine is defined by:

M = (Q, ∑, , , q0, □, F)

Where:

Q = Set of internal states of control unit

∑ = Input alphabet (finite)

г = Tape alphabet (finite)

 = Transition function (see below)

□  г is a “special” blank symbol

q0 Q is initial state

F  Q set of final states

: QxQxx {L,R}

-A partial function (domain  Q x )

∑  – {□}By definition

  • How a TM works:

 maps the current state of C.U. and the current symbol being read from the tape (under the R/W head)

To

New state of C.U., a new tape symbol which overwrites the old one, and a “move symbol” which moves the head left or right (after writing the tape symbol)

Ex. 9.1:

A move (q0,a) = (q1, d, R)

TM is derministic,  maps uniquely to a new state

Def. Halt / Halt State:

A TM is said to halt whenever it reaches a configuration for which  is not defined.

  • Possible since a partial function
  • No transitions defined for qf F

Halts whenever it enters a final state

  • See Ex. 9.2

Definition: Infinite loop

A TM program which does not halt

See Ex 9.3 … infinite loop

  • Standard Turing machine

-Unbounded tape in both directions allowing any number of L/R moves

-Deterministic  – at most one move for each configuration

-No special “input file”

Tape has specific content at initial time.

May consider this as input

No output – but contents of tape may be viewed as output

  • Instantaneous description

x1 q x2

Assume contents of tape delimited by all blanks on either side when in state q

x1 is symbols to left of head

x2 is symbols to right of head

1st symbol of x under head
or

a1 a2 . . . ak-1 q ak ak+1 . . . an

Definition. of “├” :

If(q1, c) = (q2, e, R)

Then the move

abq1cd ├ abeq2d

is made

Obvious extensions:├*├m

See Ex. 9.5 p. 227 3rd ed.

Formal Def. 9.2 p.228 3rd ed. (a “move”)

M = (Q, ∑, , , q0, □, F) is a TM

Any string a1…ak-1q1akak+1…an

with an and q1 Q

is an instantaneous description of M

A move:

a1…ak-1q1akak+1…an ├ a1…ak-1bq1ak+1…an

is possible iff

(q1,ak) = (q2, b, R)

Simlarly:

a1…ak-1q1akak+1…an ├ a1…q2ak-1bak+1…an

is possible iff
(q1,ak) = (q2, b, L)

Definition of HALTING:

M is said to halt from some initial configuration, x1qnx2

If: x1qnx2 ├* y1qjay2 (goes to a configuration for which  is not defined)

For any qj and a for which (qj,a) is undefined

This is called a computation

If it never halts:x1qx2 ├* 

Turing Machines as a Language Accepter

Definition9.3

Let M = (Q, ∑, , , q0, □, F)be a TM

Then language accepted by M is:

L(M) = {w  ∑+, : q0w ├* x1qfx2 for some qf  F, x1,x2*}

“□” is a delimiter

Blanks excluded from input

All input restricted to well defined region of tape, bracketed by blanks on left and right.

What happens if W  L(M)

(1)Machine halts in nonfinal state
or

(2)Machine enters  loop

Any string for which M does not halt

Is NOT in L(M)

See examples 9.6, L(00*)

See examples 9.6, L = {anbn : n 1} Illustrates a basic technique.

Turing Machines as Transducers

(TM’s as models of real computers)

  • Look beyond the language accepter aspect of a TM.
  • Primary purpose of a computer is to transform input into output  a transducer

How could we interpret a TM as a transducer?

Interpretation:

Input:All non blank symbols on tape

Output: (At conclusion of computation) whatever is then on the tape

View a TM as a transducer which is an implementation of a function f defined by:

ŵ = f(w)

provided that

q0w ├*m qfŵ

for some final state qf

More formally:
Defintion 9.4

A function f with a domain D is said to be “turing-computable” or “computable” iff,  some TM

M = (Q, ∑, , , q0, □, F)

s.t.

q0w ├*m qf f(w), qi f

 w D.(D , f(w) )

TM Building Block Approach

  • Want a high level programming approach for a TM

Use pseudocode

or

Combination of high level diagrams

Ex:f(x,y)= x + yx ≥ y

= 0x < y

Q:How does a TM “fire off” another?

A:It’s a notational problem

By proper naming of states (to make them all unique)

We have:

Compare TM (C)┌> ├* qAfw(x+y)0 (add path)

Qc0 w(x)0w(y)├* qA0 w(x)0w(y) if x ≥ y

├* qE0 w(x)0w(y) if x < y

└> ├*qEf0 (erase path)

  • Use of pseudocode (macroinstructions)

Ex.If “a” then qj else qk only a (conditional) state change, nothing else done

(qi, a) = (qj0, a, R),  qi Q

(qj0, c) = (qj, c, L),  c  … multiple rules, one for each c since c is arbitrary

(qi, b) = (qk0, b, R),  qi  Q, b  – {a} … multiple rules, one for each b

(qk0, c) = (qk, c, L),  c 

Perhaps a compiler would expand the above code from some “high level” rule.

Also the definition of a “don’t care” for second argument of  may be useful.

  • Use of subroutines

A work space TB work space

- Use T to pass parameters from A to B and to leave results.

- Encode in T the “old state”, so on return we could restore the state.

- To reset head on return, maybe leave a special mark (x) where it was and then record the mark along with the value it should be replaced with in T.

Turing’s Thesis

  • Any computation that can be “carried out” by “mechanical means” can be performed by some turing machine.
  • Sometimes this is what is used to define a mechanical process.
  • Q: Does turing thesis cover everything?

Don’t know – Following supports it.

Support:

1)Anything possible on an existing digital comp. can also be doing on a TM.

2)No one has yet found an “algorithmically” solvable problem which cannot be done on a TM.

3)No alternative mechanical computation models prove more “powerful” than a TM.

  • Still an assumption:

Analogous to Basic Law’s of Physics

“Failure to find experiments to invalidate the law strengthens our confidence in it.”

… Progressive refinements of physical theory

… analog here?

If we accept Turing’s Thesis, we may now precisely define an algorithm.

Definition 9.5

An algorithm for function f: D  R is a Turing machine M, which given as input any d  D on its tape, eventually HALTS with correct answer f(d) on its tape.

Ex. We require that

q0d ├*m qf f(d),qf F

 d  D