Cryptography Reference
In-Depth Information
or implemented on many different physical computing devices. In short, a Turing
machine consists of a (finite-state) control unit and one (or several) tape(s), each
of them equipped with a tapehead (i.e., a read/write head). Each tape is marked off
into (memory) cells that can be filled with at most one symbol. The tapehead is able
to read and/or write exactly one cell, namely the one that is located directly below
it. Hence, the operations of the Turing machine are limited to reading and writing
symbols on the tapes and moving along the tapes to the left or to the right. As such,
the Turing machine represents a
finite state machine
(FSM). This basically means
that the machine has a finite number of states (so-called functional states) and is in
exactly one of these states at any given point in time.
The Turing machine solves a problem by having a tapehead scanning a string
of a finite number of symbols that are placed sequentially in the leftmost cells of one
tape (i.e., the input tape). Each symbol occupies one cell and the remaining cells to
the right on that tape are blank. This string is called an
input
of a problem instance.
The scanning starts from the leftmost cell of the tape that contains the input while
the machine is in a designated
initial state
. At any time, only one tapehead of the
Turing machine is accessing its tape. A step of access made by a tapehead on its tape
is called a
move
. If the machine starts from an initial state, makes one move after
another, completes scanning the input string, eventually causes a satisfaction of a
terminating condition and thereby terminates, then the machine is said to recognize
the input. Otherwise, the machine has no move to make at some point, and hence the
machine halts without recognizing the input. An input that is recognized by a Turing
machine is called an
instance
in a recognizable language.
Upon termination, the number of moves that a Turing machine
M
has taken
to recognize an input is said to be the
running time
or
time complexity
of
M
and
is denoted as
T
M
. It goes without saying that
T
M
can be expressed as a function
T
M
(
n
):
where
n
is the length or size of the input (i.e., the number of
symbols that represent the input string when
M
is in the initial state). It is always
the case that
T
M
(
n
)
N
→
N
n
, because the machine must at least read the input (typically
encoded using the unary representation). In addition to the time requirement,
M
may also have a space requirement
S
M
that refers to the number of tape cells that
the tapeheads of
M
have visited in writing access. The quantity
S
M
can also be
expressed as a function
S
M
(
n
):
≥
N
→
N
and is said to be the
space complexity
of
M
.
In Definition 6.4 we introduced the notion of a polynomial-time algorithm.
Such an algorithm can be implemented, for example, by a polynomial-time Turing
machine. In fact, a Turing machine is called polynomial-time if its worst-case
running time function is polynomial in the input size. For all practical purposes,
polynomial-time Turing machines can perform computations that can also be carried
out on contemporary computer systems within reasonable amounts of time.
