Re: Proof of Uncomputability of Kolmogorov complexity
- From: tchow@xxxxxxxxxxxxx
- Date: 25 Jan 2007 00:27:17 GMT
In article <1169682348.371991.183780@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
asdf <qjohnny2000@xxxxxxxxx> wrote:
I was reading the page:
http://en.wikipedia.org/wiki/Kolmogorov_complexity
in particular the proof of why kolmogorov complexity is not computable.
Does anybody know why to encode n0 it takes log(n0) bits ? I'm
wondering because your programming language could represent numbers not
as regular numbers but as "1111" represents 4 and "111111" represents
6. Therefore you would need n0 space in the program to store n0 not
log(n0)... Basically the proof is assuming how n0 is stored.. is it
not ?
The first thing to note is that there is a slight error on the Wikipedia
page; the function GenerateParadoxicalString should have no arguments.
The "n_0" is really a template, and is to be replaced with an explicit
integer. It's *not* the character "n" followed by the character "0".
Back to your question. You're right, the proof assumes that in your
description language, you have chosen to represent integers using
binary or decimal notation or some other method that uses log(n) symbols
to represent n. So what happens if you use some other representation
method? See the part earlier on the page where they show that the
choice of description language matters only up to a constant. If you
could compute Kolmogorov complexity using unary representation of numbers,
then you could use that argument to show that you could compute Kolmogorov
complexity using binary representations too, which the proof shows can't
be done.
Another way to look at it is, if your description language is so ornery
as to use unary notation, then you could circumvent this problem by
writing a little subroutine that implements binary notation. Since we're
aiming at the shortest possible programs, you would find yourself using
this subroutine to deal with numbers instead of using explicit unary
representations. So the proof of uncomputability would still work;
it's just that it would be a messier proof, since you would have to
work with subroutine calls in place of literal representations of
numbers.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.
- References:
- Prev by Date: Proof of Uncomputability of Kolmogorov complexity
- Next by Date: need help finding a class project(comp. geometry and cryptography)
- Previous by thread: Proof of Uncomputability of Kolmogorov complexity
- Next by thread: need help finding a class project(comp. geometry and cryptography)
- Index(es):
Relevant Pages
|
