|
|
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? |
|
There is no answer at this time. |
|
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) |
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 Home - Answers FAQ - Terms of Service - Privacy Policy |