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 ***
