From Wikipedia, the free encyclopedia
In computability theory, the assignment of natural numbers to a set of objects
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 Gödel numberings in first-order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions.
Definition and examples[edit]A numbering of a set S {\displaystyle S} is a surjective partial function from N {\displaystyle \mathbb {N} } to S (Ershov 1999:477). The value of a numbering ν at a number i (if defined) is often written νi instead of the usual ν ( i ) {\displaystyle \nu (i)\!} .
Examples of numberings include:
Types of numberings[edit]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 { ( x , y ) : η ( x ) = η ( y ) } {\displaystyle \{(x,y):\eta (x)=\eta (y)\}} 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 numberings[edit]There is a preorder on the set of all numberings. Let ν 1 : N ⇀ S {\displaystyle \nu _{1}:\mathbb {N} \rightharpoonup S} and ν 2 : N ⇀ S {\displaystyle \nu _{2}:\mathbb {N} \rightharpoonup S} be two numberings. Then ν 1 {\displaystyle \nu _{1}} is reducible to ν 2 {\displaystyle \nu _{2}} , written ν 1 ≤ ν 2 {\displaystyle \nu _{1}\leq \nu _{2}} , if
If ν 1 ≤ ν 2 {\displaystyle \nu _{1}\leq \nu _{2}} and ν 1 ≥ ν 2 {\displaystyle \nu _{1}\geq \nu _{2}} then ν 1 {\displaystyle \nu _{1}} is equivalent to ν 2 {\displaystyle \nu _{2}} ; this is written ν 1 ≡ ν 2 {\displaystyle \nu _{1}\equiv \nu _{2}} .
Computable numberings[edit]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 N {\displaystyle \mathbb {N} } 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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4