Kleene numbering

E446862

concept in computability theory mathematical concept numbering of partial recursive functions

Kleene numbering is a method in computability theory for effectively assigning natural numbers to partial recursive functions, refining Gödel numbering to study algorithmic properties of functions.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Kleene’s recursion theorem	1

Statements (43)

Predicate	Object
instanceOf	concept in computability theory ⓘ mathematical concept ⓘ numbering of partial recursive functions ⓘ
assumption	the set of partial recursive functions is countable ⓘ
codomain	partial recursive functions ⓘ
context	arithmetization of syntax and computation ⓘ classical recursion theory ⓘ
contrastsWith	non-effective or arbitrary enumerations of functions ⓘ
domain	natural numbers ⓘ
enables	construction of diagonal functions and fixed-point arguments ⓘ definition of computably enumerable sets via indices of partial recursive functions ⓘ definition of many-one and Turing reducibility using indices ⓘ
field	computability theory ⓘ mathematical logic ⓘ theoretical computer science ⓘ
formalizes	the idea of indexing algorithms by natural numbers ⓘ
hasCharacteristic	indices are called Gödel numbers or program numbers ⓘ
historicalDevelopment	introduced in the development of recursion theory by Stephen Cole Kleene in the 20th century ⓘ
implies	existence of an effective enumeration of partial recursive functions ⓘ
isPartOf	the standard framework of classical computability theory ⓘ
namedAfter	Stephen Cole Kleene NERFINISHED ⓘ
property	allows uniform enumeration of partial recursive functions ⓘ is effective (computable) as a mapping from indices to functions ⓘ is surjective onto the class of partial recursive functions ⓘ
purpose	to effectively assign natural numbers to partial recursive functions ⓘ to study algorithmic properties of partial recursive functions ⓘ
refines	Gödel numbering ⓘ
relatedTo	Gödel numbering ⓘ Kleene normal form theorem NERFINISHED ⓘ acceptable numbering ⓘ effective numbering ⓘ partial recursive function ⓘ recursive function theory ⓘ s-m-n theorem NERFINISHED ⓘ universal partial recursive function ⓘ
requires	a fixed effective coding of finite sequences of natural numbers ⓘ a fixed formalism for defining partial recursive functions ⓘ
supports	proofs of universality and simulation theorems in recursion theory ⓘ
usedFor	defining acceptable programming systems ⓘ defining universal partial recursive functions ⓘ formalizing the notion of algorithm in recursion theory ⓘ proving recursion-theoretic invariance results ⓘ studying reducibility and degrees of unsolvability ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Gödel numbering → relatedConcept → Kleene numbering ⓘ

Stephen Kleene → knownFor → Kleene numbering ⓘ

this entity surface form: Kleene’s recursion theorem