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 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 ‘’#’’
Formal definition of Turing Machine
A Turing machine is formally defined as
(Q, Σ, Γ, s,
F, δ) 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∈Q, a∈Σ and
δ(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.)
Here we see a Turing Machine's states and transitions presented in the form of a graph. This machine will accept strings with an even number of a's. In particular, when in state q0, if the current symbol is 'a' it will be converted to '#' and the head moved to the right. If the current symbol is '#', it will remain a '#' and the machine will stop in state q1 (a final state).
A configuration for a Turing machine looks like this:
(q,#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.
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 δ 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.
Notation
A computation is a sequence of configurations for some
length n≥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,#a_aa)
⊢M(q0,##a_a)
⊢M(q0,###a_)
⊢M(q0,#####_)
⊢M(q1,#####_)
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’.
q0
q1
a;a,R #;#,R
b;b,S
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.
Transducers
Formally: Let f be a function from Σ∗0
to Σ∗1. Turing machine M is said to compute
f when, for any string w∈Σ∗0,
if f(w)=u then
(s,#w_)⊢∗M(h,#u#_)
for some state hinF (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.
Multiple Parameters
Here is how we express multiple parameters for a function
f(w1,...,wk)=u:
