Tutti i problemi relativi alle macchine di Turing che coinvolgono solo il linguaggio accettato dalla TM sono indecidibili

Question

Mi sono imbattuto nell'affermazione seguente nel classico testo "Introduzione alla teoria degli automatismi, ai linguaggi e al calcolo" di Hopcroft, Ullman, Motwani.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

Dicono che il teorema di cui sopra è per il teorema di Rice che afferma che:

"Ogni proprietà non banale dei linguaggi RE è indecidibile."

In che modo queste due affermazioni sono equivalenti?Solo il primo si occupa i problemi mentre il secondo si occupa di proprietà non banale.

Answer 1

Ci sono alcune parole chiave nell'estratto dal suddetto libro di testo: non banale, problema, proprietà.

Ora, qual è un problema, supponendo che non abbiamo a che fare con problemi di ottimizzazione combinatoria, cioèabbiamo a che fare solo con domande che hanno una risposta SI o NO.Quando fai una domanda SI o NO a una stringa di input, se la risposta è SI la inserisci in un set $L$ e se la risposta è NO lo scarti e basta.Ora questo set $L$ è la lingua o il problema.Contiene tutte quelle stringhe che soddisfano la nostra domanda SI o NO.

Tutto non banale i problemi Di Macchine di Turing che coinvolgono solo la lingua accettata dalla TM sono indecidibili

Qui l'autore parla di domande SI o NO (rispetto alle macchine di Turing) che coinvolgono solo l' linguaggio accettato dalla macchina di Turing,cioè.il linguaggio ricorsivamente enumerabile (RE), il che significa che il nostro set "problematico" conterrà solo linguaggi RE.Ora, un problema banale è quello in cui la nostra domanda SI o NO è soddisfatta da tutti gli input oppure non è soddisfatta da nessuno degli input.Quindi un problema non banale è quello che non è né vuoto né ha tutti gli input possibili.

Teorema del riso:"Ogni proprietà non banale dei linguaggi RE è indecidibile."

La proprietà dei linguaggi RE è un insieme di linguaggi RE aventi tale proprietà.

Proprietà non banale:La proprietà è soddisfatta da tutte le lingue interessate oppure da nessuna.

Quindi la "proprietà non banale dei linguaggi RE" diventa l'insieme dei linguaggi RE e non è né vuoto né ha tutti i possibili linguaggi RE.

Per l’argomentazione precedente possiamo dire che le due affermazioni sono equivalenti.

(In effetti proprietà e problema sono la stessa cosa, dopo tutto sono entrambi insiemi di stringhe.Ora potremmo pensare che la proprietà sia un insieme di lingue, anche se, sebbene sia vero, è scomodo rappresentare le lingue in un insieme (poiché le lingue possono essere infinitamente lunghe), piuttosto ciò che viene fatto è invece della lingua, rappresentiamo il corrispondente Turing Machine con una codifica adeguata)