Decidibilità dei problemi di decisione

Question

Qualcuno può dare intuizione come rispondere a queste domande? Da un lato posso dire che la maggior parte di essi è indecidenziale perché possiamo ridurre il problema di arresto (o può apparire un problema di arresto perché non conosciamo a TM dato nulla in modo che possa comportarsi in modo imprevedibile, può semplicemente loop su qualsiasi input) , ma su un'altra mano nella domanda 2. Non sappiamo molto sulla macchina, tuttavia posso hardcore tutte le parole nel mio TM per quanto riguarda il linguaggio dato è limitato. Inoltre, per la domanda 1. Sono in grado di creare TM che controlla se l'output di M è pari (classificherei questo problema come semi-rilevabile).

Quale tipo di seguenti problemi di decisione sono: decide, parzialmente decidabile o addirittura indecidibile:

1. Il linguaggio della macchina data M contiene solo parole pari?

2. La macchina M data accetta una dimensione del linguaggio finito che è inferiore al 2019?

3. Diciamo che la lingua a è priva di prefisso se nessuna parola appartenente a a è un prefisso di qualsiasi altra parola da A. Ad esempio, la lingua A = {0, 10, 110, 1110, ...} è senza prefisso, mentre la lingua b = { 0, 1, 00, 11, 000, 111, ...} non ha questa proprietà (ad esempio, perché 0 è il prefisso 00). Considera la seguente lingua (problema di decisione): l = {⟨m⟩ | L (m) è senza prefisso}.

4. La funzione ricorsiva data è un'impresa?

5. La funzione ricorsiva data è un'iniezione?

6. La macchina M si ferma a BB?

7. La macchina M accetta la lingua vuota?