A Turing machine can compute everything, a usual computer program can compute.
Less efficient - but the computation allows a mathematical analysis of
questions like :"What is computable? What is decidable? What is complexity?
Input and output of a Turing machine is performed on a doubly infinite band
containing 0 or 1's. This is the memory of the machine.
The machine running here with 3 states does the following in state 2:
if the band shows 0: go to state 3, move the band to the left
and write 1. If the band shows 1, go to state 1, move the band to the left and
write 0. This rule for state 2 can be abbreviated as 2: (3L1) (1L0).
A challenging sport is to find among all Turing machines
with n states the "busy beaver", the program, which produces
from the empty band a maximum number of consecutive 1's before it
halts.
|
