Numbering (computability Theory)

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

u

is called a total numbering if

u

is a Total Function . The value of

u

i

(if defined) is often written

u_i

instead of the usual

u(i)

.

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 exsists 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).

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

Gödel Numbering

Complete Numbering

Cylindrification

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

Information About

Numbering (computability Theory)