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.