Revision #632 → #1487 · back to history
addedPrimitive recursive function (informal)c860791776b1
addedStrict subset of total general recursive functions0c575805b1c1
addedTime-complexity bound criterionc9ba80fc5365
addedPrimitive recursive function arity3c6d0782478a
addedConstant functions (basic)32cb6cdae42b
addedSuccessor function (basic)d22d76e0b7a7
addedProjection functions (basic)0c3adc51971d
addedComposition operator0290388bcf44
addedPrimitive recursion operator41148a9c0ec9
addedClass of primitive recursive functions286b15573412
addedVector-valued primitive recursive functionc0f1d2867fe1
addedConstant unary function exampledcd45dfbc8a8
addedZero-ary constant exampleb69bf8d7552c
addedIdentity function exampleb7157505f2fc
addedLeft and right projection examplebdf968432855
addedAdd-2 function example21aa3babfd89
addedConstants as compositionsa2b09f5706ae
addedAddition functionb7b9e018810b
addedDoubling function482c27fd3314
addedMultiplication functionec84ca47abaf
addedPredecessor function8c36883a6be7
addedTruncated subtraction (monus)1b3e1a3911c9
addedIdentifying predicates with numeric functions6ccd72051529
addedIs-zero predicateddf03a1eba31
addedLess-or-equal predicate7b8a39458d4d
addedGreater-or-equal predicate6b33e372dc0a
addedIf-then-else operator8a86af4b7c8a
addedLogical conjunction1219920ac6dc
addedDisjunction and negation24077e032dc0
addedEquality predicatea2e4c723ca2d
addedLess-than and greater-than predicates0a7935137f43
addedExponentiation and primality are primitive recursivefa04c2ff4568
addedCase function is primitive recursive7c1e430ac516
addedExtension via Gödel numberings532ec777df66
addedInteger arithmetic operations primitive recursivebf3e48419bab
addedRational field operations primitive recursive5e5bb8ecdcc9
addedExponentiation04a43d6bb336
addedFactorialaf4bf235be51
addedPredecessor / decrementb4f5ea56980e
addedProper subtractiona46039ab9da4
addedMinimum and Maximum50cecf6247a9
addedAbsolute difference37438553e04f
addedSignum and its negationa0fb90321a84
addedDivisibility2b32731589ce
addedRemainder / MOD270d2d15cd02
addedPrimality predicate72a3da04ca73
addedi+1th primebb2263421724
addedExponent of prime in numberd168cf83b507
addedLength (number of nonzero exponents)49391609296f
addedInteger logarithm7d171d82b62a
addedExplicit definition closure (#A)71dcd9521f02
addedBounded sum and product (#B)f534d9a48cd0
addedSubstitution into predicate (#C)94788df8f506
addedLogical connectives of predicates (#D)409b9f4635e3
addedBounded quantifiers and minimization (#E)e2526c662387
addedBounded mu-operatorb1ec51869bb1
addedDefinition by cases (#F)a8c02fd83470
addedCourse-of-values recursion (#G)dd4c8290e90a
addedPartial recursive functionb91652eaa599
addedTuring-machine characterization of partial recursivecf722a396ec1
addedTotal recursive function81db11b548d1
addedPrimitive recursive implies total recursivee91a9d9062bf
addedAckermann function not primitive recursive1bac99d261a8
addedAckermann-bound characterizationbd090368e123
addedPrimitive recursive set is recursively enumerable5fb09481d5d6
addedEncoding multi-arg as unary via pairingf140df23ee45
addedEnumerator f is not primitive recursive04907a0eff43
addedNot the largest r.e. subsetd651c7f67822
addedProvably total but converse fails08a2d023dc64
addedNot all total computable functions are primitive recursivec54823cbb04f
addedEvaluator function not primitive recursive52fe943c808d
addedDiagonal Ackermann m to A(m,m)db96ac78598e
addedParis–Harrington functionc539623c1443
addedSudan functiond0e2e1ff6efb
addedGoodstein function5ca2087fcdae
addedSingle zero function alternativec7a45e3bbdf6
addedIteration ruleaaf74d3ce6ca
addedIteration rule generates all PR functions9f7cfb932576
addedPure recursion rule3d302bc7238e
addedPure recursion suffices (Gladstone)d0a308f7ae5d
addedPure iteration rule suffices680d84a29fd9
addedPure iteration without parameters (Severin)7d7e4e0b73d4
addedCourse-of-values recursion gives PR functions8ea5dfaebdab
addedMutual recursion gives PR functions9d67b100bcb2
addedLOOP language equals PR functions6cc7befbf5db
addedPrimitive recursive programming language3a0cb535a518
addedLOOP computing powerf1db08804b33
addedPR computation always haltse335ea07d2ff
addedHalting problem undecidable for general recursive65871486bcdf
addedPrimitive recursive arithmetic (PRA)ffe4b829d9ce
addedPRA weaker than Peano arithmetic811a5d7703d6
addedGödel incompleteness formalized in PRAda6bc31ae07d
addedPR functions carry out syntactic transformations49bc6169e896
addedFinitistic consistency proof0b03e601c43f
addedSufficient condition for finitistic proof0f636ae6bc00