Let be a Turing machine, and . Then is called an acceptor Turing machine and the states of are called accepting states.
Let be an acceptor Turing machine and let be the accepting states of . We say that accepts the word , if the computation of on is finite and at termination the Turing machine is in a state from .
Let be an acceptor Turing machine. Then is called the language recognized by .
Let be an acceptor Turing machine and let . Then transformator Turing machine such that if and only if .
The new Turing machine can be defined using . The states of and the transition function can be redefined on the way, that the Turing machine does not finish the computation there, but erase the tape and writes a 1 instead. ✓
The above Lemma implies that acceptor Turing machines basically do not differ from transformation Turing machines. They computes the characteristic function of the recognised language.