The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility (Q4032885)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 150250
Language Label Description Also known as
default for all languages
No label defined
    English
    The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
    scientific article; zbMATH DE number 150250

      Statements

      The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility (English)
      0 references
      0 references
      0 references
      1 April 1993
      0 references
      Turing jump
      0 references
      embedding of finite partial orders
      0 references
      decidability
      0 references
      r.e. degrees
      0 references
      Turing reducibility
      0 references
      The paper shows the decidability of the existential theory of the r.e. degrees in the language of Turing reducibility and Turing reducibility of the jump. The authors express their expectation to extend the results to the language of Turing reducibility of all \(n\)th jumps shortly. The proof gives a direct embedding of arbitrary finite partial orders, controlling the reduction between their jumps at the same time.
      0 references

      Identifiers