Cylindric numbering

Cylindric numbering

In computability theory a cylindric numbering is a special kind of numbering first introduced by Yuri L. Ershov in 1973.

If a numberings ν is reducible to μ then there exists a computable function f with \nu = \mu \circ f. Usually f is not injective but if μ is a cylindric numbering we can always find an injective f.

Contents

Definition

A numbering ν is called cylindric if

\nu \equiv_1 c(\nu).

That is if it is one-equivalent to its cylindrification

A set S is called cylindric if its indicator function

1_S: \mathbb{N} \to \{0,1\}

is a cylindric numbering.

Examples

  • every Gödel numbering is cylindric

Properties

  • cylindric numberings are idempotent, \nu \circ \nu = \nu

References

  • Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Cylindrification — In computability theory a cylindrification is a construction which associates a cylindric numbering to each numbering. The concept was first introduced by Yuri L. Ershov in 1973. Definition Given a numbering ν the cyclindrification c(ν) is… …   Wikipedia

  • Eurybia divaricata — Taxobox name = White Wood Aster image width = 250px status = G5 status system = TNC status ref = Cite web publisher =NatureServe title = Eurybia divaricata work = NatureServe Explorer url = http://www.natureserve.org/explorer/servlet/NatureServe?s… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • bryophyte — bryophytic /bruy euh fit ik/, adj. /bruy euh fuyt /, n. Bot. any of the Bryophyta, a phylum of nonvascular plants comprising the true mosses and liverworts. [1875 80; < NL Bryophyta name of the group; see BRYO , PHYTE] * * * Any of the green,… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”