, *** Forwarded message, originally written by Brent Meeker on 22-Aug-01 *** 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 *** vr,