• Title of article

    Interpreting true arithmetic in the theory of the r.e. truth table degrees Original Research Article

  • Author/Authors

    André Nies، نويسنده , , Richard A Shore، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 1995
  • Pages
    43
  • From page
    269
  • To page
    311
  • Abstract
    We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.
  • Journal title
    Annals of Pure and Applied Logic
  • Serial Year
    1995
  • Journal title
    Annals of Pure and Applied Logic
  • Record number

    890028

    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=10&DC=890028