Premium
Kolmogorov Complexity and Noncomputability
Author(s) -
Davie George
Publication year - 2002
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/1521-3870(200211)48:4<574::aid-malq574>3.0.co;2-o
Subject(s) - kolmogorov complexity , kolmogorov structure function , mathematics , statement (logic) , embedding , halting problem , discrete mathematics , combinatorics , algorithm , computer science , artificial intelligence , computation , epistemology , philosophy , turing machine
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 (e. g. by embedding in the halting problem). Also, many sets which are (at least) 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 (shortest) proof length.