Esercizio: dimostrare che l'insieme I dato non è un I.I.R.F.

Rispondi
Avatar utente
andrea.tosti
Messaggi: 15
Iscritto il: 02/10/2018, 9:20

Sto provando a fare l'esercizio presente a pagina 2:
dimostrare che

[math]

non è un I.I.R.F.

Per definizione,
[math]
L'idea a questo punto è negare il quantificatore universale e ottenere
[math]

Allora costruisco una funzione ad-hoc:
[math]

Preso l'indice [math] ottengo

[math]

e concludo che [math]

Preso l'indice [math] (che esiste per il Padding Lemma) (e di conseguenza [math]), impongo anche che [math] e lo posso fare perché gli indici che vengono fuori dal Padding lemma sono [math][math]

[math] perché

[math]


VECCHIA SOLUZIONE (errata, credo)
L'idea a questo punto è che nego la tesi, costruisco una funzione ad-hoc:
[math]

Preso l'indice [math] ottengo

[math]

dato che [math] ha infiniti indici, scelgo [math] e ottengo

[math]

Quindi [math] e quindi I non è un I.I.R.F.
Pareri e correzioni sono ben accetti.
Ultima modifica di andrea.tosti il 12/01/2020, 22:05, modificato 1 volta in totale.
Motivazione: Ho fatto un errore sugli indici
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”