Both Russell and Brent are right (see orig. message below),
but they *cannot* be both right, or can they?
They are right but not enough precise for agreeing!
You should try to restate the "paradox" in such a precise
way each of you find one of the two different theorems
which are hidden behind the paradox. Your "conclusion"
are right, but you should be both clearer on what "cheat"
must be corrected for getting those conclusions in an
absolute clear and unequivocable proof.
(cf
http://www.escribe.com/science/theory/m3079.html, and
http://www.escribe.com/science/theory/m3081.html).
I wait a little bit more for a final comment/solution.
Your "solutions " are hints for the other, also.
There is no shame finding that paradox rather not obvious,
Most of the initiators like Post, Church, Kleene, Godel, ...
have been wrong---a short time (like Post or Kleene), or a
longer time ... on that question.
I insist, the incorrect proof can be corrected in two precise
ways, giving two astonishing results, which are in a sense
the gate of theoretical computer science. You are very
close, it's good training to be able to find the definite
proofs. Looks like Brent is very close to one theorem, and
Russell very close to the other one. OK, no more hints.
Bruno
---- original message by Brent meeker----
>On 22-Aug-01, Russell Standish wrote:
>> Brent Meeker wrote:
>>>
>>> I think there is a cheat here. "Computable" requires that the
>>> function be defined finitely. While
>>>
>>> g(n) = f_n(n) + 1
>>>
>>> appears to be a finite description, it implicitly calls an the
>>> infinite list of functions f_n. So it's description is only given in
>>> terms of a enumerable, but infinite string, and hence does not occur
>>> in the list f_k.
>>>
>>> Brent Meeker
>>>
>> I thought this too when I first saw it, but it not that. What is
>> implictly called is the enumeration algorithm, not the infinite
>> list. That enumeration algorithm is presumably finitely describable,
>> ie there is a formal function f(i,n) such that f(i,n)=f_i(n).
>>
>> One thing that concerns me, is that while it is possible to map every
>> formal function onto a subset of the integers in a naive way (eg
>> express the function as a lisp program encoded in the ASCII character
>> set - the formal function number is given by expressing the program's
>> string as a number in base 128), not every integer corresponds to a
>> valid program. Hence f_n(n) may not be defined, if f_n() is not a
>> valid function.
>>
>> Perhaps this is the resolution. In order to construct a mapping f_n()
>> from the set of whole numbers onto the set of valid functions, one
>> needs to determine if a given string is a valid function. This is
>> surely as impossible a problem to solve as the Halting problem. The
>> enumerated set {f_n(): n\in n, f_n() a valid function} is perhaps
>> impossible to compute, but is a subset of a countable set.
>
>Imagine what would happen if you tried to implement this function g in a
>program. When you gave it any argument, i, that was not it's own index,
>it would return a value, f_i(i) + 1. But if it were given the integer
>that was it's own index, it would go thru the enumeration until it
>found f_k, when it started to execute f_k the first think it would do
>would be to start thru the list looking for the function whose index
>was k => an infinite loop. I wouldn't return a value.
>
>Brent Meeker
> When you find yourself in a hole,the first thing to do is stop digging.
> --- Molly Ivins
>*** End of forwarded message ***
Received on Mon Aug 27 2001 - 07:21:07 PDT