|
Search: id:A118874
|
|
|
| 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
|
|
| 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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
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.
Adjacent sequences: A118871 A118872 A118873 this_sequence A118875 A118876 A118877
Sequence in context: A014413 A131632 A051348 this_sequence A020851 A131033 A135821
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Sam Alexander (amnalexander(AT)yahoo.com), May 24 2006
|
|
|
Search completed in 0.002 seconds
|
