Poiché si ferma sempre, la macchina è in grado di decidere se una data stringa è membro di un linguaggio formale. La classe dei linguaggi che possono essere decisi da tale macchina è esattamente l'insieme dei linguaggi ricorsivi. È importante notare che, dato il problema della terminazione, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile - non c'è nessun algoritmo per determinarlo. L'insieme delle macchine che terminano sempre è solo ricorsivamente enumerabile.