Re: Diagonalisation 1 (fwd)

From: Brent Meeker <meekerdb.domain.name.hidden>
Date: Sat, 25 Aug 2001 10:03:41 -0700

,
*** 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,
Received on Sat Aug 25 2001 - 11:11:25 PDT