Passaggio nella dimostrazione del Teorema di Enumerazione

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Antonio Sisbarra
Nella prima parte della dimostrazione del teorema di Enumerazione si dice che la funzione U, definita nel teorema di forma Normale, è anch'essa una funzione calcolabile in due argomenti: i e x.

Come mai la y non fa parte degli argomenti della funzione che poi servirà nella dimostrazione del teorema di Enumerazione?

MindFlyer
y non è una variabile libera perché è legata all'operatore di minimizzazione. Quindi ovviamente non è un parametro della funzione. Ripassa il teorema di forma normale...

Tra l'altro, per dimostrare questa versione del teorema di enumerazione non serve nemmeno passare per il teorema di forma normale, ma basta semplicemente la macchina di Turing universale.

EDIT. Ah, mi sono accorto che Degano costruisce la MdT universale dopo aver dimostrato i teoremi di forma normale e di enumerazione. Quindi in quel punto non la può usare. Scelta forse poco ortodossa, ma tant'è. Anche perché nel "dimostrare" il teorema di forma normale si appoggia alla tesi di Church-Turing (insomma, non lo dimostra davvero), il che inficia anche il teorema di enumerazione. Mentre potrebbe risparmiarsi questo giro contorto semplicemente anticipando la costruzione della MdT universale... In definitiva, trattasi dell'ennesima deganata.
Rispondi

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