A machine can do that too:
| Yd(z,x) ¬E <=> ¬(Yz(x,x)=0) | |
| Yd(z,x) = fs(d,z)(x) = fg(z)(x) | |
| Yh(x,y)=0 <=> fx(y) ¬E | |
| Yd(h,x) = fg(h)(x) | |
| Yh(g(h),g(h))=0 <=> fg(h)(g(h)) ¬E | |
| fg(h)(g(h)) ¬E <=> ¬(Yh(g(h),g(h))=0) |
The machine which computes the (primitive) recursive function g(z)
calculates, for any machine Mp, including itself, the
machine index and input g(p) at which Yp
is not the halting function, so Mp does not solve the
halting problem.
Adapted
from Mechanism, Mentalism and Metamathematics -
An Essay on Finitism, Judson C.
Webb,
D. Reidel Publ. Co.
1980, pp. 230-1.