Perché il teorema di ricorsione è dimostrato che c'è un set finito indecididabile?

Question

Ho creato qualcosa di simile alla prova di Sipser per l'indecisione della $ a_ {tm} $ (teorema 6.5), "dimostrando" l'indecisione di un set che deve essere finito. Presumibilmente, è sbagliato, ma non riesco a capire perché per la vita di me.

.

$ a_r:={\ Langle m \ Rangle | M= r \ Land m \ text {accetta "foobar"} \} $

assumere $ d $ decide $ a_r $ . $ r:= $ su qualsiasi ingresso:

.
1. Con il teorema di ricorsione, ottieni la propria descrizione $ \ langle r \ rangle $
2. Esegui $ D $ su $ \ langle r \ rangle $
3. Fai il contrario di ciò che $ d $ dice. Se rifiuta, accetta. Se accetta, rifiutare.

$ R $ contraddice cosa $ d $ dice circa $ R $ . Quindi $ D $ Non può essere un decisore. (cioè se $ d $ accetta $ r $ , $ R $ dovrebbe accettare "foobar", ma $ r $ rifiuterà tutte le stringhe. Se $ D $ < / span> rifiuta $ r $ , $ r $ dovrebbe rifiutare "foobar", ma $ R $ accetterà tutte le stringhe).

ma poiché $ a_r $ può contenere solo $ r $ , $ A_R=DEVERSETSET \ LOR A_R={\ Langle r \ Rangle \} $ . In ogni caso, è finita, quindi $ a_r $ è decidabile.

Allora cosa c'è che non va nel primo argomento? Alcune idee mi attraversano la mente:

.
• Sto perdendo un dettaglio importante facendo un argomento informale.
• qualcosa di strano nella relazione ricorsiva tra edificio $ a_r $ e riferizione $ d $ . (Questo potrebbe essere evitato restringendolo al sottoinsieme del TMS con la lunghezza di R, che potremmo "indovinare" prima che r venisse creato - e sarebbe ancora finita)
• Logic Shenanigans (A La The Liar Paradox)

Ma io non vedo esattamente qual è il problema.

Elaborazione sulla mia interpretazione dell'errore per riferimento aggiuntivo :

L'argomento è simile a questo:

.
1. Dato un decisore arbitrario per $ a_r $ , possiamo costruire una classe TM $ r $ . < / li >.
2. Dato $ R $ , costruiamo $ a_r $ .
3. Quindi possiamo ottenere una contraddizione. Quindi non c'è decisione per $ a_r $ .

È circolare e, si spera più ovviamente sbagliato. E indovinare la lunghezza della classe $ R $ , come suggerito in precedenza, non funziona neanche - perché un decisione arbitrario ha una lunghezza arbitraria.

Answer 1

Il tuo argomento "va all'indietro."

Si noti che la tua definizione di $ R $ dipende da $ d $ (graduato / "Math-Container"> $ 2 $ ). Ciò significa che non è possibile concludere che no macchina decide $ a_r $ , semplicemente quella $ d $ specificamente no.

Fondamentalmente, quello che hai scritto sembra questo:

.

• reclamazione: c'è qualche $ x $ tale che no $ y $ fa [ Attività che coinvolge $ x $ ].

• Prova: raccogliendo un po 'di class class="container di matematica"> $ y $ , costruiamo una $ x $ $ y $ non fa [attività che coinvolge $ x $ ].

e questo non è valido .

---

.

Può aiutare a considerare un argomento della stessa "forma" ma su un argomento più concreto.

.

• Richiesta: c'è un numero naturale $ n> 1 $ che non è divisibile da qualsiasi Prime $ p $ .

• Prova: Fissaggio di una Prime $ P $ , Let $ N= P + 1 $ . Quindi $ N $ non è divisibile da $ p $ .

La natura sottile della decidabilità spesso fa sembrare le domande a riguardo più complicate di quanto non siano, e penso che questa sia una tale situazione.

---

.

Vale la pena notare che il teorema di ricorsione può essere applicato qui per mostrare Qualcosa - in particolare, che la classe $ A_R $ s non sono < Em> uniformemente decidabile.

In particolare, supponiamo di avere una funzione computabile totale $ f $ . Dal teoreme di ricorsione posso montare una macchina $ R $ in modo tale che $ r $ si comporta come descrivi per $ d= f (r) $ e così $ f (r) $ Impossibile decidere < class="Math-Container"> $ A_R $ . Questo significa:

.

Mentre per ogni $ R $ c'è una certa $ d $ che decide $ A_R $ , non esiste un modo Computable per trovare un tale $ D $ Dato $ r $ .

Non è sorprendente - lo stesso risultato segue più semplicemente dall'insolvibilità del problema di fermezza - ma è un esempio importante di come è possibile utilizzare il teorema di ricorsione per dimostrare risultati di decidabilità non uniformi anche quando ognuna delle lingue in questione è decidabile.

Answer 2

È il tuo secondo punto elenco - qualcosa di strano nella relazione ricorsiva.

L'argomento sta cercando di mostrare una contraddizione esibendo un linguaggio finito che è indecidabile.

In altre parole, l'argomento deve dimostrare che esiste un linguaggio finito $ l $ tale che per ogni decisore $ D $ , c'è qualche ingresso $ w $ tale che $ d $ decide in modo errato Sia $ w \ in l $ .

Il problema è che stai commutando quantificatori: stai raccogliendo una decideria $ d $ prima, quindi stai esibendo una lingua (specificando la classe di span="Math-Container"> $ R $ dipende da $ d $ ) e dicendo che $ d $ non decide $ a_r $ correttamente. Per ottenere una contraddizione, la tua lingua non può sapere in anticipo il decisivo sarà provato.

Mi piacerebbe aggiungere questo mentre $ a_r $ è decidabile per ogni file fisso $ r $ (come è un set finito), se si effettua $ R $ un parametro di ingresso, il set risultante non è più decidabile.