Jason (jcreed) wrote,

I got off on the wrong foot with my proof attempt yesterday by stupidly thinking I could dodge diagonalization by computable approximation; I guess the thing I had read somewhere was the (not computably realizable) fact that if you keep taking the smallest theory (i.e. Turing machine) consistent with the data so far, and which terminates on all inputs so far (that being the noncomputable part), you'll eventually be always right.

Here's another thought, though: choose up front a sound proof system P that has a terminating proof-checking procedure. On the nth step, start enumerating P-provably terminating Turing machines and running them on inputs 0..n-1. As soon as you get a g that is consistent with f(0)..f(n-1), guess g(n) as your prediction of f(n). As long as f is P-provably terminating, you'll eventually always make guesses consistent with it. The moral of diagonalizing here is that the guessing procedure itself can't possibly be P-provably terminating, right?
Tags: computability

  • (no subject)

    Had a disappointing time at climbing (although I nearly got a new V2), but a rousing good time at D's. The draft root beer may be a bit overpriced,…

  • (no subject)

    Had a decent if not spectacular time climbing. New successes were a V0+ and V1 inside the side cave. The V0+ in particular was something I'd been…

  • (no subject)

    Got some work done in the morning. Later went climbing with a ton of people. That V2 jump-start is still awfully fun. I'm getting more consistent at…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded