From: Peter de Blanc (peter@spaceandgames.com)
Date: Sun Dec 07 2008 - 12:50:15 MST
Joshua Fox wrote:
> Peter,
>
> Since we're discussing the paper here, I hope that some questions about
> it are not out of place.
No problem.
> * A broad question, not a technical criticism of the proof, but rather a
> request for an intuitive understanding:
> I'm wondering why p cannot nose-dive as fast as U skyrockets. I see
> that you bound both U and p from below with computable functions. Of
> course, that's not too tight a bound, but it raises the question: Why
> can't p go down as much as U goes up, so that ultimately the series of
> their products converges?
One way of looking at it is to say that a computable partial function
can grow faster than any computable total function. For example,
consider the function D(n) = output of program n given zero input. D(n)
grows about as quickly (on a certain subsequence) as the busy beaver
numbers (D(n) ~ BB(log n), a trivial distinction), so it grows faster
than any computable sequence. D(n) itself is not a computable total
function because for some indices n, the program n will not halt.
So to consider a slightly simpler case than in the paper, suppose p and
U were both computable functions. p is a function of an _index_ of a
program, whereas U is a function of the _output_ of the program. Since
the map from programs to outputs is not a total computable function, it
should seem conceivable that U(program_n(0)) could grow more quickly
than 1/p(n), because the former is not a total function in n but the
latter is.
Anyway, this doesn't prove the claim of the paper (that's what the paper
is for), but I hope I've addressed the intuitions which might lead one
to believe that p should be able to shrink as fast as U can grow.
> * A minor notational question: In the proof of lemma 1.
> F(x) = 1 + f(x) + max {B(x) − f(x) : x ∈ N}
> The x in the curly-braces is quantified and the x outside the braces
> is not; does that make these in fact separate variables?
Thanks for the proof-reading. Yes, these should be separate variables,
so I should rename the x inside the curly braces to, say, y. So then it
would read:
F(x) = 1 + f(x) + max {B(y) − f(y) : y ∈ N}
The idea here is that if B(x) > f(x) only finitely-many times, we can
construct another computable function, F, which is strictly greater than
B, simply by adding a constant to f.
- Peter de Blanc
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT