La lingua l= {, m accetta una quantità finita di parole} decidabile?

Question

$ l={ |L (m) \ è \ finito \} $ decidabile?M è un TM.

Penso che sia semplice semplice da provare con il teorema del riso.Ma sono interessato a una soluzione che non usa il teorema del riso.

Questo è il mio tentativo: Lascia che f () sia una funzione che funziona nel modo seguente:

.
1. Esegui w su m
2. se m accetti costruire un TM MGwhich accepts only the word w and return M
3. se m respinge costruisci un MGwhich accepts everything. Return M TM

quindi se m è in $ a_ {tm}={ | m \ accetti \ w \} $ Sappiamo che f () è a L. Se M non è in un allora sappiamo che f () accetta ogni parola e quindi parole infiniti.Quindi f () non in l.

è una riduzione della mappatura corretta?

Answer 1

La funzione che hai definito non è affatto una riduzione - potrebbe non fermarsi nemmeno!

Il problema è in esecuzione $ M $ su $ w $ : puoi essere sicuro di $ m $ Non sarà bloccato in un ciclo infinito su $ W $ ? Non puoi.

È possibile definire una corretta riduzione dei seguenti: (su ingresso $ $ )

Creazione della macchina $ m_ {m, w} $ che fa il seguente algoritmo e ritorno in: (su input $ s $ )

.
1. emula $ m $ on $ w $ per $ | S | $ Passi. Se $ M $ fermato in quell'ora, rifiutare $ s $ . Altrimenti, accettare $ s $ .

Lo lascerò per dimostrare che questa è una corretta riduzione da $ h_ {tm} $ a $ l $ (è un buon esercizio!)