Comprensione del paesaggio prima
Prima di immergerti in esempi, chiariamo le categorie:
* Turing-decidabile (ricorsivo) Lingue: Queste sono lingue per le quali una macchina Turing può * sempre * fermare e rispondere correttamente a "sì" (accetta) se la stringa di input è nella lingua o "no" (rifiuta) se la stringa di input non è nella lingua. La macchina Turing fornisce sempre una risposta definitiva.
* Turing-Rognizable (ricorsivamente enumerabili) Lingue: Queste sono lingue per le quali una macchina Turing si fermerà e accetterà se la stringa di input * è * nella lingua. Tuttavia, se la stringa di input è * non * nella lingua, la macchina Turing potrebbe fermarsi e rifiutare, oppure potrebbe funzionare per sempre (loop). La chiave è che * alla fine * dice "sì" per le stringhe nella lingua.
* Lingue riconoscibili (non-recursamente enumerate): Queste sono lingue per le quali * NO * Turing Machine può anche essere progettata per riconoscere in modo affidabile le stringhe nella lingua. Non importa quanto tu sia intelligente, non puoi costruire una macchina Turing che accetterà tutte le stringhe nella lingua (e potenzialmente fermare quando non lo è). Il complemento di un linguaggio riconoscibile Turing è riconoscibile.
Esempi di lingue riconoscibili non di Turing
Gli esempi più comuni di lingue riconoscibili non Turing spesso coinvolgono i complementi di noti problemi indecidibili.
1. Il complemento del problema di arresto (¬Halt):
* Il problema di arresto (Halt): Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m, W⟩` dove la macchina Turing` m` si interrompe sulla stringa di input `w`. (Questo è riconoscibile Turing ma * non * disordinabile).
* ¬Halt: Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m, w⟩` dove la macchina Turing` m` non si ferma * sulla stringa di input `w`.
* Perché non è riconoscibile: Se ¬alt fosse riconoscibile, allora si sarebbe arrestato (potremmo simulare `m` su` w` e se il nostro riconoscimento per ¬Halt accetta, sappiamo che `M` non si ferma; se si rifiuta, sappiamo che` M` si fermano). Ma Halt è * comprovato * indecidibile. Poiché l'arresto è riconoscibile ma non rilevabile, il suo complemento, ¬Halt, deve essere riconoscibile non-Turing. Se Halt fossero decidabili, allora entrambi e il suo complimento sarebbero riconoscibili.
2. Il complemento del problema di accettazione (¬A tm ):
* Il problema di accettazione (a tm ): Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m, w⟩` dove la macchina Turing` m` accetta la stringa di input `w`. (Questo è Turing-riconoscibile ma non rilevabile).
* ¬a tm : Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m, w⟩` dove la macchina Turing` m` non * accetta * String input `w`. `M` può rifiutare o loop.
* Perché non è riconoscibile: Ragionamento simile a quello con ¬alt. Se ¬a tm erano riconoscibili, quindi un tm Sarebbe disordinabile, contraddicendo l'indecidabilità nota di un tm .
3. Il complemento del problema del vuoto per le macchine Turing (¬E tm ):
* Il problema del vuoto (e tm ): Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m⟩` in cui il linguaggio riconosciuto dalla macchina Turing` m` è vuota (cioè `l (m) =∅`). (Questo è * non * riconoscibile).
* ¬e tm : Questo è il linguaggio contenente tutte le codifiche della macchina Turing `⟨m⟩` in cui il linguaggio riconosciuto dalla macchina Turing` m` non * non * vuoto (cioè, `l (m) ≠ ∅`).
* Perché è riconoscibile Turing: Una macchina Turing può riconoscere questo linguaggio simulando la macchina `M` su tutti i possibili input fino a quando` M` accetta.
4. Il linguaggio delle macchine Turing che non si fermano su * qualsiasi * input:
* Considera il linguaggio delle macchine Turing che, quando avviate su * qualsiasi * stringa di input, non si fermerà mai. Non esiste un algoritmo generale per determinare questo.
* Potresti provare a eseguire la macchina su molti input diversi, ma non sarai mai sicuro che non fermerà qualche altro input non testato.
In che modo le lingue riconoscibili non Turing differiscono
La differenza chiave sta nella capacità di creare una macchina Turing che * in modo affidabile * riconosce le stringhe nella lingua:
* Turing-decidabile: Una macchina Turing * sempre * dà una risposta corretta ("Sì" o "No") e si ferma.
* Turing-Rognizable: Una macchina Turing fornisce una risposta "sì" se la stringa è nella lingua, ma potrebbe loop per sempre se la stringa è * non * nella lingua.
* Non-Turing Riconoscibile: * Nessuna macchina* Turing può essere costruita per riconoscere anche le stringhe in modo affidabile nella lingua. Qualsiasi macchina di Turing che provi accetterà alcune stringhe che * non sono * nella lingua, loop per sempre su stringhe che * sono * nella lingua o falliscono in qualche altro modo fondamentale.
Intuizione
Pensaci così:
* decidabile: Hai un test perfettamente affidabile che ti dà sempre la risposta giusta.
* Riconoscibile: Hai un test che * sicuramente * dirà "sì" se è la risposta corretta, ma potrebbe non essere in grado di dirti se la risposta è "No".
* Non riconoscibile: Non puoi nemmeno creare un test che identificherà in modo affidabile i casi "sì". Qualsiasi test che ti viene in mente sarà imperfetto e potrebbe darti risultati errati.
Implicazioni importanti
L'esistenza di lingue riconoscibili non Turing ha profonde implicazioni per l'informatica e la matematica:
* Limiti del calcolo: Dimostra che ci sono limiti intrinseci a ciò che i computer possono fare, non importa quanto potenti diventino.
* Undecidabilità: Sottolinea l'esistenza di problemi fondamentalmente indecidibili:non esiste un algoritmo in grado di risolverli in tutti i casi.
* Tecniche di prova: È necessario l'uso di tecniche di prova sofisticate (come la diagonalizzazione e le riduzioni) per dimostrare l'indecidabilità o la non riconoscibilità di alcuni problemi.
In breve, le lingue riconoscibili non Turing definiscono il confine di ciò che è fondamentalmente insolibile. Sono una parte cruciale della comprensione dei limiti teorici del calcolo.
Programmazione © www.354353.com