7.A General Model of Computation§

Want a general model of computation that is as simple as possible.

Our key concern now is ability (we want to do “anything),
but not efficiency.
Transducer: Change the value of a string (convert input to output)
Wish to be able to reason about the model.
“State machines” are simple.

Necessary features:

Read
Write
Compute

Turing Machines (1)

A tape, divided into squares.

A single I/O head:

Read current symbol

Change current symbol

States

Control Unit Actions:

(1) Put the control unit into a new state.

(2) And

(a) Write a symbol in current tape square.

(b) Move I/O head one square left, right, or stay at the current cell.

Turing Machines (2)

Tape has an infinite left end, and right end.
The letters that can appear on the tape are an important part of the definition for a given Turing machine.
The alphabet of the machine is these letters that may appear in the input.
There is also the blank character ‘’#’’

Formal definition of Turing Machine

A Turing machine is formally defined as (

$Q$ ,

$\Sigma$ ,

$\Gamma$ ,

$s$ ,

$F$ ,

$\delta$ ) where

Q is a finite set of states.
Σ is an alphabet. This is used to define the input.
Γ is another alphabet that at least includes Σ and
#. It might include other symbols, and is the alphabet used
 by the computational process.
s∈Q is the initial state.
F⊂Q is the set of final states.
δ is a partial function from Q×Γ to

Formal definition of Turing Machine

The machine operates as follows: For $q \in Q$ , $a \in \Sigma$ and $\delta(q, a) = (p, b, m)$ , when in state $q$ and scanning $a$ , enter state $p$ , replace $a$ with $b$ , and move the head ( $m$ is $L$ , $R$ , or $S$ ).

Formal definition of Turing Machine

To do computation, we have to have some conventions about starting and ending the process. The machine stops immediately if (1) it enters any final state, or (2) it is in a state and scans a character for which there is no transition. (Note that there are many ways to define Turing Machines, and some definitions require an explicit reject state. We do not.)

Turing Machine Example 1

$M = (Q, \Sigma, \Gamma, s, F, \delta)$ where

$Q = \{q_0, q_1\}$ ,
$\Sigma = \{a\}$ ,
$\Gamma = \Sigma \cup \{\#\}$ ,
$s = q_0$ ,
$F = {q_1}$ ,
$\delta =$

$\begin{split}\begin{array}{lll} \hline q&\gamma&\delta(q, \gamma)\\ \hline q_0&a&(q_0, \#, R)\\ q_0&\#&(q_1, \#, S)\\ \end{array}\end{split}$

Turing Machine Example 1

0 / 0 Settings

<<<>>>

In this slideshow, we will trace the acceptance or rejection for some strings.

a;#,R

#;#,S

Saving...

Server Error
Resubmit

Turing Machine Example 2

#;#,S

a;a,R

b;b,R

c;c,R

#;#,S

c;c,R

#;#,S

b;b,R

Notation

A configuration for a Turing machine looks like this:

$(q, aaba\#\underline{\#}a)$

This means that the TM is on state $q$ , the tape contains $aaba\#\underline{\#}a$ and read / write head position is on the underlined $a$ . In this book, any TM starts running with the read/write head position is on the first Tape letter from the left.

Notation

A halted configuration occurs when the machine do not find a move from the given state using the tape letter (the current configuration). In other words, TM halts if there is no $\Delta$ defined. That is why in this book we always assume that there are no transitions defined out of the final state. Therefore, any TM will halt once it entered a final state.

Notation

A computation is a sequence of configurations for some length

$n \geq 0$ .

Recall the TM example that earases all a’s from the tape. Here are the cofigurations for the input aaaa

(q0,a_aaa)⊢M (q0,#_aaa)
⊢M (q0,##_aa)
⊢M (q0,###_a)
⊢M (q0,####_)
⊢M (q1,#####_)
 