is there an effective procedure such that, given any and , we can determine whether or not is defined, i.e., whether or not applied to input yields an output? by church's thesis this question can be put in the following equivalent and precise form. is there a recursive function such that if is convergent and if is divergent? we answer the question in the following theorem.
there is no recursive function such that for all ,
assume there is such a recursive . it can be used to define a new partial function as follows: since must = 0 or 1, this gives an algorithm, and by church's thesis, will be a partial recursive function. let be a godel number for . then, by the definition of , is convergent iff ; but, by our initial assumption about , divergent. this is a contradiction, and hence there can be no such recursive .
the halting problem was one of the first "natural" combinatorial problems to be shown recursively unsolvable. demonstration of the existence of easily described recursively unsolvable problems is one of the more striking achievements of twentieth-century mathematics. prior to such demonstration (in the 1930's) many mathematicians were unwilling to concede that there could exist easily described combinatorial problems (such as the halting problem) which had no algorithmic solution.
let is r.e. however, we can show by reducing to , that is, by showing that , that is not recursive: iff , and the function is computable. in fact, it is easy to show that every r.e. set is many-one reducible to : if is r.e., then
is 1-complete.
is basically the same as in my notes.
the same notation in not-comp-K0 is also used in (in robert i. soare, 2016 definition 1.6.6), it basically denotes the entries of the function in the halting problem, where represents the function and the input to it.