Numbering Computability Theory Article Index for
Numbering 		Website Links For
Numbering 		 

Information About

Numbering Computability Theory
  CATEGORIES ABOUT NUMBERING COMPUTABILITY THEORY
   
theory of computation
   
recursion theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



In Computability Theory a numbering is the assignment of Natural Number s to a Set of objects like Rational Number s, Graph s or words in some Language . A numbering can be used to transfer the computability concept, which is strictly defined on the natural numbers using Computable Function s, to different objects.

Important numberings are the Gödel Numbering of the terms in First-order Predicate Calculus and numberings of the set of computable functions which can be used to apply results of computability theory on the set of computable functions itself.


DEFINITION

A numbering of a set S \! is a Partial Surjective Function
:
u: \subseteq \mathbb{N} o S.

The value of
u \! at i \! (if defined) is often written
u_i \! instead of the usual
u(i) \!.
u \! is called a total numbering if
u \! is a Total Function .

If S \! is a set of natural numbers, then
u \! is required to be a Partial Recursive Function . If S \! is a set of subsets of the natural numbers, then the set \{\langle i,j angle : j \in
u_i \} (using the Cantor Pairing Function ) is required to be Recursively Enumerable .


EXAMPLES

  • Given a Gödel numbering arphi_i we can define a numbering of the Recursively Enumerable Set s by W(i):=\mathrm{domain}( arphi_i)



PROPERTIES

It is often more convenient to work with a total numbering than with a partial one. If the Domain of a partial numbering is Recursively Enumerable then there always exists an equivalent total numbering.


COMPARISON OF NUMBERINGS

Using computable function we can define a Partial Ordering on the set of all numberings. Given two numberings
:
u_1: \subseteq \mathbb{N} o S_1
and
:
u_2: \subseteq \mathbb{N} o S_2
we say
u_1 is reducible to
u_2 and write
:
u_1 \le
u_2
if
:\exists f \in \mathbf{P}^{(1)} \, orall i \in \mathrm{Domain}(
u_1) :
u_1(i) =
u_2 \circ f(i).

If
u_1 \le
u_2 and
u_1 \ge
u_2 then we say
u_1 is equivalent to
u_2 and write
u_1 \equiv
u_2.


SEE ALSO