Tim Little says... > >On 2010-06-28, Virgil <Virgil@home.esc> wrote: >> It does not require that any element in the listing be known, but >> correctly tells what to do for any listing > >I think that is even a bit too informal for Peter. The phrase "tells >what to do" is superfluous, all that is mathematically required is >that existence of an antidiagonal sequence for each list is proven. >He's going to latch onto "tells what to do" and think that it means >that there is an algorithm for everything involved. > >Witness his confusion over the example I defined of a list where each >entry was computable but the list itself (and its antidiagonal) was >not. He didn't dispute that the list *existed*, but considered it >cheating because he couldn't use the definition to extract actual >digits of the antidiagonal - it didn't "tell him what to do" in his >own special sense.
I never saw a response from Peter on my post about Turing machine computability relative to an oracle. You can imagine a Turing machine tape (the oracle) that lists codes for computable functions. Using the oracle, you can diagonalize to get a new function that is not listed by the oracle. This new function is computable *relative* to the oracle, but may not be computable *without* the oracle.
