A Turing machine
is given
by the following data
The transition function defines how the function behaves if is in
state and the symbol on the tape is
. If
then the machine stops otherwise if
the machines gets into state
, writes
on the tape (replacing
) and moves left if
or
right, if
In the course text the transition function is defined without the
stop option as
. However they allow
to be undefined which correspond to our function returning
stop.
This defines deterministic Turing machines, for non-deterministic TMs we change the transition function to
As for PDAs we define instantaneous descriptions
for Turing
machines. We have
where
means that the TM is in state
and
left from the head the non-blank part of the tape is
and
starting with the head itself and all the non-blank symbols to the
right is
.
We define the next state relation similar as for PDAs:
We say that a TM accepts a word if it goes into an accepting state,
i.e. the language of a TM is defined as
A TM decides a language if it accepts it and it never loops (in the
negative case).
To illustrate this we define a TM which accepts the language
-- this is a language which cannot be
recognized by a PDA or be defined by a CFG.
We define
by
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
The machine replaces an a by (
) and then looks for the first
b replaces it by
(
) and looks for the first
c and
replaces it by a
(
). If there are more cs left it moves left
to the next a (
) and repeats the cycle. Otherwise it checks
whether there are no as and bs left (
) and if so goes
in an accepting state (
).
E.g. consider the sequence of IDs on aabbcc:
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |