4.2. Felismerő Turing-gépek

4.9. Definíció

Legyen  egy Turing-gép,  és . 
Ekkor -t elfogadó Turing-gépnek nevezzük, a -beli állapotokat 
pedig elfogadó állapotoknak. 

4.10. Definíció

Legyen  egy elfogadó Turing-gép,  a  elfogadó állapotainak 
halmaza. Azt mondjuk, hogy  elfogadja a 
             szót, hogyha  
számítása véges a bemeneten, és megálláskor -beli állapotban van.

4.11. Definíció

Legyen  egy elfogadó Turing-gép.
Az  nyelvet a  által felismert
nyelvnek nevezzük.

4.12. Lemma

Legyen  egy elfogadó Turing-gép és . Ekkor  átalakító 
Turing-gép, amelyikre 
             pontosan akkor, ha .

Bizonyítás

Az előbbi lemma alapján megállapíthatjuk, hogy az elfogadó Turing-gépek lényegében nem jelentenek újdonságot az átalakító Turing-gépekhez képest, azonosnak tekinthetők az általuk felismert nyelv karakterisztikus függvényét megvalósító Turing-géppel.