Ecco alcuni esempi di lingue indecidibili, che illustrano diversi modi in cui si presentano l'indecidabilità:
1. Il problema di arresto (H):
* Descrizione della lingua: H ={⟨m, W⟩ | Turing Machine M si ferma sull'ingresso w}. Questo linguaggio è costituito da tutte le coppie della codifica di una macchina Turing (⟨m⟩) e di una stringa di input (W) in modo tale che la macchina m si interrompa quando viene data W come input.
* Undecidabilità: È dimostrato che non può esistere alcun algoritmo che determina correttamente, per ogni ⟨m, w⟩, se M si ferme su w. Questo è un risultato fondamentale nella teoria della calcolo. Qualsiasi tentativo di costruire un tale algoritmo porta a una contraddizione (in genere attraverso la diagonalizzazione).
* Perché è indecidibile: L'indecidabilità del problema di arresto deriva dalla natura intrinseca autoreferenziale delle macchine Turing. Un algoritmo ipotetico che risolve il problema di arresto potrebbe essere usato per creare una macchina paradossale che contraddice il proprio comportamento previsto.
2. Il problema di accettazione (a):
* Descrizione della lingua: A ={⟨m, w⟩ | Turing Machine M accetta w}. Questo è simile al problema di arresto, ma si concentra specificamente sull'accettazione (la macchina si interrompe in uno stato di accettazione).
* Undecidabilità: Questo è anche indecidibile. Se potessimo decidere A, potremmo anche decidere H (perché se M accetta W, si ferma chiaramente su W). Poiché H è indecidibile, un must è anche indecidibile.
3. Il problema del vuoto per le macchine Turing (E):
* Descrizione della lingua: E ={⟨m⟩ | L (m) =∅} dove l (m) è la lingua accettata da Turing Machine M. Questo linguaggio contiene le codifiche di tutte le macchine Turing che non accettano affatto stringhe (la loro lingua è vuota).
* Undecidabilità: Non esiste un algoritmo in grado di determinare, per ogni macchina Turing M, se l (m) è vuoto. Ciò è correlato al problema di arresto; Se potessimo risolvere E, potremmo risolvere il problema di arresto costruendo una macchina m 'che si ferma se e solo se M si ferma e accetta w.
4. Problema di corrispondenza post (PCP):
* Descrizione della lingua: Questo è un esempio più complesso che coinvolge coppie di stringhe. È indecidenziale determinare se un determinato set di coppie di stringhe ha una soluzione (una concatenazione di stringhe dalle coppie che corrispondono).
* Undecidabilità: L'insicidabilità di PCP è dimostrata utilizzando riduzioni (che mostra che se il PCP fosse decidibile, anche il problema di arresto sarebbe decidibile - una contraddizione).
Lingue decidibili - Contrasto:
Le lingue decidibili, d'altra parte, * hanno * algoritmi che si fermano sempre e classificano correttamente le stringhe come appartenenti alla lingua o meno. Esempi includono:
* Il linguaggio dei palindromi: Un algoritmo può facilmente verificare se una determinata stringa è gli stessi in avanti e indietro.
* Il linguaggio delle stringhe contenenti "ABC": Un semplice algoritmo può scansionare una stringa e verificare la sottostringa "ABC".
* Il linguaggio delle stringhe binarie pari: Un algoritmo può controllare la lunghezza della stringa.
In sostanza, la differenza si riduce al fatto che un algoritmo possa essere progettato per * dare sempre una risposta sì/no corretta in tempo finito. Per le lingue indecidibili, tale algoritmo è dimostrabile da creare. L'esistenza di un tale algoritmo è la caratteristica distintiva che distingue decidabile dalle lingue indecidibili.
Programmazione © www.354353.com