Harman Patil (Editor)

Cylindric numbering

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

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

Definition

A numbering ν is called cylindric if

ν ≡ 1 c ( ν ) .

That is if it is one-equivalent to its cylindrification

A set S is called cylindric if its indicator function

1 S : N → { 0 , 1 }

is a cylindric numbering.

Examples

  • every Gödel numbering is cylindric

    • Properties

  • cylindric numberings are idempotent, ν ∘ ν = ν

    • References

    Cylindric numbering Wikipedia
    (Text) CC BY-SA