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.