the halting problem
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.
[cite:;taken from @computability_rogers_1987 chapter 1.9 the halting problem]
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 
,
[cite:;taken from @computability_rogers_1987 theorem VII]
such that for all ,[cite:;taken from @computability_rogers_1987 theorem VII]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.. 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 .[cite:;taken from @computability_rogers_1987 chapter 1.9 the halting problem]
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
[cite:;taken from @computability_davis_1994 chapter 4.6 diagonalization and reducibility]
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[cite:;taken from @computability_davis_1994 chapter 4.6 diagonalization and reducibility] is basically the same as 
in my notes.