by [anonymous]
1 min read9th Apr 20118 comments

9

This is a short math question.  Say I have an oracle that computes Kolmogorov complexity.  Is there an algorithm that consults this oracle that will determine whether a given Turing machine halts?

New to LessWrong?

New Comment
8 comments, sorted by Click to highlight new comments since: Today at 6:53 AM

Yes, the two are equivalent. See Chaitin, Arslanov, Calude "Program-size complexity computes the halting problem" (linky).

I'm glad that we're beginning to have such questions here and not on MathOverflow :-)

[-][anonymous]13y80

Thanks. It's only a paragraph but it took me a while to understand Chaitin's argument, for what it's worth here's my take:

Let K(n) = complexity of the integer n. For each integer c, let Sigma(c) be the largest number with complexity c -- they call this the "information theory busy beaver function" and indeed Sigma(c) dominates the Turing-style busy beaver function: each computer program of length n will halt before Sigma(n) steps, or not at all. (To see this, note that if a program of length n halts in time t, then we can compute t by running our program, giving K(t) < n and t < Sigma(n).) The problem is that it's not clear whether an oracle for K(n) allows us to compute Sigma(n) -- Chaitin explains how to compute a more complicated function beta(n).

To define beta(n) you do something like this. Write a computer program P that outputs a sequence (x_1,k_1), (x_2,k_2), ... with each K(x) <= k and all such pairs occuring. You can do this without using the K-oracle. Eventually P will output (x,K(x)), and we may use our oracle to tell when. In fact we can use our oracle to tell how many steps it takes before (x,K(x)) appears for every n-digit x, call this function beta(n). Claim: beta(n) is a good substitute for Sigma(n), in the sense that if T > beta(n) then K(T) > n; therefore a computer program of length n halts after beta(n) steps or not at all.

The claim is just the observation that if T > beta(n), then the complexity of T is larger than the complexity of a maximally complex n-digit number, because we can run P with the additional instruction "stop after T steps" (maybe with a subroutine of length K(T) to generate T) to get this number. The most complex n-digit number has complexity n, and that's it.

The Arslane-Calude argument is over my head.

Does anyone know if the following are equivalent:

An oracle that returns the length of the shortest program to return a given string of bits.

An oracle that returns the length of the shortest program to return either the given string of digits or any longer string that begins with the given string.

More specifically, is there an algorithm that computes the latter by consulting the former.

If the answer to this is yes then the answer to the problem in the OP is yes as well.