3329:
1843:
2473:
1504:
1049:
139:. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the
3118:
2218:
2925:
1838:{\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the k+1 -ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}
3367:
that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).
801:
3737:
A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following the string of parameters
125:) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the
3723:
To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort,
2468:{\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}
2946:
2805:
578:
273:
1352:
3667:
1227:
792:
2482:
Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which
75:, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the
2719:
2739:
The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive.
2071:
2585:). The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total.
361:
4495:
1044:{\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}
2223:
1509:
2581:
only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form
Theorem (see
4661:
4459:
4586:
4529:
3480:
1495:
4687:
4416:
4552:
2176:
3204:
3536:
1908:
1423:
676:
4612:
4304:
turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church.
2569:
1963:
1108:
591:
defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result):
3689:. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.
3258:
3172:
2800:
3113:{\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}
463:
2920:{\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}
401:
616:
2612:
2514:
2209:
2100:
3412:
4145:: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starts with 3 initial functions
431:
135:
The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of
3713:
472:
283:
as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator.
178:
1232:
3288:
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
3552:
1113:
681:
4733:
Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming
Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982
2724:
holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.
4724:
Jones, N. D., Computability and
Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997
2628:
4764:
1968:
297:
3811:: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:
4747:
4463:
4933:
4751:
4295:
60:
4278:
4911:
4866:
4844:
4823:
4616:
3377:
4743:
2733:
4420:
4041:(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(
4556:
4499:
3417:
1432:
4665:
4394:
3340:
102:
4533:
2119:
4953:
3177:
3485:
2573:
While some textbooks use the μ-operator as defined here, others like demand that the μ-operator is applied to
1852:
1372:
625:
4948:
4590:
136:
2519:
1913:
1058:
4258:
72:
4712:
Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge
University Press, 2007
4836:
Recursively enumerable sets and degrees: A Study of
Computable Functions and Computably Generated Sets
4357:
4325:
3213:
3127:
2760:
3716:
436:
68:
2614:
can be used to compare partial μ-recursive functions. This is defined for all partial functions
63:, it is shown that the μ-recursive functions are precisely the functions that can be computed by
374:
600:
4899:
4099:
induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U
2597:
2490:
2185:
2076:
4834:
3387:
4236:
3307:
588:
3310:. There is no way to computably tell if a given general recursive function is total - see
8:
4928:
2746:
573:{\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}
410:
48:
4299:
4382:
4374:
3698:
3360:
140:
76:
20:
4784:
4907:
4862:
4840:
4819:
4316:
4878:
4854:
4779:
4386:
4366:
4334:
4248:
4231:
2940:
87:
40:
24:
4934:
A compiler for transforming a recursive function into an equivalent Turing machine
4338:
4320:
268:{\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}
4895:
4891:
3312:
2590:
83:
1347:{\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}
47:
to natural numbers that is "computable" in an intuitive sense – as well as in a
4811:
3364:
3306:
if it is defined for every input, or, equivalently, if it can be computed by a
106:
64:
44:
3770:) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " const
3662:{\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))}
1222:{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}
4942:
4887:
4881:
model, thus demonstrating its equivalence to the general recursive functions.
3692:
787:{\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}
126:
4700:
Enderton, H. B., A Mathematical
Introduction to Logic, Academic Press, 1972
4352:
4016:
In a similar manner, but without the sub- and superscripts, B-B-J write:
3328:
4378:
4877:
On pages 210-215 Minsky shows how to create the μ-operator using the
4253:
2802:. Using the minimization operator, a general recursive definition is
4370:
3728:, as we have invested in constructing the universal Turing machine
2714:{\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}
3319:
3261:
2732:
Examples not involving the minimization operator can be found at
2066:{\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}
3715:
defined above is in essence the μ-recursive equivalent of the
143:
can be proven to be total recursive, and to be non-primitive.
16:
One of several equivalent definitions of a computable function
4708:
4706:
4906:(4th ed.). Cambridge University Press. pp. 70–71.
356:{\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,}
2943:, greater-than, and multiplication, respectively. In fact,
82:
Other equivalent classes of functions are the functions of
4703:
3953:", whereas the subscript "n" refers to the n variable "x
3849:" to indicate the identity function over the variables x
4673:
4598:
4538:
4490:{\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}
4481:
4471:
4402:
4285:. Metaphysics Research Lab, Stanford University. 2021.
2487:
is not defined, then the search never terminates, and
4792:
4668:
4619:
4593:
4559:
4536:
4502:
4466:
4423:
4397:
3949:). The superscript "m" refers to the m of function "f
3701:
3555:
3488:
3420:
3390:
3216:
3180:
3130:
2949:
2808:
2763:
2631:
2600:
2522:
2493:
2221:
2188:
2122:
2079:
1971:
1916:
1855:
1507:
1435:
1375:
1235:
1116:
1061:
804:
684:
628:
603:
475:
439:
413:
377:
300:
181:
71:). The μ-recursive functions are closely related to
4886:
4762:
4681:
4655:
4606:
4580:
4546:
4523:
4489:
4453:
4410:
4082:Example: primitive recursion definition of a + b:
3707:
3661:
3530:
3474:
3406:
3252:
3198:
3166:
3112:
2919:
2794:
2713:
2606:
2563:
2508:
2467:
2203:
2170:
2094:
2065:
1957:
1902:
1837:
1489:
1417:
1346:
1221:
1102:
1043:
786:
670:
610:
572:
457:
425:
395:
355:
267:
4772:Transactions of the American Mathematical Society
4204:induction step: h( b', a ) = g( b, h( b, a ), a )
3527:
3471:
3403:
4940:
4355:(Dec 1937). "Computability and λ-Definability".
51:. If the function is total, it is also called a
4748:Primitive recursive function#Equality predicate
4696:
4694:
4656:{\displaystyle {\stackrel {Kleene}{\implies }}}
3945:(not to be confused with his S for "successor"
67:(this is one of the theorems that supports the
3320:Equivalence with other models of computability
4454:{\displaystyle {\stackrel {triv}{\implies }}}
4720:
4718:
4691:
4581:{\displaystyle {\stackrel {161}{\implies }}}
4524:{\displaystyle {\stackrel {160}{\implies }}}
3475:{\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}
1490:{\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}
4752:Primitive recursive function#Multiplication
4682:{\displaystyle \lambda {\mbox{-definable}}}
4411:{\displaystyle \lambda {\mbox{-definable}}}
3297:
4628:
4624:
4568:
4564:
4547:{\displaystyle {\mbox{Turing computable}}}
4511:
4507:
4432:
4428:
3049:
2287:
2283:
2171:{\displaystyle f(y,x_{1},\ldots ,x_{k})\,}
86:and the functions that can be computed by
4929:Stanford Encyclopedia of Philosophy entry
4859:Computation: Finite and Infinite Machines
4818:. Walters-Noordhoff & North-Holland.
4783:
4715:
3199:{\displaystyle \operatorname {Isqrt} (x)}
2167:
1827:
1486:
1414:
667:
607:
566:
352:
3531:{\displaystyle f(x_{1},\ldots ,x_{k})\!}
3384:there are primitive recursive functions
2582:
1903:{\displaystyle f(y,x_{1},\ldots ,x_{k})}
1418:{\displaystyle g(x_{1},\ldots ,x_{k})\,}
671:{\displaystyle h(x_{1},\ldots ,x_{m})\,}
4607:{\displaystyle \mu {\mbox{-recursive}}}
4283:The Stanford Encyclopedia of Philosophy
3482:such that for any μ-recursive function
3302:A general recursive function is called
4941:
4853:
4810:
4798:
4765:"Recursive predicates and quantifiers"
4351:
4315:
3371:
3361:equivalence of models of computability
2564:{\displaystyle (x_{1},\ldots ,x_{k}).}
1958:{\displaystyle g(x_{1},\ldots ,x_{k})}
1103:{\displaystyle f(x_{1},\ldots ,x_{k})}
279:Alternative definitions use instead a
4832:
4744:Primitive recursive function#Junctors
2734:Primitive recursive function#Examples
3853:; B-B-J use the identity function id
3323:
4296:Stanford Encyclopedia of Philosophy
3931:Composition (Substitution) operator
97:recursive functions with values in
13:
4321:"λ-definability and recursiveness"
3071:
2297:
2294:
2291:
1551:
1548:
1545:
865:
862:
859:
545:
542:
539:
332:
329:
326:
251:
248:
245:
14:
4965:
4922:
4861:. Prentice-Hall. pp. 210–5.
4785:10.1090/S0002-9947-1943-0007371-8
3380:due to Kleene says that for each
1568:where the k+1 -ary function
4763:Stephen Cole Kleene (Jan 1943).
3327:
2516:is not defined for the argument
146:Primitive or "basic" functions:
4816:Introduction to Metamathematics
4756:
2460:
2396:
2368:
2362:
1565:
888:
882:
103:computational complexity theory
4736:
4727:
4625:
4565:
4508:
4429:
4345:
4309:
4289:
4271:
3726:and essentially the same ideas
3656:
3653:
3615:
3612:
3606:
3600:
3591:
3559:
3524:
3492:
3468:
3424:
3400:
3394:
3363:, a parallel is drawn between
3253:{\displaystyle S(z)*S(z)>x}
3241:
3235:
3226:
3220:
3193:
3187:
3167:{\displaystyle S(z)*S(z)>x}
3155:
3149:
3140:
3134:
3107:
3098:
3092:
3083:
3077:
3068:
3062:
3050:
3046:
3043:
3022:
2974:
2965:
2950:
2914:
2911:
2890:
2842:
2833:
2818:
2795:{\displaystyle (z+1)^{2}>x}
2777:
2764:
2708:
2676:
2667:
2635:
2555:
2523:
2503:
2497:
2447:
2409:
2349:
2311:
2284:
2270:
2238:
2235:
2229:
2198:
2192:
2164:
2126:
2060:
2025:
1987:
1975:
1952:
1920:
1897:
1859:
1824:
1789:
1751:
1739:
1726:
1691:
1685:
1679:
1669:
1637:
1624:
1586:
1527:
1515:
1483:
1439:
1411:
1379:
1341:
1338:
1306:
1284:
1252:
1239:
1213:
1181:
1159:
1127:
1097:
1065:
1035:
1032:
1000:
978:
946:
933:
924:
892:
843:
811:
781:
749:
727:
695:
664:
632:
523:
491:
310:
304:
229:
197:
1:
4339:10.1215/s0012-7094-36-00227-2
4264:
4225:
458:{\displaystyle 1\leq i\leq k}
137:primitive recursive functions
112:
73:primitive recursive functions
4259:Recursion (computer science)
4087:base step: f( 0, a ) = a = U
3801:( r, s, t, u, v, w, x ) = 13
3794:( r, s, t, u, v, w, x ) = 13
3732:
2753:can be defined as the least
1360:Primitive recursion operator
7:
4242:
4037:: Kleene uses the symbol "
3925:( r, s, t, u, v, w, x ) = t
3542:free variables there is an
2727:
622:): Given an m-ary function
407:): For all natural numbers
123:general recursive functions
10:
4970:
3933:: Kleene uses a bold-face
164:: For each natural number
33:partial recursive function
29:general recursive function
4358:Journal of Symbolic Logic
4326:Duke Mathematical Journal
396:{\displaystyle P_{i}^{k}}
4391:Proof outline on p.153:
4190:base step: h( 0, a ) = U
4063:induction step: h( y+1,
3840:: Kleene (1952) uses " U
3717:universal Turing machine
3304:total recursive function
3298:Total recursive function
611:{\displaystyle \circ \,}
55:(sometimes shortened to
53:total recursive function
4904:Computability and Logic
2607:{\displaystyle \simeq }
2509:{\displaystyle \mu (f)}
2204:{\displaystyle \mu (f)}
2095:{\displaystyle z<y.}
4683:
4657:
4608:
4582:
4548:
4525:
4491:
4455:
4412:
3730:
3709:
3663:
3532:
3476:
3408:
3407:{\displaystyle U(y)\!}
3254:
3200:
3168:
3114:
2921:
2796:
2715:
2608:
2565:
2510:
2469:
2205:
2172:
2096:
2067:
1959:
1904:
1839:
1491:
1419:
1348:
1223:
1104:
1045:
788:
678:and m k-ary functions
672:
612:
574:
459:
427:
397:
357:
269:
127:minimization operator
4954:Theory of computation
4684:
4658:
4609:
4583:
4549:
4526:
4492:
4456:
4413:
4353:Turing, Alan Mathison
4279:"Recursive Functions"
3721:
3710:
3664:
3533:
3477:
3409:
3255:
3201:
3169:
3115:
2922:
2797:
2716:
2609:
2566:
2511:
2470:
2206:
2173:
2107:Minimization operator
2097:
2068:
1960:
1905:
1840:
1492:
1420:
1349:
1224:
1105:
1046:
789:
673:
620:substitution operator
613:
575:
460:
428:
398:
358:
289:Successor function S:
270:
119:μ-recursive functions
4949:Computability theory
4666:
4617:
4591:
4557:
4534:
4500:
4464:
4421:
4395:
4237:McCarthy 91 function
3862:over the variables x
3699:
3553:
3486:
3418:
3388:
3308:total Turing machine
3260:holds. The negation
3214:
3178:
3128:
2947:
2806:
2761:
2629:
2598:
2520:
2491:
2219:
2186:
2120:
2077:
2073:are defined for all
1969:
1914:
1853:
1505:
1433:
1373:
1233:
1114:
1059:
802:
682:
626:
601:
596:Composition operator
589:domain of a function
473:
437:
411:
375:
298:
179:
69:Church–Turing thesis
61:computability theory
37:μ-recursive function
4839:. Springer-Verlag.
4833:Soare, R. (1999) .
4300:Recursive Functions
4035:Primitive Recursion
3962:If we are given h(
3378:normal form theorem
3372:Normal form theorem
3042:
3021:
2997:
2910:
2889:
2865:
2747:integer square root
1910:is defined only if
1576: is defined by
1110:is defined only if
490:
426:{\displaystyle i,k}
392:
370:Projection function
196:
151:Constant functions
4900:"6.2 Minimization"
4679:
4677:
4653:
4604:
4602:
4578:
4544:
4542:
4521:
4487:
4485:
4475:
4451:
4408:
4406:
4317:Kleene, Stephen C.
3809:Successor function
3746:is abbreviated as
3705:
3659:
3528:
3472:
3404:
3339:. You can help by
3250:
3196:
3164:
3110:
3028:
3007:
2983:
2917:
2896:
2875:
2851:
2792:
2711:
2604:
2561:
2506:
2465:
2463:
2201:
2168:
2092:
2063:
1955:
1900:
1835:
1833:
1487:
1415:
1344:
1219:
1100:
1041:
784:
668:
608:
570:
476:
455:
423:
393:
378:
353:
265:
182:
141:Ackermann function
107:complexity class R
93:The subset of all
77:Ackermann function
57:recursive function
21:mathematical logic
4855:Minsky, Marvin L.
4676:
4650:
4601:
4575:
4541:
4540:Turing computable
4518:
4484:
4474:
4448:
4405:
4187:( b, c, a )) = c'
4052:base step: h( 0,
3838:Identity function
3757:: Kleene uses " C
3755:Constant function
3708:{\displaystyle U}
3685:for the function
3357:
3356:
3271:encodes truth by
3124:if, and only if,
2400:
2366:
2307:
2302:
2116:+1)-ary function
1577:
1569:
1561:
1556:
1534:
1429:+2 -ary function
886:
875:
870:
848:
618:(also called the
555:
550:
528:
405:Identity function
403:(also called the
342:
337:
315:
261:
256:
234:
88:Markov algorithms
4961:
4917:
4896:Jeffrey, Richard
4879:register machine
4872:
4850:
4829:
4802:
4796:
4790:
4789:
4787:
4769:
4760:
4754:
4740:
4734:
4731:
4725:
4722:
4713:
4710:
4701:
4698:
4689:
4688:
4686:
4685:
4680:
4678:
4674:
4662:
4660:
4659:
4654:
4652:
4651:
4649:
4629:
4622:
4613:
4611:
4610:
4605:
4603:
4599:
4587:
4585:
4584:
4579:
4577:
4576:
4574:
4569:
4562:
4553:
4551:
4550:
4545:
4543:
4539:
4530:
4528:
4527:
4522:
4520:
4519:
4517:
4512:
4505:
4496:
4494:
4493:
4488:
4486:
4482:
4476:
4472:
4460:
4458:
4457:
4452:
4450:
4449:
4447:
4433:
4426:
4417:
4415:
4414:
4409:
4407:
4403:
4390:
4349:
4343:
4342:
4313:
4307:
4293:
4287:
4286:
4275:
4249:Recursion theory
4232:Fibonacci number
4198:
4197:
4186:
4185:
4178:g(b, c, a) = S(U
4174:
4173:
4162:
4161:
4133:
4132:
4121:
4120:
4107:
4106:
4095:
4094:
4000:
3999:
3944:
3943:
3924:
3923:
3915:
3914:
3896:
3895:
3883:
3882:
3861:
3860:
3848:
3847:
3793:
3792:
3765:
3764:
3714:
3712:
3711:
3706:
3668:
3666:
3665:
3660:
3652:
3651:
3633:
3632:
3590:
3589:
3571:
3570:
3537:
3535:
3534:
3529:
3523:
3522:
3504:
3503:
3481:
3479:
3478:
3473:
3467:
3466:
3448:
3447:
3413:
3411:
3410:
3405:
3352:
3349:
3331:
3324:
3282:
3278:
3274:
3270:
3267:is needed since
3266:
3259:
3257:
3256:
3251:
3209:
3205:
3203:
3202:
3197:
3173:
3171:
3170:
3165:
3123:
3119:
3117:
3116:
3111:
3041:
3036:
3020:
3015:
2996:
2991:
2941:logical negation
2938:
2934:
2930:
2926:
2924:
2923:
2918:
2909:
2904:
2888:
2883:
2864:
2859:
2801:
2799:
2798:
2793:
2785:
2784:
2756:
2752:
2720:
2718:
2717:
2712:
2707:
2706:
2688:
2687:
2666:
2665:
2647:
2646:
2613:
2611:
2610:
2605:
2580:
2570:
2568:
2567:
2562:
2554:
2553:
2535:
2534:
2515:
2513:
2512:
2507:
2486:
2474:
2472:
2471:
2466:
2464:
2446:
2445:
2427:
2426:
2401:
2398:
2367:
2364:
2348:
2347:
2329:
2328:
2305:
2304:
2303:
2301:
2300:
2288:
2281:
2269:
2268:
2250:
2249:
2210:
2208:
2207:
2202:
2177:
2175:
2174:
2169:
2163:
2162:
2144:
2143:
2111:
2101:
2099:
2098:
2093:
2072:
2070:
2069:
2064:
2059:
2058:
2040:
2039:
2024:
2023:
2005:
2004:
1964:
1962:
1961:
1956:
1951:
1950:
1932:
1931:
1909:
1907:
1906:
1901:
1896:
1895:
1877:
1876:
1849:This means that
1844:
1842:
1841:
1836:
1834:
1823:
1822:
1804:
1803:
1788:
1787:
1769:
1768:
1725:
1724:
1706:
1705:
1668:
1667:
1649:
1648:
1623:
1622:
1604:
1603:
1578:
1575:
1570:
1567:
1559:
1558:
1557:
1555:
1554:
1542:
1537:
1532:
1496:
1494:
1493:
1488:
1482:
1481:
1463:
1462:
1424:
1422:
1421:
1416:
1410:
1409:
1391:
1390:
1364:
1354:are all defined.
1353:
1351:
1350:
1345:
1337:
1336:
1318:
1317:
1305:
1304:
1283:
1282:
1264:
1263:
1251:
1250:
1228:
1226:
1225:
1220:
1212:
1211:
1193:
1192:
1180:
1179:
1158:
1157:
1139:
1138:
1126:
1125:
1109:
1107:
1106:
1101:
1096:
1095:
1077:
1076:
1055:This means that
1050:
1048:
1047:
1042:
1031:
1030:
1012:
1011:
999:
998:
977:
976:
958:
957:
945:
944:
923:
922:
904:
903:
887:
884:
873:
872:
871:
869:
868:
856:
851:
846:
842:
841:
823:
822:
793:
791:
790:
785:
780:
779:
761:
760:
748:
747:
726:
725:
707:
706:
694:
693:
677:
675:
674:
669:
663:
662:
644:
643:
617:
615:
614:
609:
579:
577:
576:
571:
565:
564:
553:
552:
551:
549:
548:
536:
531:
526:
522:
521:
503:
502:
489:
484:
464:
462:
461:
456:
432:
430:
429:
424:
402:
400:
399:
394:
391:
386:
362:
360:
359:
354:
340:
339:
338:
336:
335:
323:
318:
313:
274:
272:
271:
266:
259:
258:
257:
255:
254:
242:
237:
232:
228:
227:
209:
208:
195:
190:
171:
167:
162:
161:
160:
130:
100:
41:partial function
25:computer science
4969:
4968:
4964:
4963:
4962:
4960:
4959:
4958:
4939:
4938:
4925:
4920:
4914:
4869:
4847:
4826:
4812:Kleene, Stephen
4806:
4805:
4801:, pp. 189.
4797:
4793:
4767:
4761:
4757:
4741:
4737:
4732:
4728:
4723:
4716:
4711:
4704:
4699:
4692:
4672:
4667:
4664:
4663:
4630:
4623:
4621:
4620:
4618:
4615:
4614:
4597:
4592:
4589:
4588:
4570:
4563:
4561:
4560:
4558:
4555:
4554:
4537:
4535:
4532:
4531:
4513:
4506:
4504:
4503:
4501:
4498:
4497:
4480:
4470:
4465:
4462:
4461:
4434:
4427:
4425:
4424:
4422:
4419:
4418:
4401:
4396:
4393:
4392:
4371:10.2307/2268280
4350:
4346:
4314:
4310:
4294:
4290:
4277:
4276:
4272:
4267:
4245:
4228:
4210:He arrives at:
4196:
4193:
4192:
4191:
4184:
4181:
4180:
4179:
4175:( b, c, a ) = c
4172:
4169:
4168:
4167:
4160:
4157:
4156:
4155:
4131:
4128:
4127:
4126:
4119:
4116:
4115:
4114:
4105:
4102:
4101:
4100:
4093:
4090:
4089:
4088:
4067:) = g( y, h(y,
4008:
4004:
3998:
3995:
3994:
3993:
3977:
3969:
3956:
3952:
3942:
3939:
3938:
3937:
3922:
3919:
3918:
3917:
3913:
3910:
3909:
3908:
3904:
3894:
3891:
3890:
3889:
3881:
3878:
3877:
3876:
3869:
3865:
3859:
3856:
3855:
3854:
3852:
3846:
3843:
3842:
3841:
3829:
3825:
3821:
3800:
3791:
3788:
3787:
3786:
3773:
3763:
3760:
3759:
3758:
3745:
3741:
3735:
3700:
3697:
3696:
3647:
3643:
3628:
3624:
3585:
3581:
3566:
3562:
3554:
3551:
3550:
3518:
3514:
3499:
3495:
3487:
3484:
3483:
3462:
3458:
3443:
3439:
3419:
3416:
3415:
3389:
3386:
3385:
3374:
3365:Turing machines
3353:
3347:
3344:
3337:needs expansion
3322:
3313:Halting problem
3300:
3295:
3286:
3280:
3276:
3272:
3268:
3264:
3215:
3212:
3211:
3207:
3179:
3176:
3175:
3129:
3126:
3125:
3121:
3037:
3032:
3016:
3011:
2992:
2987:
2948:
2945:
2944:
2936:
2932:
2928:
2905:
2900:
2884:
2879:
2860:
2855:
2807:
2804:
2803:
2780:
2776:
2762:
2759:
2758:
2754:
2750:
2730:
2702:
2698:
2683:
2679:
2661:
2657:
2642:
2638:
2630:
2627:
2626:
2599:
2596:
2595:
2591:strong equality
2578:
2549:
2545:
2530:
2526:
2521:
2518:
2517:
2492:
2489:
2488:
2484:
2462:
2461:
2450:
2441:
2437:
2422:
2418:
2403:
2402:
2397:
2363:
2352:
2343:
2339:
2324:
2320:
2290:
2289:
2282:
2280:
2279:
2264:
2260:
2245:
2241:
2222:
2220:
2217:
2216:
2211:is defined by:
2187:
2184:
2183:
2158:
2154:
2139:
2135:
2121:
2118:
2117:
2109:
2078:
2075:
2074:
2054:
2050:
2035:
2031:
2019:
2015:
2000:
1996:
1970:
1967:
1966:
1946:
1942:
1927:
1923:
1915:
1912:
1911:
1891:
1887:
1872:
1868:
1854:
1851:
1850:
1832:
1831:
1818:
1814:
1799:
1795:
1783:
1779:
1764:
1760:
1729:
1720:
1716:
1701:
1697:
1673:
1672:
1663:
1659:
1644:
1640:
1627:
1618:
1614:
1599:
1595:
1580:
1579:
1574:
1566:
1544:
1543:
1538:
1536:
1535:
1530:
1508:
1506:
1503:
1502:
1477:
1473:
1458:
1454:
1434:
1431:
1430:
1405:
1401:
1386:
1382:
1374:
1371:
1370:
1362:
1332:
1328:
1313:
1309:
1300:
1296:
1278:
1274:
1259:
1255:
1246:
1242:
1234:
1231:
1230:
1207:
1203:
1188:
1184:
1175:
1171:
1153:
1149:
1134:
1130:
1121:
1117:
1115:
1112:
1111:
1091:
1087:
1072:
1068:
1060:
1057:
1056:
1026:
1022:
1007:
1003:
994:
990:
972:
968:
953:
949:
940:
936:
918:
914:
899:
895:
883:
858:
857:
852:
850:
849:
837:
833:
818:
814:
803:
800:
799:
775:
771:
756:
752:
743:
739:
721:
717:
702:
698:
689:
685:
683:
680:
679:
658:
654:
639:
635:
627:
624:
623:
602:
599:
598:
587:Operators (the
560:
556:
538:
537:
532:
530:
529:
517:
513:
498:
494:
485:
480:
474:
471:
470:
438:
435:
434:
412:
409:
408:
387:
382:
376:
373:
372:
325:
324:
319:
317:
316:
299:
296:
295:
244:
243:
238:
236:
235:
223:
219:
204:
200:
191:
186:
180:
177:
176:
169:
165:
159:
156:
155:
154:
152:
128:
115:
98:
84:lambda calculus
65:Turing machines
45:natural numbers
17:
12:
11:
5:
4967:
4957:
4956:
4951:
4937:
4936:
4931:
4924:
4923:External links
4921:
4919:
4918:
4912:
4888:Boolos, George
4883:
4882:
4874:
4873:
4867:
4851:
4845:
4830:
4824:
4807:
4804:
4803:
4791:
4755:
4735:
4726:
4714:
4702:
4690:
4671:
4648:
4645:
4642:
4639:
4636:
4633:
4627:
4596:
4573:
4567:
4516:
4510:
4479:
4469:
4446:
4443:
4440:
4437:
4431:
4400:
4365:(4): 153–163.
4344:
4333:(2): 340–352.
4308:
4302:, Sect.1.7: "
4288:
4269:
4268:
4266:
4263:
4262:
4261:
4256:
4251:
4244:
4241:
4240:
4239:
4234:
4227:
4224:
4223:
4222:
4221:
4220:
4208:
4207:
4206:
4205:
4201:
4200:
4194:
4188:
4182:
4176:
4170:
4164:
4158:
4152:
4140:
4139:
4138:
4137:
4136:
4135:
4129:
4123:
4117:
4110:
4109:
4103:
4097:
4091:
4079:
4078:
4077:
4076:
4061:
4047:
4046:
4031:
4030:
4029:
4028:
4013:
4012:
4011:
4010:
4006:
4002:
3996:
3975:
3967:
3959:
3958:
3954:
3950:
3940:
3927:
3926:
3920:
3911:
3905:
3902:
3892:
3879:
3872:
3871:
3867:
3863:
3857:
3850:
3844:
3834:
3833:
3832:
3831:
3827:
3823:
3819:
3813:
3812:
3805:
3804:
3803:
3802:
3798:
3795:
3789:
3780:
3779:
3771:
3761:
3743:
3739:
3734:
3731:
3704:
3671:
3670:
3658:
3655:
3650:
3646:
3642:
3639:
3636:
3631:
3627:
3623:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3599:
3596:
3593:
3588:
3584:
3580:
3577:
3574:
3569:
3565:
3561:
3558:
3526:
3521:
3517:
3513:
3510:
3507:
3502:
3498:
3494:
3491:
3470:
3465:
3461:
3457:
3454:
3451:
3446:
3442:
3438:
3435:
3432:
3429:
3426:
3423:
3402:
3399:
3396:
3393:
3373:
3370:
3355:
3354:
3334:
3332:
3321:
3318:
3299:
3296:
3294:
3293:
3290:
3285:
3284:
3249:
3246:
3243:
3240:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3195:
3192:
3189:
3186:
3183:
3163:
3160:
3157:
3154:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3109:
3106:
3103:
3100:
3097:
3094:
3091:
3088:
3085:
3082:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3048:
3045:
3040:
3035:
3031:
3027:
3024:
3019:
3014:
3010:
3006:
3003:
3000:
2995:
2990:
2986:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2916:
2913:
2908:
2903:
2899:
2895:
2892:
2887:
2882:
2878:
2874:
2871:
2868:
2863:
2858:
2854:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2791:
2788:
2783:
2779:
2775:
2772:
2769:
2766:
2742:
2729:
2726:
2722:
2721:
2710:
2705:
2701:
2697:
2694:
2691:
2686:
2682:
2678:
2675:
2672:
2669:
2664:
2660:
2656:
2653:
2650:
2645:
2641:
2637:
2634:
2603:
2560:
2557:
2552:
2548:
2544:
2541:
2538:
2533:
2529:
2525:
2505:
2502:
2499:
2496:
2480:
2479:
2478:
2477:
2476:
2475:
2459:
2456:
2453:
2451:
2449:
2444:
2440:
2436:
2433:
2430:
2425:
2421:
2417:
2414:
2411:
2408:
2405:
2404:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2361:
2358:
2355:
2353:
2351:
2346:
2342:
2338:
2335:
2332:
2327:
2323:
2319:
2316:
2313:
2310:
2299:
2296:
2293:
2286:
2278:
2275:
2272:
2267:
2263:
2259:
2256:
2253:
2248:
2244:
2240:
2237:
2234:
2231:
2228:
2225:
2224:
2200:
2197:
2194:
2191:
2182:-ary function
2166:
2161:
2157:
2153:
2150:
2147:
2142:
2138:
2134:
2131:
2128:
2125:
2104:
2103:
2102:
2091:
2088:
2085:
2082:
2062:
2057:
2053:
2049:
2046:
2043:
2038:
2034:
2030:
2027:
2022:
2018:
2014:
2011:
2008:
2003:
1999:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1954:
1949:
1945:
1941:
1938:
1935:
1930:
1926:
1922:
1919:
1899:
1894:
1890:
1886:
1883:
1880:
1875:
1871:
1867:
1864:
1861:
1858:
1847:
1846:
1845:
1830:
1826:
1821:
1817:
1813:
1810:
1807:
1802:
1798:
1794:
1791:
1786:
1782:
1778:
1775:
1772:
1767:
1763:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1730:
1728:
1723:
1719:
1715:
1712:
1709:
1704:
1700:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1674:
1671:
1666:
1662:
1658:
1655:
1652:
1647:
1643:
1639:
1636:
1633:
1630:
1628:
1626:
1621:
1617:
1613:
1610:
1607:
1602:
1598:
1594:
1591:
1588:
1585:
1582:
1581:
1573:
1564:
1553:
1550:
1547:
1541:
1531:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1510:
1485:
1480:
1476:
1472:
1469:
1466:
1461:
1457:
1453:
1450:
1447:
1444:
1441:
1438:
1413:
1408:
1404:
1400:
1397:
1394:
1389:
1385:
1381:
1378:
1369:-ary function
1357:
1356:
1355:
1343:
1340:
1335:
1331:
1327:
1324:
1321:
1316:
1312:
1308:
1303:
1299:
1295:
1292:
1289:
1286:
1281:
1277:
1273:
1270:
1267:
1262:
1258:
1254:
1249:
1245:
1241:
1238:
1218:
1215:
1210:
1206:
1202:
1199:
1196:
1191:
1187:
1183:
1178:
1174:
1170:
1167:
1164:
1161:
1156:
1152:
1148:
1145:
1142:
1137:
1133:
1129:
1124:
1120:
1099:
1094:
1090:
1086:
1083:
1080:
1075:
1071:
1067:
1064:
1053:
1052:
1051:
1040:
1037:
1034:
1029:
1025:
1021:
1018:
1015:
1010:
1006:
1002:
997:
993:
989:
986:
983:
980:
975:
971:
967:
964:
961:
956:
952:
948:
943:
939:
935:
932:
929:
926:
921:
917:
913:
910:
907:
902:
898:
894:
891:
881:
878:
867:
864:
861:
855:
845:
840:
836:
832:
829:
826:
821:
817:
813:
810:
807:
783:
778:
774:
770:
767:
764:
759:
755:
751:
746:
742:
738:
735:
732:
729:
724:
720:
716:
713:
710:
705:
701:
697:
692:
688:
666:
661:
657:
653:
650:
647:
642:
638:
634:
631:
606:
585:
584:
583:
582:
581:
580:
569:
563:
559:
547:
544:
541:
535:
525:
520:
516:
512:
509:
506:
501:
497:
493:
488:
483:
479:
454:
451:
448:
445:
442:
422:
419:
416:
390:
385:
381:
367:
366:
365:
364:
363:
351:
348:
345:
334:
331:
328:
322:
312:
309:
306:
303:
286:
285:
284:
277:
276:
275:
264:
253:
250:
247:
241:
231:
226:
222:
218:
215:
212:
207:
203:
199:
194:
189:
185:
157:
114:
111:
15:
9:
6:
4:
3:
2:
4966:
4955:
4952:
4950:
4947:
4946:
4944:
4935:
4932:
4930:
4927:
4926:
4915:
4913:9780521007580
4909:
4905:
4901:
4897:
4893:
4892:Burgess, John
4889:
4885:
4884:
4880:
4876:
4875:
4870:
4868:9780131654495
4864:
4860:
4856:
4852:
4848:
4846:9783540152996
4842:
4838:
4837:
4831:
4827:
4825:0-7204-2103-9
4821:
4817:
4813:
4809:
4808:
4800:
4795:
4786:
4781:
4777:
4773:
4766:
4759:
4753:
4749:
4745:
4739:
4730:
4721:
4719:
4709:
4707:
4697:
4695:
4669:
4646:
4643:
4640:
4637:
4634:
4631:
4594:
4571:
4514:
4477:
4467:
4444:
4441:
4438:
4435:
4398:
4388:
4384:
4380:
4376:
4372:
4368:
4364:
4360:
4359:
4354:
4348:
4340:
4336:
4332:
4328:
4327:
4322:
4318:
4312:
4305:
4301:
4297:
4292:
4284:
4280:
4274:
4270:
4260:
4257:
4255:
4252:
4250:
4247:
4246:
4238:
4235:
4233:
4230:
4229:
4219:
4215:
4214:
4213:
4212:
4211:
4203:
4202:
4189:
4177:
4165:
4153:
4150:
4149:
4148:
4147:
4146:
4144:
4124:
4112:
4111:
4098:
4086:
4085:
4084:
4083:
4081:
4080:
4074:
4070:
4066:
4062:
4059:
4055:
4051:
4050:
4049:
4048:
4044:
4040:
4036:
4033:
4032:
4026:
4022:
4018:
4017:
4015:
4014:
3992:
3988:
3984:
3983:
3981:
3973:
3965:
3961:
3960:
3948:
3936:
3932:
3929:
3928:
3906:
3900:
3887:
3874:
3873:
3839:
3836:
3835:
3822:a', where 1 =
3818:S(a) = a +1 =
3817:
3816:
3815:
3814:
3810:
3807:
3806:
3796:
3784:
3783:
3782:
3781:
3777:
3769:
3756:
3753:
3752:
3751:
3749:
3729:
3727:
3720:
3718:
3702:
3695:observes the
3694:
3690:
3688:
3684:
3680:
3677:is called an
3676:
3648:
3644:
3640:
3637:
3634:
3629:
3625:
3621:
3618:
3609:
3603:
3597:
3594:
3586:
3582:
3578:
3575:
3572:
3567:
3563:
3556:
3549:
3548:
3547:
3545:
3541:
3519:
3515:
3511:
3508:
3505:
3500:
3496:
3489:
3463:
3459:
3455:
3452:
3449:
3444:
3440:
3436:
3433:
3430:
3427:
3421:
3397:
3391:
3383:
3379:
3369:
3366:
3362:
3351:
3348:February 2010
3342:
3338:
3335:This section
3333:
3330:
3326:
3325:
3317:
3315:
3314:
3309:
3305:
3292:
3291:
3289:
3263:
3247:
3244:
3238:
3232:
3229:
3223:
3217:
3206:is the least
3190:
3184:
3181:
3174:holds. Hence
3161:
3158:
3152:
3146:
3143:
3137:
3131:
3104:
3101:
3095:
3089:
3086:
3080:
3074:
3065:
3059:
3056:
3053:
3038:
3033:
3029:
3025:
3017:
3012:
3008:
3004:
3001:
2998:
2993:
2988:
2984:
2980:
2977:
2971:
2968:
2962:
2959:
2956:
2953:
2942:
2906:
2901:
2897:
2893:
2885:
2880:
2876:
2872:
2869:
2866:
2861:
2856:
2852:
2848:
2845:
2839:
2836:
2830:
2827:
2824:
2821:
2815:
2812:
2809:
2789:
2786:
2781:
2773:
2770:
2767:
2748:
2744:
2743:
2741:
2737:
2735:
2725:
2703:
2699:
2695:
2692:
2689:
2684:
2680:
2673:
2670:
2662:
2658:
2654:
2651:
2648:
2643:
2639:
2632:
2625:
2624:
2623:
2621:
2617:
2601:
2593:
2592:
2586:
2584:
2576:
2571:
2558:
2550:
2546:
2542:
2539:
2536:
2531:
2527:
2500:
2494:
2457:
2454:
2452:
2442:
2438:
2434:
2431:
2428:
2423:
2419:
2415:
2412:
2406:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2359:
2356:
2354:
2344:
2340:
2336:
2333:
2330:
2325:
2321:
2317:
2314:
2308:
2276:
2273:
2265:
2261:
2257:
2254:
2251:
2246:
2242:
2232:
2226:
2215:
2214:
2213:
2212:
2195:
2189:
2181:
2159:
2155:
2151:
2148:
2145:
2140:
2136:
2132:
2129:
2123:
2115:
2108:
2105:
2089:
2086:
2083:
2080:
2055:
2051:
2047:
2044:
2041:
2036:
2032:
2028:
2020:
2016:
2012:
2009:
2006:
2001:
1997:
1993:
1990:
1984:
1981:
1978:
1972:
1947:
1943:
1939:
1936:
1933:
1928:
1924:
1917:
1892:
1888:
1884:
1881:
1878:
1873:
1869:
1865:
1862:
1856:
1848:
1828:
1819:
1815:
1811:
1808:
1805:
1800:
1796:
1792:
1784:
1780:
1776:
1773:
1770:
1765:
1761:
1757:
1754:
1748:
1745:
1742:
1736:
1733:
1731:
1721:
1717:
1713:
1710:
1707:
1702:
1698:
1694:
1688:
1682:
1676:
1664:
1660:
1656:
1653:
1650:
1645:
1641:
1634:
1631:
1629:
1619:
1615:
1611:
1608:
1605:
1600:
1596:
1592:
1589:
1583:
1571:
1562:
1539:
1524:
1521:
1518:
1512:
1501:
1500:
1499:
1498:
1478:
1474:
1470:
1467:
1464:
1459:
1455:
1451:
1448:
1445:
1442:
1436:
1428:
1406:
1402:
1398:
1395:
1392:
1387:
1383:
1376:
1368:
1361:
1358:
1333:
1329:
1325:
1322:
1319:
1314:
1310:
1301:
1297:
1293:
1290:
1287:
1279:
1275:
1271:
1268:
1265:
1260:
1256:
1247:
1243:
1236:
1216:
1208:
1204:
1200:
1197:
1194:
1189:
1185:
1176:
1172:
1168:
1165:
1162:
1154:
1150:
1146:
1143:
1140:
1135:
1131:
1122:
1118:
1092:
1088:
1084:
1081:
1078:
1073:
1069:
1062:
1054:
1038:
1027:
1023:
1019:
1016:
1013:
1008:
1004:
995:
991:
987:
984:
981:
973:
969:
965:
962:
959:
954:
950:
941:
937:
930:
927:
919:
915:
911:
908:
905:
900:
896:
889:
879:
876:
853:
838:
834:
830:
827:
824:
819:
815:
808:
805:
798:
797:
796:
795:
776:
772:
768:
765:
762:
757:
753:
744:
740:
736:
733:
730:
722:
718:
714:
711:
708:
703:
699:
690:
686:
659:
655:
651:
648:
645:
640:
636:
629:
621:
604:
597:
594:
593:
592:
590:
567:
561:
557:
533:
518:
514:
510:
507:
504:
499:
495:
486:
481:
477:
469:
468:
467:
466:
452:
449:
446:
443:
440:
420:
417:
414:
406:
388:
383:
379:
371:
368:
349:
346:
343:
320:
307:
301:
294:
293:
292:
291:
290:
287:
282:
281:zero function
278:
262:
239:
224:
220:
216:
213:
210:
205:
201:
192:
187:
183:
175:
174:
173:
172:
163:
149:
148:
147:
144:
142:
138:
133:
131:
124:
120:
110:
108:
104:
96:
91:
89:
85:
80:
78:
74:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
4903:
4858:
4835:
4815:
4794:
4778:(1): 41–73.
4775:
4771:
4758:
4738:
4729:
4362:
4356:
4347:
4330:
4324:
4311:
4303:
4291:
4282:
4273:
4217:
4209:
4142:
4141:
4108:( b, c, a ))
4072:
4068:
4064:
4057:
4053:
4042:
4038:
4034:
4024:
4020:
3990:
3986:
3979:
3971:
3963:
3946:
3934:
3930:
3898:
3885:
3837:
3808:
3775:
3767:
3754:
3747:
3736:
3725:
3722:
3691:
3686:
3683:Gödel number
3682:
3678:
3674:
3672:
3543:
3539:
3381:
3375:
3358:
3345:
3341:adding to it
3336:
3311:
3303:
3301:
3287:
2738:
2731:
2723:
2619:
2615:
2589:
2587:
2574:
2572:
2481:
2179:
2113:
2106:
1426:
1366:
1365:: Given the
1359:
619:
595:
586:
404:
369:
288:
280:
150:
145:
134:
122:
118:
116:
101:is known in
94:
92:
81:
56:
52:
36:
32:
28:
18:
4799:Minsky 1972
4742:defined in
3830:0 ' ', etc.
3673:The number
2112:: Given a (
4943:Categories
4675:-definable
4600:-recursive
4483:-definable
4404:-definable
4265:References
4045:)". Given:
3974:), ... , f
3797:e.g. const
3546:such that
3279:seeks for
3210:such that
2757:such that
2577:functions
433:such that
168:and every
113:Definition
49:formal one
4857:(1972) .
4814:(1991) .
4670:λ
4626:⟹
4595:μ
4566:⟹
4509:⟹
4468:λ
4430:⟹
4399:λ
4254:Recursion
4151:S(a) = a'
4122:(a), S }
4005:, ... , f
3733:Symbolism
3638:…
3604:μ
3595:≃
3576:…
3509:…
3453:…
3230:∗
3185:
3144:∗
3087:∗
3072:¬
3005:∘
2981:∘
2972:∘
2963:∘
2957:∘
2873:∘
2849:∘
2840:∘
2831:∘
2825:∘
2816:μ
2693:…
2671:≃
2652:…
2602:≃
2594:relation
2540:…
2495:μ
2432:…
2391:−
2382:…
2334:…
2285:⟺
2255:…
2227:μ
2190:μ
2149:…
2045:…
2010:…
1937:…
1882:…
1809:…
1774:…
1711:…
1654:…
1609:…
1513:ρ
1468:…
1396:…
1323:…
1291:…
1269:…
1198:…
1166:…
1144:…
1082:…
1017:…
985:…
963:…
909:…
828:…
809:∘
766:…
734:…
712:…
649:…
605:∘
508:…
450:≤
444:≤
214:…
4898:(2002).
4319:(1936).
4298:, Entry
4243:See also
4226:Examples
4134:(a), S }
3778:) = n ":
3742:, ..., x
3275:, while
2927:, where
2728:Examples
2622:so that
4387:2317046
4379:2268280
4163:(a) = a
4143:Example
3966:)= g( f
3826:0', 2 =
3359:In the
3262:junctor
105:as the
4910:
4865:
4843:
4822:
4750:, and
4385:
4377:
4216:a+b =
4060:), and
4056:)= f(
4023:)= Cn(
3907:e.g. U
3888:) = id
3785:e.g. C
3693:Minsky
3277:μ
2935:, and
2306:
2178:, the
2110:μ
1560:
1533:
1363:ρ
874:
847:
554:
527:
341:
314:
260:
233:
59:). In
4768:(PDF)
4383:S2CID
4375:JSTOR
4125:Pr{ U
4113:R { U
4001:(g, f
3901:) = x
3679:index
3538:with
3182:Isqrt
2810:Isqrt
2583:below
2575:total
885:where
99:{0,1}
95:total
43:from
39:is a
35:, or
4908:ISBN
4863:ISBN
4841:ISBN
4820:ISBN
3989:) =
3982:) )
3916:= id
3866:to x
3414:and
3245:>
3159:>
3102:>
2939:are
2787:>
2745:The
2618:and
2588:The
2357:>
2084:<
1965:and
1425:and
1229:and
121:(or
117:The
27:, a
23:and
4780:doi
4572:161
4515:160
4367:doi
4335:doi
4199:(a)
4096:(a)
3828:def
3824:def
3820:def
3681:or
3343:.
3265:Not
3120:is
2969:Mul
2954:Not
2937:Mul
2929:Not
2837:Mul
2822:Not
2749:of
2399:and
2365:for
19:In
4945::
4902:.
4894:;
4890:;
4776:53
4774:.
4770:.
4746:,
4717:^
4705:^
4693:^
4381:.
4373:.
4361:.
4329:.
4323:.
4281:.
4071:),
4021:x'
4019:h(
3985:h(
3957:":
3897:(
3884:(
3799:13
3790:13
3774:(
3750::
3719::
3376:A
3316:.
3269:Gt
2960:Gt
2933:Gt
2931:,
2828:Gt
2736:.
1497::
794::
465::
132:.
109:.
90:.
79:.
31:,
4916:.
4871:.
4849:.
4828:.
4788:.
4782::
4647:e
4644:n
4641:e
4638:e
4635:l
4632:K
4478:K
4473:-
4445:v
4442:i
4439:r
4436:t
4389:.
4369::
4363:2
4341:.
4337::
4331:2
4306:"
4218:R
4195:1
4183:2
4171:2
4166:U
4159:1
4154:U
4130:1
4118:1
4104:2
4092:1
4075:)
4073:x
4069:x
4065:x
4058:x
4054:x
4043:x
4039:R
4027:)
4025:x
4009:)
4007:m
4003:1
3997:m
3991:S
3987:x
3980:x
3978:(
3976:m
3972:x
3970:(
3968:1
3964:x
3955:n
3951:m
3947:!
3941:n
3935:S
3921:3
3912:3
3903:i
3899:x
3893:i
3886:x
3880:i
3875:U
3870::
3868:n
3864:1
3858:i
3851:i
3845:i
3776:x
3772:n
3768:x
3766:(
3762:q
3748:x
3744:n
3740:1
3738:x
3703:U
3687:f
3675:e
3669:.
3657:)
3654:)
3649:k
3645:x
3641:,
3635:,
3630:1
3626:x
3622:,
3619:e
3616:(
3613:)
3610:T
3607:(
3601:(
3598:U
3592:)
3587:k
3583:x
3579:,
3573:,
3568:1
3564:x
3560:(
3557:f
3544:e
3540:k
3525:)
3520:k
3516:x
3512:,
3506:,
3501:1
3497:x
3493:(
3490:f
3469:)
3464:k
3460:x
3456:,
3450:,
3445:1
3441:x
3437:,
3434:e
3431:,
3428:y
3425:(
3422:T
3401:)
3398:y
3395:(
3392:U
3382:k
3350:)
3346:(
3283:.
3281:0
3273:1
3248:x
3242:)
3239:z
3236:(
3233:S
3227:)
3224:z
3221:(
3218:S
3208:z
3194:)
3191:x
3188:(
3162:x
3156:)
3153:z
3150:(
3147:S
3141:)
3138:z
3135:(
3132:S
3122:0
3108:)
3105:x
3099:)
3096:z
3093:(
3090:S
3084:)
3081:z
3078:(
3075:S
3069:(
3066:=
3063:)
3060:x
3057:,
3054:z
3051:(
3047:)
3044:)
3039:2
3034:2
3030:P
3026:,
3023:)
3018:2
3013:1
3009:P
3002:S
2999:,
2994:2
2989:1
2985:P
2978:S
2975:(
2966:(
2951:(
2915:)
2912:)
2907:2
2902:2
2898:P
2894:,
2891:)
2886:2
2881:1
2877:P
2870:S
2867:,
2862:2
2857:1
2853:P
2846:S
2843:(
2834:(
2819:(
2813:=
2790:x
2782:2
2778:)
2774:1
2771:+
2768:z
2765:(
2755:z
2751:x
2709:)
2704:l
2700:x
2696:,
2690:,
2685:1
2681:x
2677:(
2674:g
2668:)
2663:k
2659:x
2655:,
2649:,
2644:1
2640:x
2636:(
2633:f
2620:g
2616:f
2579:f
2559:.
2556:)
2551:k
2547:x
2543:,
2537:,
2532:1
2528:x
2524:(
2504:)
2501:f
2498:(
2485:f
2458:0
2455:=
2448:)
2443:k
2439:x
2435:,
2429:,
2424:1
2420:x
2416:,
2413:z
2410:(
2407:f
2394:1
2388:z
2385:,
2379:,
2376:0
2373:=
2370:i
2360:0
2350:)
2345:k
2341:x
2337:,
2331:,
2326:1
2322:x
2318:,
2315:i
2312:(
2309:f
2298:f
2295:e
2292:d
2277:z
2274:=
2271:)
2266:k
2262:x
2258:,
2252:,
2247:1
2243:x
2239:(
2236:)
2233:f
2230:(
2199:)
2196:f
2193:(
2180:k
2165:)
2160:k
2156:x
2152:,
2146:,
2141:1
2137:x
2133:,
2130:y
2127:(
2124:f
2114:k
2090:.
2087:y
2081:z
2061:)
2056:k
2052:x
2048:,
2042:,
2037:1
2033:x
2029:,
2026:)
2021:k
2017:x
2013:,
2007:,
2002:1
1998:x
1994:,
1991:z
1988:(
1985:f
1982:,
1979:z
1976:(
1973:h
1953:)
1948:k
1944:x
1940:,
1934:,
1929:1
1925:x
1921:(
1918:g
1898:)
1893:k
1889:x
1885:,
1879:,
1874:1
1870:x
1866:,
1863:y
1860:(
1857:f
1829:.
1825:)
1820:k
1816:x
1812:,
1806:,
1801:1
1797:x
1793:,
1790:)
1785:k
1781:x
1777:,
1771:,
1766:1
1762:x
1758:,
1755:y
1752:(
1749:f
1746:,
1743:y
1740:(
1737:h
1734:=
1727:)
1722:k
1718:x
1714:,
1708:,
1703:1
1699:x
1695:,
1692:)
1689:y
1686:(
1683:S
1680:(
1677:f
1670:)
1665:k
1661:x
1657:,
1651:,
1646:1
1642:x
1638:(
1635:g
1632:=
1625:)
1620:k
1616:x
1612:,
1606:,
1601:1
1597:x
1593:,
1590:0
1587:(
1584:f
1572:f
1563:f
1552:f
1549:e
1546:d
1540:=
1528:)
1525:h
1522:,
1519:g
1516:(
1484:)
1479:k
1475:x
1471:,
1465:,
1460:1
1456:x
1452:,
1449:z
1446:,
1443:y
1440:(
1437:h
1427:k
1412:)
1407:k
1403:x
1399:,
1393:,
1388:1
1384:x
1380:(
1377:g
1367:k
1342:)
1339:)
1334:k
1330:x
1326:,
1320:,
1315:1
1311:x
1307:(
1302:m
1298:g
1294:,
1288:,
1285:)
1280:k
1276:x
1272:,
1266:,
1261:1
1257:x
1253:(
1248:1
1244:g
1240:(
1237:h
1217:,
1214:)
1209:k
1205:x
1201:,
1195:,
1190:1
1186:x
1182:(
1177:m
1173:g
1169:,
1163:,
1160:)
1155:k
1151:x
1147:,
1141:,
1136:1
1132:x
1128:(
1123:1
1119:g
1098:)
1093:k
1089:x
1085:,
1079:,
1074:1
1070:x
1066:(
1063:f
1039:.
1036:)
1033:)
1028:k
1024:x
1020:,
1014:,
1009:1
1005:x
1001:(
996:m
992:g
988:,
982:,
979:)
974:k
970:x
966:,
960:,
955:1
951:x
947:(
942:1
938:g
934:(
931:h
928:=
925:)
920:k
916:x
912:,
906:,
901:1
897:x
893:(
890:f
880:,
877:f
866:f
863:e
860:d
854:=
844:)
839:m
835:g
831:,
825:,
820:1
816:g
812:(
806:h
782:)
777:k
773:x
769:,
763:,
758:1
754:x
750:(
745:m
741:g
737:,
731:,
728:)
723:k
719:x
715:,
709:,
704:1
700:x
696:(
691:1
687:g
665:)
660:m
656:x
652:,
646:,
641:1
637:x
633:(
630:h
568:.
562:i
558:x
546:f
543:e
540:d
534:=
524:)
519:k
515:x
511:,
505:,
500:1
496:x
492:(
487:k
482:i
478:P
453:k
447:i
441:1
421:k
418:,
415:i
389:k
384:i
380:P
350:1
347:+
344:x
333:f
330:e
327:d
321:=
311:)
308:x
305:(
302:S
263:n
252:f
249:e
246:d
240:=
230:)
225:k
221:x
217:,
211:,
206:1
202:x
198:(
193:k
188:n
184:C
170:k
166:n
158:n
153:C
129:μ
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
