Supponiamo, per assurdo, che esista un tale procedimento.
Sia Fi una generica funzione calcolabile.
Prendiamo m tale che Fm(x) = Fi(x)
Fi(x)
Prendiamo n tale che Fn(x) = 0 per ogni x.
Abbiamo che Fm =est Fn sse Fi è totale.
Con il nostro procedimento saremmo in grado di stabilire se Fi è totale o no.
Avremmo dunque un procedimento generale per decidere se una funzione calcolabile è totale o no, ossia K tale che, per ogni P, K([P])→1 se P termina per ogni input, K([P])→0 altrimenti, il che è assurdo. Infatti:
- potremmo definire Q tale che Q([P])→1 se P([P])
, Q([P])→0 altrimenti
[basta applicare K al programma che per qualunque input v calcola P([P])]
- definire il seguente procedimento W:
LEGGI v
10 SE Q(v)→1 VAI A 10
- avremmo: W([W]) sse Q([W]))→0 sse (W([W])