Measure independent Gödel speed-ups and the relative difficulty of recognizing sets

✍ Scribed by Martin K. Solomon

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 558 KB
• Volume: 39
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19930390142

✦ Synopsis

Abstract

We provide and interpret a new measure independent characterization of the Gödel speed‐up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed‐up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed‐up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed‐up. We interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed‐up phenomena. MSC: 03D15, 03F20.