formal definition of a Turing machine
Based on the informal description of a Turing machine in the parent entry, we give it a formal mathematical definition:
Definition. A Turing machine is a 7-tuple consists of the following:
an alphabet called the state alphabet,
an element called the accept state, and
an element such that , called the reject state,
an alphabet called the input alphabet,
a symbol called the blank symbol not in ,
a function called the transition function, such that
where and .
are collectively called the halt states of .
Actually, the definition above is only part of the story. What is described in the definition is the “finite control” (the brain) portion of a Turing machine. All by itself, the finite control is useless. In order for a Turing machine to do computations, two other ingredients are needed to complete the description: a tape, and a reading head. The two can be formalized as follows:
Definition. A tape, or formally a tape description, is a function . A position of the reading head is an integer .
In other words, the tape of a Turing machine is infinitely long in both direction, and is divided up into squares. The content of each square is either a symbol in or blank (). The purpose of the tape is to store input, output, as well as any other strings that are used during computations.
The finite control and the tape of a Turing machine are connected by a reading head, which points over the tape, has the ability to move left or right along the tape, and reads the tape one square at a time. The position of the reading head is the square it is currently reading.
The Turing machine defined this way is also known as a two-way deterministic Turing machine.
To formally describe the computational process of a Turing machine, we need to know three things: what is the current state of the finite control, what is on the tape, and what is the current position of the reading head:
Definition. A configuration of a Turing machine is a triple , where , called the state of the configuration, is a tape description called the tape description of the configuration, and is a position of the reading head called the position of the reading head of the configuration.
We are now ready to describe what it means for a Turing machine to compute something:
Definition. Given a Turing machine (with the associated tape and reading head), a computation step is a binary relation on the set of all configurations of , defined as follows: if
We can of course take the reflexive transitive closure of to obtain .
Definition. An input to a Turing machine is a (finite) word over . If the length of is , we define the tape description of as follows:
Definition. Given an input and a Turing machine , a computation of by is a finite sequence
where . From the computation of above, we also say that the computation of leads to state . is said to accept an input iff it there is a computation of leading to the accepting state . In other words, is accepted by iff for some and . Similarly, is rejected by iff for some and . is said to halt on input iff it either accepts or rejects . Otherwise, is said to loop on .
By the definition of the transition function , once the computation of leads to the accepting state , it never leaves that state. Likewise, once the computation of leads to the reject state , no further computation will lead to a non-reject state.
Definition. Let be a Turing machine. The set of words accepted by is denoted by . A set of words over is said to be Turing acceptable if there is a Turing machine such that . If halts on every input word, then is said to be total.
It can be shown that is Turing acceptable iff it is recursively enumerable. Furthermore, is recursive iff there it is Turing acceptable by a total Turing machine.
The Turing machines described above are known as language acceptors. However, any Turing machine can be modified so it is capable of producing outputs. Using this modification, one can think of a Turing machine as a partial function where an input is in its domain iff the computation leads to a halting state. More can be found here (http://planetmath.org/TuringComputable).
|Title||formal definition of a Turing machine|
|Date of creation||2013-03-22 19:09:47|
|Last modified on||2013-03-22 19:09:47|
|Last modified by||CWoo (3771)|