|
| |
|
|
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.
|
|
0
| |
|
|
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, 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, 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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| The prototypical example of a noncomputable sequence.
|
|
|
REFERENCES
| Nigel Cutland, "Computability: An introduction to recursive function theory". Cambridge University Press, 1980. p. 78.
|
|
|
LINKS
| Ramin Naimi, URM Simulator
|
|
|
EXAMPLE
| 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.
|
|
|
CROSSREFS
| Cf. A004147, A028444, A052200, A060843, A081419.
Sequence in context: A051348 A190445 A141648 * A020851 A190457 A179833
Adjacent sequences: A118871 A118872 A118873 * A118875 A118876 A118877
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Sam Alexander (amnalexander(AT)yahoo.com), May 24 2006
|
| |
|
|
