Re: Diagonalisation 1 (fwd)
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 ***
Re: Diagonalisation 1 (fwd)
,
*** 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,
Re: Diagonalisation 1
Brent Meeker wrote: in memory of James, [...] == 2. A paradox ? I will say that a function f is computable if there is a well defined formal language FL in which I can explained non ambiguously how to compute f on arbitrary input (number). I must be able to recognise if an expression in my language is a grammaticaly correct definition of a function, that is syntax error must be recoverable. All expression in the language must be of finite length, and the alphabet (the set of symbols) of the language is asked to be finite. Now all finite strings, a fortiori the grammatically correct one, form a countable set. Just use the lexicographic order defined above. So the set of function computable with FL is countable. A synonym of countable is *enumerable*, and is used by computer scientist, so I will also use it. So I can enumerate the functions computable with FL, that is I can put them in sequence like f_0, f_1, f_2, f_3, ... going through all functions computable in or with FL. Let us consider the function g defined again by g(n) = f_n(n) + 1 Now, g is not only well defined, but is even computable. To compute it on n, just search in the enumeration f_i the nth function, apply it to n (this gives an answer because the f_i are computable) and add 1. So, there is a number k such that g = f_k, but then, again g(k) = f_k(k) = f_k(k) + 1 But f_k(k) is a well defined number (f_k is computable), and no numbers can be equal to itself + 1. Contradiction. Could the set of computable functions in FL be uncountable, after all, or is g not expressible in FL, or what? Where is the error? I let you think a little bit. You can ask question. (Notably in case of notational problem). 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. Of course there is a cheat. But I don't see any infinite string appearing. The description of g is only given in terms of an enumerable infinite *list*. And for computing g(n) we need only to generate the n first element of the list, and this for each n. I give a hint. There are two ways to correct the argument, two possible cheats! Correcting one transforms the paradox into a wonderful theorem. Correcting the other transforms the paradox into another wonderful theorem. It is a deep paradox. It is at the root of both theoretical computer science and mathematical logic. It is worth to think what is going on here. So I let you think (and perhaps others) a little bit more ... Bruno
Re: Diagonalisation 1
On 21-Aug-01, Marchal wrote: in memory of James, == 2. A paradox ? I will say that a function f is computable if there is a well defined formal language FL in which I can explained non ambiguously how to compute f on arbitrary input (number). I must be able to recognise if an expression in my language is a grammaticaly correct definition of a function, that is syntax error must be recoverable. All expression in the language must be of finite length, and the alphabet (the set of symbols) of the language is asked to be finite. Now all finite strings, a fortiori the grammatically correct one, form a countable set. Just use the lexicographic order defined above. So the set of function computable with FL is countable. A synonym of countable is *enumerable*, and is used by computer scientist, so I will also use it. So I can enumerate the functions computable with FL, that is I can put them in sequence like f_0, f_1, f_2, f_3, ... going through all functions computable in or with FL. Let us consider the function g defined again by g(n) = f_n(n) + 1 Now, g is not only well defined, but is even computable. To compute it on n, just search in the enumeration f_i the nth function, apply it to n (this gives an answer because the f_i are computable) and add 1. So, there is a number k such that g = f_k, but then, again g(k) = f_k(k) = f_k(k) + 1 But f_k(k) is a well defined number (f_k is computable), and no numbers can be equal to itself + 1. Contradiction. Could the set of computable functions in FL be uncountable, after all, or is g not expressible in FL, or what? Where is the error? I let you think a little bit. You can ask question. (Notably in case of notational problem). 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
