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