5 found
Sort by:
  1. Albert E. Lyngzeidetson & Martin K. Solomon (1994). Abstract Complexity Theory and the Mind-Machine Problem. British Journal for the Philosophy of Science 45 (2):549-54.
    In this paper we interpret a characterization of the Gödel speed-up phenomenon as providing support for the ‘Nagel-Newman thesis’ that human theorem recognizers differ from mechanical theorem recognizers in that the former do not seem to be limited by Gödel's incompleteness theorems whereas the latter do seem to be thus limited. However, we also maintain that (currently non-existent) programs which are open systems in that they continuously interact with, and are thus inseparable from, their environment, are not covered by the (...)
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  2. Martin K. Solomon (1993). Measure Independent Gödel Speed‐Ups and the Relative Difficulty of Recognizing Sets. Mathematical Logic Quarterly 39 (1):384-392.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Martin K. Solomon (1990). Relativized Gödel Speed‐Up and the Degree of Succinctness of Representations. Zeitschrift für Mathematische Logik Und Grundlagen der Mathematik 36 (3):185-192.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Martin K. Solomon (1987). A Connection Between Blum Speedable Sets and Gödel's Speed-Up Theorem. Zeitschrift für Mathematische Logik Und Grundlagen der Mathematik 33 (5):417-421.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. Martin K. Solomon (1978). Some Results on Measure Independent Gödel Speed-Ups. Journal of Symbolic Logic 43 (4):667-672.
    We study the measure independent character of Godel speed-up theorems. In particular, we strengthen Arbib's necessary condition for the occurrence of a Godel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Godel speed-ups and show that a theory τ 2 is a measure independent Godel speed-up of a theory τ 1 if and only if the set of undecidable sentences (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation