(no title)

Notes from a Medium-Sized Island

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.

Link

Comments:

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)

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)

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)

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)

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)

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)

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)