Rogers' Equivalence Theorem - Definition

Definition

The formalization of computability theory by Kleene led to a particular universal partial computable function Ψ(e, x) defined using the T predicate. This function is universal in the sense that it is partial computable, and for any partial computable function f there is an e such that, for all x, f(x) = Ψ(e,x), where the equality means that either both sides are undefined or both are defined and are equal. It is common to write ψe(x) for Ψ(e,x); thus the sequence ψ0, ψ1, ... is an enumeration of all partial computable functions. Such enumerations are formally called computable numberings of the partial computable functions.

An arbitrary numbering η of partial functions is defined to be an admissible numbering if:

  • The function H(e,x) = ηe(x) is a partial computable function.
  • There is a total computable function f such that, for all e, ηe = ψf(e).
  • There is a total computable function g such that, for all e, ψe = ηg(e).

Here, the first bullet requires the numbering to be computable; the second requires that any index for the numbering η can be converted effectively to an index to the numbering ψ; and the third requires that any index for the numbering ψ can be effectively converted to an index for the numbering η.

Read more about this topic:  Rogers' Equivalence Theorem

Famous quotes containing the word definition:

    “The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
    —William James (1842–1910)

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)