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

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

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

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


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.

[User Picture]From: platypuslord
2012-01-10 02:08 am (UTC)
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.
(Reply) (Thread)
[User Picture]From: jcreed
2012-01-10 03:01 am (UTC)
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.
(Reply) (Parent) (Thread)
From: rdore
2012-01-10 05:34 am (UTC)
Predictor doesn't need to run said bitstream-generator. As long as Predictor is computable, so is the bit sequence that diagonalizes against it.

(Reply) (Parent) (Thread)
[User Picture]From: jcreed
2012-01-10 03:04 am (UTC)
But as I say that it's not clear that turing machine N finishes soon enough either :/

I guess my proof is broken anyway.
(Reply) (Parent) (Thread)
[User Picture]From: krasnoludek
2012-01-10 03:32 am (UTC)
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.
(Reply) (Thread)
[User Picture]From: jcreed
2012-01-10 03:34 am (UTC)
I think I was asked this prisoner puzzle --- including the bit about \omega_1 --- during a job interview in '09.
(Reply) (Parent) (Thread)
[User Picture]From: nightspore
2012-01-10 05:01 am (UTC)
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
(Reply) (Parent) (Thread)
[User Picture]From: krasnoludek
2012-01-10 05:21 am (UTC)
huh, well that's weird. I didn't type any leading "jcreed.livejournal.com" and that's not in the code for the HREF, even now if I were to edit it. However, I did happen to omit the http:// and just began the URL in the HREF with www.
(Reply) (Parent) (Thread)
From: simrob
2012-01-10 06:12 am (UTC)
right: it assumed it was a relative directory link to jcreed.livejournal.com, specifically in the www.math.union.edu directory of jcreed.livejournal.com.

I blame jcreed for not pre-caching www.math.union.edu on his blog. How inconsiderate of him.
(Reply) (Parent) (Thread)
From: wjl
2012-01-10 03:20 pm (UTC)
This must be related to Andrej Bauer's seemingly impossible functional programs post. I don't think I ever managed to fully grok that one, either, though..
(Reply) (Thread)