Notes from a Medium-Sized Island [entries|archive|friends|userinfo]
Jason

 [ website | My Website ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

[Jan. 9th, 2012|08:10 pm]
Jason
 [ Tags | computability ]

Reading some about Ray Solomonoff I was reminded how funny universality of computation really is.

WARNING WARNING PROBABLY NOT A VALID PROOF OF ANYTHING

For example: let a computable function f : N → 2 be given; that is, an infinite stream of bits. We're going to try to play the game of guessing the next bit of f, given the first n bits. So, given the first n bits (that is, the value of f on values 0, ..., n-1) we simulate the n smallest turing machines on all inputs 0..n for n steps, take the smallest turing machine g in that set that satisfies
(a) g(n) terminates (in the n steps that we waited for it)
(b) g(0), ... g(n-1) are consistent with the bits we've seen so far (i.e. g(i) = f(i) or else g(i) doesn't terminate, for all i) and we use g(n) as our guess.

If I haven't slipped up somewhere, this guessing game has the property that it will eventually always be right! Constructively, it is a contradiction for it to have an infinite number of errors. For let N be the goedel number of a turing machine that computes f. We will never choose a turing machine for our guess with goedel number greater than N, and each of the turing machines less than N can only fool us once before they are invalidated forever. Any turing machine that never fools us is actually never *wrong* --- and so is just a witness that our original N wasn't minimal, which is fine.

 From: 2012-01-10 02:08 am (UTC) (Link)
I'm thinking of a bitstream-generator that, at step n, runs your predictor function with input equal to the previous n-1 bits, and then outputs the opposite of whatever your predictor said.
 From: 2012-01-10 03:01 am (UTC) (Link)
It's not clear to me that it would get run long enough by predictor to terminate in time and be a candidate for the guess.
 From: 2012-01-10 05:34 am (UTC) (Link)
Predictor doesn't need to run said bitstream-generator. As long as Predictor is computable, so is the bit sequence that diagonalizes against it.

 From: 2012-01-10 03:04 am (UTC) (Link)
But as I say that it's not clear that turing machine N finishes soon enough either :/

I guess my proof is broken anyway.
 From: 2012-01-10 03:32 am (UTC) (Link)
Whoa! This is an uncanny coincidence of ideas. Several parts of your post remind me of a conversation I had with another logician just a few days ago at the JMM. I had forgotten it until I read what you wrote and it rang a bell. So I looked up the paper and I think I found it. It's a cute new paradox involving the Axiom of Choice.
 From: 2012-01-10 03:34 am (UTC) (Link)
I think I was asked this prisoner puzzle --- including the bit about \omega_1 --- during a job interview in '09.
 From: 2012-01-10 05:01 am (UTC) (Link)
That link's malformed: begins: you need to drop the leading jcreed.livejournal.com to make it http://www.math.union.edu/~hardinc/pub/peculiar.pdf