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 <[EMAIL PROTECTED]> To: [email protected] 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---
