Macchina che termina sempre

Nella teoria della computabilità una macchina che termina sempre, chiamata anche un decider o macchina di Turing totale, è un particolare di tipo di macchina di Turing per cui, al contrario del modello generale, vi è garanzia che termini per ogni input. 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 macchine di questo tipo è esattamente l'insieme dei linguaggi ricorsivi. Dato il problema della fermata, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile,non c'è nessun algoritmo per determinarlo.