Numbering (computability theory)

<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a> a numbering is the assignment of <a href="/facts/Natural_number/u65og8JE">natural numbers</a> to a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of objects such as <a href="/facts/Function_(mathematics)/CdReEKCh">functions</a>, <a href="/facts/Rational_number/VJQmyY05">rational numbers</a>, <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a>, or words in some <a href="/facts/Formal_language/crDTyP8q">formal language</a>. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using <a href="/facts/Computable_function/dzwBlLGn">computable functions</a>, to these different types of objects.
</p><p>Common examples of numberings include <a href="/facts/G%25C3%25B6del_numbering/36BpTK1g">Gödel numberings</a> in <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>, the <a href="/facts/Description_number/vac5wCWu">description numbers</a> that arise from <a href="/facts/Universal_Turing_machine/2klpb1qQ">universal Turing machines</a> and <a href="/facts/Admissible_numbering/cXveEfhJ">admissible numberings</a> of the set of partial computable functions.
</p>

Numbering (computability theory) open-in-new

Numbering (computability theory)