**Definition 4.9.**

Let be a Turing machine, and . Then is called an acceptor Turing machine and the states of are called accepting states.

**Definition 4.10.**

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 .

**Definition 4.11.**

Let be an acceptor Turing machine. Then is called the language recognized by .

**Lemma 4.12.**

Let be an acceptor Turing machine and let . Then transformator Turing machine such that if and only if .

**Proof**

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.