Riduzione di TOT a INF

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

Salve a tutti,
ho sentito che al primo compitino il Degano ha chiesto di dimostrare che TOT si riduce a INF.
Ho provato a dimostrarlo ma inutilmente.... Qualche suggerimento?

MindFlyer:
Va bene. C'è una riduzione abbastanza semplice che manda ogni funzione [math] in una funzione [math] che è definita fino a un certo [math] e non definita da [math] in poi (col caso degenere [math], in cui [math] è sempre definita). Ovviamente, se [math] è totale, dovremo avere [math], altrimenti no.

Come si può fare questa riduzione?

mikele_94
Ah ok... credo di aver capito il barbatrucco....

Costruisco [math] in questo modo.
[math]

In questo modo se [math] calcola la funzione costante [math].
Perciò [math].
Altrimenti se [math]. Quindi in questo caso la macchina [math]diverge quando ha come input valori maggiori di [math], dove [math] è il minimo numero t.c la [math].

Pertanto [math], che è finito e quindi [math]
Rispondi

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