Premium
Measure independent Gödel speed‐ups and the relative difficulty of recognizing sets
Author(s) -
Solomon Martin K.
Publication year - 1993
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19930390142
Subject(s) - measure (data warehouse) , mathematics , characterization (materials science) , computer science , data mining , physics , optics
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.