8.1.1. 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

8.1.2. 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.

8.1.3. Turing Machines (2)¶

Tape has an infinite left end, and right end.

The symbols 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 symbols that may appear in the input.

There is also the blank character ‘’#’’

8.1.4. 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.

\(\Sigma\) is an alphabet. This is used to define the input.

\(\Gamma\) is another alphabet that at least includes \(\Sigma\) and \(\#\). It might include other symbols, and is the alphabet used by the computational process.

\(s \in Q\) is the initial state.

\(F \subset Q\) is the set of final states.

\(\delta\) is a partial function from \(Q \times \Gamma\) to

8.1.5. 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\)).

8.1.6. 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.)

8.1.7. 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}\]

8.1.8. Turing Machine Example 1¶

Settings

Saving...
Server Error
Resubmit

8.1.9. Turing Machine Example 2¶

8.1.10. Notation¶

A configuration for a Turing machine looks like this: \((q, \#\underline{a}aba\#)\).

This means that the TM is on state \(q\), the tape contains \(\#aaba\#\) and read / write head position is on the underlined \(a\).

Any TM starts with the read/write head position on the first tape symbol from the left.

8.1.11. Notation¶

A halted configuration occurs when the machine do not find a move from the given state using the tape symbols (the current configuration).

In other words, TM halts if there is no \(\delta\) defined. That is why 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.

8.1.12. 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.

\((q_0, \underline{a}aaa) \vdash_M\ (q_0, \#\underline{a}aa)\)

\(\vdash_M\ (q_0, \#\#\underline{a}a)\)

\(\vdash_M\ (q_0, \#\#\#\underline{a})\)

\(\vdash_M\ (q_0, \#\#\#\#\underline{\#})\)

\(\vdash_M\ (q_1, \#\#\#\#\underline{\#})\)

\(\ \)

8.1.13. Hanging¶

The machine hangs when it goes into an infinite loop

This machine processes strings of a’s and b’s. It scans right until it sees (the first) ‘b’.

8.1.14. Acceptors and Transducers¶

We have become used to machines that act as acceptors. We gave a definition for accept vs. reject for Turing machines.

A Transducer converts one string to another.

8.1.15. Transducers¶

Formally: Let \(f\) be a function from \(\Sigma^*_0\) to \(\Sigma^*_1\). Turing machine \(M\) is said to compute \(f\) when, for any string \(w \in \Sigma^*_0\), if \(f(w) = u\) then

\(\qquad (s, \#\underline{w}) \vdash^*_M (h, \#u\underline{\#})\)

for some state \(h \\in F\) (that is, a Final State for \(M\)).

Such a function \(f\) is said to be a Turing-computable function.

Notice that we require the machine to start with the head under the first symbol of the input string, and end in the first space after the output string.

8.1.16. Multiple Parameters¶

Here is how we express multiple parameters for a function \(f(w_1, ..., w_k) = u\):

\(\qquad (s, \#\underline{w_1}\#w_2\#...\#w_k) \vdash^*_M (h, \#u\underline{\#})\).

8.1.17. Numbers¶

Settings

Saving...
Server Error
Resubmit