Stavo riguardando l'esercizio 2.1.7 dell'eserciziario, ultima edizione (2005 mi pare). Il testo è questo:
CITAZIONE
Dimostrare per riduzione che le seguenti funzioni non sono compatibili:
1. g(x,y) = if x in Ify then 1 else 0
La soluzione dice che bisogna ridurre a g la funzione che stabilisce la terminazione delle TM.
Poi parte dicendo:
CITAZIONE
sia h(x) = if fx(x) != _|_ then x else _|_
Questa funzione è ovviamente computabile: si simula la x-esima TM sull'ingresso x e se questa non termina si scrive x, altrimenti non si termina
Poi prosegue la dimostrazione trovando che, se g(x,y) fosse computabile, allora sarebbe computabile anche il problema di terminazione delle TM, ovvero
CITAZIONE
if fx(x) != _|_ then 1 else 0
che invece sappiamo essere incomputabile.
Io però non riesco a capire come mai la funzione h(x) che abbiamo definito allo scopo di risolvere il problema, è computabile, mentre la funzione di terminazione delle MT è incomputabile!
Sono un caso disperato, lo so, ma sta "informatica" teorica davvero mi sta tirando scemo....
Grazie e ciao!
