Come posso applicare il teorema del riso?

Question

Sto imparando per il mio esame di calcolo e complessità in cui c'è sempre un esercizio per decidere se un problema è decidabile o meno.

In uno degli esami passati, c'era il seguente problema:

Dato la macchina di tentazione m, decidere se esiste un numero primo su cui si ferma.

Dovrei decidere se il problema è decidabile o meno.

Immagino di poter riscrivere il problema nella lingua $ l={\ Langle m \ GRANGLE | \ esiste p \ in \ mathbb {p}: m (p) \ downarrow \} $ . Mi è stato dato un suggerimento che posso usare il teorema del riso per dimostrare che la lingua è indecidabile. In realtà sto cercando, dal momento che non ho idea di come dovrei applicare il problema del teorema del riso (Generaly).

Sono interessato a queste domande:

.
1. Come posso scoprire se il teorema del riso è applicabile o no?
2. Se lo trovo, come applicarlo? (In questo esercizio in particolare)

Qualsiasi aiuto apprezzato.

Answer 1

Ecco un'altra tecnica a prova di elementare che non usa il teorema del riso che è troppo overkill per questo semplice problema.

Abbiamo la fattura della famiglia della macchina $ f (a) $ che entra in un ciclo infinito per qualsiasi input tranne 2, nel qual caso eseguerà il programma $ A $ , che può essere arbitrario.

Ora se potessimo decidere il tuo problema originale, potremmo decidere per macchine arbitrarie inputless inputless se si fermano usando $ f $ .Ma questo è ovviamente indecidabile e quindi è anche il tuo problema originale.