Table of Contents
Cosa significa Turing-recognizable
Una macchina di Turing che accetta o no un linguaggio.
In una TM recognizable i possibili esiti sono solo: accetta; rifiuta/loop.
Cosa significa Turing-decidibile
Cosa significa decisore
No, non significa questo
Un decisore è una macchina di Turing che termina sicuramente in uno stato accept o reject e non ha mai loop infiniti.
Perché un decisore nondeterministico accetti un linguaggio, bisogna che almeno uno dei branch termini con uno stato accettato; viceversa perché sia rifiutato bisogna che tutti i branch finiscano in uno stato rifiutato.