Bruno,
Taking your assumption that I am a machine or number and so I can be
plugged into an equation (You = Tom or George...), I will say speaking
for myself that I would like a couple of days to think about this. If
we all are one person, then I will not be surprised that George feels
the same way. However, the "or" in the equation "You = Tom or
George..." is already non-constructive. :)
On the topic of non-constructiveness, the controversial use of the
excluded middle is in the context of infinity, not in the finite. I
previously agreed that you did not leave the finite. But now I have a
doubt. It seems that the diagonalization step you have already taken
actually uses the excluded middle for a countable infinity. Given a
(countably infinite) sequence of functions f1, f2, ..., you say that
fn(n)+1 must either be in the sequence OR not in the sequence.
But I will take some of my rare spare time (which I always have by
diagonalization) to think some more about this absoluteness of
computability and Church Thesis, etc. and try to understand this and
solve the puzzle of where your straw-man argument is wrong.
Speaking of straw-men, it seems you are saying that machines simply
running programs, without axioms and inference rules, are like zombies.
Zombies are how I would traditionally think of machines, but you seem
to be saying that the axioms and inference rules somehow breathe life
into the machine.
Tom
-----Original Message-----
From: Bruno Marchal <marchal.domain.name.hidden>
To: everything-list.domain.name.hidden
Sent: Tue, 6 Jun 2006 16:38:28 +0200
Subject: Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi,
Here is a little test, just for singling out a typical non
intuitionistic (non constructive) argument.
Such kind of argument makes me recall the tale: "The Little Prince"
written by the French pilot and novelist St-Exupery, where the Little
Prince asked the narrator (a pilot) to draw a sheep. But he can't draw
at all and fails badly in all his attempt to draw a sheep, so that
after a while, and because the Little Prince insisted so much,
eventually he decided to draw just a box, and told the little Prince
that the sheep was in the box.
Well, classical mathematicians does that all the time: actually they do
it each time they prove the existence of some object without exhibiting
precisely that object. Constructivist and engineers can be
disappointed, but platonist or classical mathematicians are quite cool
with such non-constructive proof.
I know by experience that even if I give the solution of the *puzzle*,
many people does not really see the non constructive step. So let me
first illustrate such a non-constructive reasoning on a very cute
example.
It is a "well known" proof that there exist irrational numbers x, y,
such that x^y is rational. We don't ask that x should be different of
y. The question is really (in english): is it possible that a
irrational number exponentiated by an irrational number gives a
rational number?
(I recall that a positive real number r is rational iff there exist
natural numbers n and m such that r is equal to m/n. r will be said
to be irrational if r is not rational. A typical irrational number is
the square root of 2, written sqrt(2)).
Here is the delightful proof by Jarden.
First note that a real number is either rational or ... irrational.
Right?
Well, if you say "yes" to this, you have already leave the constructive
area!!!! You have accepted the principle of excluded middle saying that
for any well-defined proposition p, either p is true, or p is false. In
this case p is, for some real number r, the proposition "r is
rational". The excluded middle principle gives then: "r is rational or
r is not rational", or "r is rational or is irrational".
Good ... So you agree that the real number sqrt(2) ^ sqrt(2), that is:
the (square root of two) exponentiated up to the (square root of two)
is rational or irrational. Right?
So we have just two cases to consider:
1) sqrt(2) ^ sqrt(2) is rational. Well, in that case we have a
solution: x = y = sqrt(2).
2) sqrt(2) ^ sqrt(2) is irrational. In that case just take x =
(sqrt(2) ^ sqrt(2)), and y = sqrt(2). Then, if you remember elementary
algebra, i.e. that ((a^b)^c) = a^(bc), then you see that x^y = 2 which
is rational of course.
So in all cases we have end up with an irrational which exponentiated
up to some irrational gives a rational, and we have solve the existence
problem. If you ask me a precise (constructive) solution, this
reasoning is not satisfactory. But the reasoning is far from hopeless:
the solution is given to you in a box, the box (set) containing the
couple (sqrt(2) , sqrt(2)) and the couple (sqrt(2) ^ sqrt(2) ;
sqrt(2)). I can, like St-Exupery, tell you that the solution is in the
two-elements box:
{ (x = sqrt(2) ; y = sqrt(2)) (x = sqrt(2) ^ sqrt(2) ; y =
sqrt(2)) }
But I cannot tell you which one, among the two solutions, is the
correct one.
Put in a different way I did prove a non-constructive OR proposition. I
have proved that
["x = sqrt(2) , y = sqrt(2)" is the solution] OR ["x= sqrt(2) ^
sqrt(2) ; y = sqrt(2)" is the solution].
And the or is non constructive because my reasoning does not allow us
to choose between the solution proposed on the left of the "or" or if
it is the one on the right of the "or".
In this present case, highly complex number theory (including elliptic
function theory, modular form, etc.) can settle the disjunction
constructively, but in theoretical computer science, on the contrary,
we will met many non-constructive "or" which can be proved being
necessarily non constructive. That means the non constructive solution
is the best we can ever hope for.
And that will be the case for the solution of the *puzzle*.
I don't want to jeopardize the pleasure of searching that solution, and
so I let you think a little bit more. Normally, with what Jesse and
Hall (notably) told, and what you have already seen, + the present
post, you have all the tools in the hands to explain exactly and
precisely how we can generate all computable functions in a way
vaccinated from the diagonalization procedure.
Of course, the "or" of the first person talk about its future personal
memory in the Washington Moscow duplication is also a special sort of
non constructive OR. Also, in the field of theoretical artificial
intelligence (or computational learning theory), it can be shown that
almost all "OR" are necessarily non constructive, making almost the
entire field completely empty from an intuitionist perspective.
Another example: I insist all the time that the correct part of the
Penrose-Lucas use of Godel's theorem is that it does not show that we
are not machine, but only that if we are machines then we cannot know
which one we are, and this means that the proposition "I am a machine"
*does* necessarily leave the constructive area. The proposition "I am a
machine" is equivalent (with Church thesis) with the proposition "I am
M1 OR I am M2 OR I am M3 OR I am M4 OR ...", with Mi giving an
enumeration of all machine (exist by CT). Given that I cannot know
which machine I am, all those "OR" are non constructive. Of course I
anticipate here.
OK so far? Do you want to know the solution? Do you prefer to think
about all this a couple of days?
You = Tom, or George, or others ...
Be sure to understand the problem before I give the solution. We really
are at the heart of the matter, not just of Smullyan's FU, but of all
my own work and what I am trying to say. All the nuances between the
arithmetical plotinian hypostases will emerge thanks to all those
nuances between computations, proofs, constructive, not constructive,
etc.
Bruno
http://iridia.ulb.ac.be/~marchal/
________________________________________________________________________
Check out AOL.com today. Breaking news, video search, pictures, email
and IM. All on demand. Always Free.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Tue Jun 06 2006 - 14:51:19 PDT