Riduzione di TOT a INF
Inviato: 14/12/2016, 21:11
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]
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]