cp's OEIS Frontend

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

%I A118874 #3 Oct 09 2013 14:20:20
%S A118874 1,3,1,4,2,1,1,0,1,12,2,1,1,1,1,16,0,19,1,21,3,2,2,0,1,1,1,1,1,1,1,32,
%T A118874 1,0,0,36,2,1,1,0,2,45,3,2,2,2,2,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,64,1,
%U A118874 67,1,0,0,0,0,0,1,76,2,1,1,1,1,81,0,84,2,86,4,3,3,0,2,2,2,2,2,2,2,1,1,0,0
%N A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.
%C A118874 The prototypical example of a noncomputable sequence.
%D A118874 Nigel Cutland, "Computability: An introduction to recursive function theory". Cambridge University Press, 1980. p. 78.
%H A118874 Ramin Naimi, <a href="http://faculty.oxy.edu/rnaimi/home/URMsim.htm">URM Simulator</a>
%e A118874 Using Cutland's Godel numbering, 80 corresponds to the URM program "Z(1) J(1,1,1) S(1)", which clearly loops forever on any input, so a(80)=0. On the other hand, 17 corresponds to the URM program "S(1) T(1,1)", which, on input 17, produces 18. So a(17)=18+1=19.
%Y A118874 Cf. A004147, A028444, A052200, A060843, A081419.
%K A118874 nonn
%O A118874 0,2
%A A118874 _Sam Alexander_, May 24 2006