f(e,e) = 1. Similarly, if g(e) is not defined, then program e does not halt on input e, thus f(e,e) = 0, which leads to g(e) = 0 under g's construction. This contradicts the assumption of g(e) not being defined. In both cases contradiction arises. Therefore any arbitrary computable function f cannot be the halting function h.

Computability theory

A typical method of proving a problem to be undecidable is to reduce the halting problem to .For example, there cannot be a general

1.Previous
3.Next