Mathematical Logic Quarterly 48 (4):574-581 (2002)

We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability . Also, many sets which are awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal proof length
Keywords Kolmogorov complexity  noncomputable
Categories (categorize this paper)
DOI 10.1002/1521-3870(200211)48:4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,163
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Kolmogorov Complexity and the Second Incompleteness Theorem.Makoto Kikuchi - 1997 - Archive for Mathematical Logic 36 (6):437-443.
Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.
Recursive Events in Random Sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.


Added to PP index

Total views
13 ( #769,307 of 2,506,898 )

Recent downloads (6 months)
1 ( #417,155 of 2,506,898 )

How can I increase my downloads?


My notes