Citations of:
Add citations
You must login to add citations.




Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations. 







Without introducing quantifiers, minimal axiomatic systems have already been constructed for Peirce's triadic logics. The present paper constructs a dual pair of axiomatic systems which can be used to introduce quantifiers into Peirce's preferred system of triadic logic. It is assumed (on the basis of textual evidence) that Peirce would prefer a system which rejects the absurd but tolerates the absolutely undecidable. The systems which are introduced are shown to be absolutely consistent, deductively complete, and minimal. These dual axiomatic systems (...) 

We provide and interpret a new measure independent characterization of the Gödel speedup phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speedup 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 speedup, and by deleting the “for all r” condition from the definition so as to relax the required amount of speedup. We (...) 

In this paper we prove some results about the complexity of proofs. We consider proofs in Hilbertstyle formal systems such as in [17]. Thus a proof is a sequence offormulas satisfying certain conditions. We can view the formulas as being strings of symbols; hence the whole proof is a string too. We consider the following measures of complexity of proofs: length , depth and number of steps For a particular formal system and a given formula A we consider the shortest (...) 

