Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question about well-known theorems:

Theorem: Kolmogorov complexity is not a computable function.

And, related, Chaitin's incompleteness theorem.


In both cases constructed programs and proofs based on paradoxical inequality

$U+log(n)+C< n$

I'm embarrassed by following thoughts:

For manipulation(processing) of strings, these programs must "know" the size of strings(type of string) that they generate. Or places in memory(linear memory) where string starts and ends. This is impotrant for KolmogorovComplexity subroutine.

But a priori program do "not know" size of string that will satisfy the condition:


Thus, program must to reserve the memory for infinity inductive type, used as:

$...for \ i=1\ to\ infinity:...$

and we obtain:



$log(∞)$ means "size" of unbounded strings' buffer

Thus, program GenerateParadoxicalString has infinite size and never stop.

Infinite size due to GenerateComplexString, because of unbounded buffer.

And never stop due to KolmogorovComplexity, in attempt to read string from unbounded buffer.

Is it correct?


share|improve this question
I don't know what kind of programming language you are using in your definition of computability, but in C you can dynamically allocate memory with malloc. The problem you describe wouldn't be faced by a Turing machine either, I don't think. –  Trevor Wilson Jan 24 '13 at 17:23
The possibility of a finite-sized program gobbling up infinite memory over time is a requirement for Turing-completeness, I think –  Trevor Wilson Jan 24 '13 at 17:26
Sorry, I'm not sure what your last comment says. Are you saying that you can look at a program and put an upper bound on the amount of memory it will allocate? It is undecidable how much memory it will allocate. –  Trevor Wilson Jan 24 '13 at 17:32
Computability is defined in terms of computers with unlimited memory, or Turing machines with endless tapes. –  Trevor Wilson Jan 24 '13 at 18:09
A finite program can end up using infinitely much memory (by which I mean that its memory usage can grow without bound as it runs.) –  Trevor Wilson Jan 24 '13 at 19:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.