Numbering (computability theory)

Short description: 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.

## Contents

* 1 Definition and examples
* 2 Types of numberings
* 3 Comparison of numberings
* 4 Computable numberings
* 5 See also
* 6 References

## Definition and examples

A numbering of a set S is a surjective partial 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 ν(i).

Examples of numberings include:

* The set of all finite subsets of ℕ has a numbering γ , defined so that γ(0)=∅ and so that, for each finite nonempty set A={a0,…,ak}, γ(nA)=A where nA=∑i≤k2ai (Ershov 1999:477). This numbering is a (partial) bijection.
* A fixed Gödel numbering φi 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 numberings

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)} 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

There is a preorder on the set of all numberings. Let ν1:ℕ⇀S and ν2:ℕ⇀S be two numberings. Then ν1 is reducible to ν2, written ν1≤ν2, if

∃f∈𝐏(1)∀i∈Domain(ν1):ν1(i)=ν2∘f(i).

If ν1≤ν2 and ν1≥ν2 then ν1 is equivalent to ν2; this is written ν1≡ν2.

## Computable numberings

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.

## See also

* Complete numbering
* Cylindrification
* Gödel numbering
* Description number

## References

1. ↑ "Computability Theory - an overview | ScienceDirect Topics". https://www.sciencedirect.com/topics/mathematics/computability-theory.

* 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Numbering (computability theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Numbering_(computability_theory)&oldid=231315"