About Segment Complexity of Turing Reductions

✍ Scribed by Valeriy K. Bulitko

• Book ID: 102942668
• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 645 KB
• Volume: 45
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19990450413

✦ Synopsis

We apply complexity concepts to define a new sort of sub-Turing reducibilities 5 8 to make the degree hierarchy thinner and to obtain some new specifications of the well known jump inversion theorem of Friedberg. We show that this theorem doesn't hold when ST is replaced with 58, where 5 is any countable subset of the class z of all total increasing functions f : N -* N.