• Wilfrid Laurier University

• CP 414

CP414 Final

3.1 Turing Machines

Turing Machines

- Similar to a finite automaton but with an unlimited and unrestricted memory, a

Turing machine is a much more accurate model of a general purpose computer.

-

Differences between finite automata and Turing machines.

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

2. The read–write head can move both to the left and to the right.

3. The tape is infinite.

4. The special states for rejecting and accepting take effect immediately.

Formal Definition

- As a Turing machine computes, changes occur in the current state, the cur- rent

tape contents, and the current head location.

o these three items are called a configuration of the Turing machine

- for state q, and two strings u and v over the tape alphabet Γ, we write u q v for the

configuration where the current state is q, the current tape contents is uv, and the

current head location is the first symbol of v

- e.g. 1011q701111 represents configuration when tape is 101101111, current state

is q7 and head is on the second 0

- say configuration C1 yields configuration C2 if Turing machine can go from C1

to C2 in a single step

o We have a, b, and c in Γ, as well as u and v in Γ∗ and states qi and qj . In

that case, uaqibv and uqjacv are two configurations. Say that

§ uaqibv yields uqjacv

- The start configuration of M on input w is the configuration q0 w, which

indicates that the machine is in the start state q0 with its head at the leftmost

position on the tape

- In an accepting configuration, the state of the configuration is qaccept.

- In a rejecting configuration, the state of the configuration is qreject

- Accepting and rejecting configurations are halting configurations and do not

yield further configurations.

- A Turing machine M accepts input w if a sequence of configurations C1, C2, . . . ,

Ck exists, where

1. C1 is the start configuration of M on input w,

2. each Ci yields Ci+1, and

3. Ck is an accepting configuration.

Definition

Call a language Turing-recognizable if some Turing machine recognizes it.1

- when start a turing machine on an input, 3 outcomes are possible

- may accept, reject or loop

- deciders: machines that halt on all inputs; never loop, always make a decisions to

accept or reject

Definition

Call a language Turing-decidable or simply decidable if some Turing machine decides it.

Example

Turing Machine M2 that decides A = {02n | n ≥ 0}, the language consisting of all strings

of 0s whose length is a power of 2.

M2 = “On input string w:

1. Sweep left to right across the tape, crossing off every other 0.

2. If in stage 1 the tape contained a single 0, accept.