Google Answers Logo
View Question
 
Q: Incompressible strings ( No Answer,   2 Comments )
Question  
Subject: Incompressible strings
Category: Computers > Algorithms
Asked by: nr9-ga
List Price: $50.01
Posted: 01 Aug 2004 23:11 PDT
Expires: 02 Aug 2004 06:29 PDT
Question ID: 382261
How do you show that the set of incompressible strings is undecidable?
Answer  
There is no answer at this time.

Comments  
Subject: Re: Incompressible strings
From: rhansenne-ga on 02 Aug 2004 04:47 PDT
 
The following paper states:

http://minerva.ufpel.edu.br/~campani/cisst04.pdf

"It is interesting to observe that the problem of determining if
a string is incompressible is an undecidable problem. Suppose
that the set of incompressible strings is enumerable. Let f be
a recursive partial function that enumerates the incompressible
strings. Thus f(n) denotes the first string x0 with complexity
greater than n. Then, C(x0) > n and C(x0) = C(f(n)) · C(n) + c = log n
+ c. So C(x0) > n and C(x0) · log n + c,
for any arbitrary n, which is a contradiction. Observe that log
denotes the base two logarithm.
It means that we cannot formally determine how much
information is necessary to compute a string, this being a
limitation of the formal systems."
Subject: Re: Incompressible strings
From: nr9-ga on 02 Aug 2004 06:28 PDT
 
sorry i meant to ask something else ( i posted a new question)

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy