A numbering of a set is a surjectivepartial function from to S (Ershov 1999:477). The value of a numbering ν at a number i (if defined) is often written νi instead of the usual .
Examples of numberings include:
The set of all finite subsets of has a numbering , defined so that and so that, for each finite nonempty set , where (Ershov 1999:477). This numbering is a (partial) bijection.
A fixed Gödel numbering of the computable partial functions can be used to define a numbering W of the recursively enumerable sets, by letting by W(i) be the domain of φi. This numbering will be surjective (like all numberings) but not injective: there will be distinct numbers that map to the same recursively enumerable set under W.
Types of numberingsedit
A numbering is total if it is a total function. If the domain of a partial numbering is recursively enumerable then there always exists an equivalent total numbering (equivalence of numberings is defined below).
A numbering η is decidable if the set is a decidable set.
A numbering η is single-valued if η(x) = η(y) if and only if x=y; in other words if η is an injective function. A single-valued numbering of the set of partial computable functions is called a Friedberg numbering.
Comparison of numberingsedit
There is a preorder on the set of all numberings. Let and be two numberings. Then is reducible to , written , if
If and then is equivalent to ; this is written .
Computable numberingsedit
When the objects of the set S being numbered are sufficiently "constructive", it is common to look at numberings that can be effectively decoded (Ershov 1999:486). For example, if S consists of recursively enumerable sets, the numbering η is computable if the set of pairs (x,y) where y ∈ η(x) is recursively enumerable. Similarly, a numbering g of partial functions is computable if the relation R(x,y,z) = "[g(x)](y) = z" is partial recursive (Ershov 1999:487).
A computable numbering is called principal if every computable numbering of the same set is reducible to it. Both the set of all recursively enumerable subsets of and the set of all partial computable functions have principle numberings (Ershov 1999:487). A principle numbering of the set of partial recursive functions is known as an admissible numbering in the literature.
^"Computability Theory - an overview | ScienceDirect Topics". www.sciencedirect.com. Retrieved 2021-01-19.
Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.
V.A. Uspenskiĭ, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer.
November 17, 2023
numbering, computability, theory, computability, theory, numbering, assignment, natural, numbers, objects, such, functions, rational, numbers, graphs, words, some, formal, language, numbering, used, transfer, idea, computability, related, concepts, which, orig. In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions rational numbers graphs or words in some formal language A numbering can be used to transfer the idea of computability 1 and related concepts which are originally defined on the natural numbers using computable functions to these different types of objects Common examples of numberings include Godel numberings in first order logic the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions Contents 1 Definition and examples 2 Types of numberings 3 Comparison of numberings 4 Computable numberings 5 See also 6 ReferencesDefinition and examples editA numbering of a set S displaystyle S nbsp is a surjective partial function from N displaystyle mathbb N nbsp to S Ershov 1999 477 The value of a numbering n at a number i if defined is often written ni instead of the usual n i displaystyle nu i nbsp Examples of numberings include The set of all finite subsets of N displaystyle mathbb N nbsp has a numbering g displaystyle gamma nbsp defined so that g 0 displaystyle gamma 0 emptyset nbsp and so that for each finite nonempty set A a 0 a k displaystyle A a 0 ldots a k nbsp g n A A displaystyle gamma n A A nbsp where n A i k 2 a i displaystyle n A sum i leq k 2 a i nbsp Ershov 1999 477 This numbering is a partial bijection A fixed Godel numbering f i displaystyle varphi i nbsp of the computable partial functions can be used to define a numbering W of the recursively enumerable sets by letting by W i be the domain of fi This numbering will be surjective like all numberings but not injective there will be distinct numbers that map to the same recursively enumerable set under W Types of numberings editA numbering is total if it is a total function If the domain of a partial numbering is recursively enumerable then there always exists an equivalent total numbering equivalence of numberings is defined below A numbering h is decidable if the set x y h x h y displaystyle x y eta x eta y nbsp is a decidable set A numbering h is single valued if h x h y if and only if x y in other words if h is an injective function A single valued numbering of the set of partial computable functions is called a Friedberg numbering Comparison of numberings editThere is a preorder on the set of all numberings Let n 1 N S displaystyle nu 1 mathbb N rightharpoonup S nbsp and n 2 N S displaystyle nu 2 mathbb N rightharpoonup S nbsp be two numberings Then n 1 displaystyle nu 1 nbsp is reducible to n 2 displaystyle nu 2 nbsp written n 1 n 2 displaystyle nu 1 leq nu 2 nbsp if f P 1 i D o m a i n n 1 n 1 i n 2 f i displaystyle exists f in mathbf P 1 forall i in mathrm Domain nu 1 nu 1 i nu 2 circ f i nbsp If n 1 n 2 displaystyle nu 1 leq nu 2 nbsp and n 1 n 2 displaystyle nu 1 geq nu 2 nbsp then n 1 displaystyle nu 1 nbsp is equivalent to n 2 displaystyle nu 2 nbsp this is written n 1 n 2 displaystyle nu 1 equiv nu 2 nbsp Computable numberings editWhen the objects of the set S being numbered are sufficiently constructive it is common to look at numberings that can be effectively decoded Ershov 1999 486 For example if S consists of recursively enumerable sets the numbering h is computable if the set of pairs x y where y h x is recursively enumerable Similarly a numbering g of partial functions is computable if the relation R x y z g x y z is partial recursive Ershov 1999 487 A computable numbering is called principal if every computable numbering of the same set is reducible to it Both the set of all recursively enumerable subsets of N displaystyle mathbb N nbsp and the set of all partial computable functions have principle numberings Ershov 1999 487 A principle numbering of the set of partial recursive functions is known as an admissible numbering in the literature See also editComplete numbering Cylindrification Godel numbering Description numberReferences edit Computability Theory an overview ScienceDirect Topics www sciencedirect com Retrieved 2021 01 19 Y L Ershov 1999 Theory of numberings Handbook of Computability Theory Elsevier pp 473 506 V A Uspenskiĭ A L Semenov 1993 Algorithms Main Ideas and Applications Springer Retrieved from https en wikipedia org w index php title Numbering computability theory amp oldid 1075402104, wikipedia, wiki, book, books, library,