George,
At 21:17 20/07/04 -0700, George Levy wrote:
Bruno, John, Russell
I am half-way through Smullyan's book.
Nice! You will see how easy it will be to state precisely the main result and the open problems in my thesis once you grasp the whole FU. Of course, to really appreciate, there will be a need to study a little bit two "non-classical logics": intuitionist logic and quantum logic ('course).
It is an entertaining book for someone motivated enough to do all these puzzles, but I think that what is missing is a metalevel discussion of what all this means.
Sure! I see that now that we are going back to the basic you are impatiently anticipating the things! That's makes me happy!
Mathematical fireworks occur because we are dealing with self-referential systems. In the old days they may have called them "reflexive." Reflection is, I think, an essential component of conscious thought.
Yes.
The type of reflection I have encountered so far in the book involves "infinite" reflections which lead to paradoxes.
For example if someone says " I am a knave" then obviously we have a paradox.
I disagree!!! I'm a little bit sorry because I have not resisted putting a little trap in the problems yesterday. Actually there is no paradox here! (More below).
The human mind, however, does not have the capacity to deal with an infinite number of reflections. (I think that you think that I think that you think.....).
You anticipate a little bit too much. In a sense not only humans can deal with infinite reflexion but machine can do aswell...I will not try to explain now. In FU this is explained in the "heart of the matter" section 25. To be honest Smullyan's explanation is rather short. When we will arrive at that stage it will be good to (re)read the "diagonalisation posts" (accessible from my url). There are two really fundamental theorems: their official name are 1) The second recursion theorem of Kleene (2-REC) 2) The diagonalisation lemma (DL) The first one can aptly be called (with the comp hyp) the fundamental theorem of theoretical biology. It is the one I have use to build "amoeba" (self-reproducing programs), "planaria" (self regenerating programs) and "dreaming machine" (programs capable of conceiving themselves in alternate anticipations). Solovay's arithmetical completeness theorems of G and G* are themselves the most pretty application of 2-REC. George Boolos use the DL instead. They are quite related.
If, however, self referential systems are limited to a finite number of reflections, such as the human mind is capable of, then these paradoxes may go away. With one reflection a knave would says: "I am a knight." With two reflections he would say "I am a knave." With three reflections, "I am a knight." With four "I am a knave." and so on. With an infinite number of reflections he would remain "Forever Undecided."
I am not sure if Physics is derived from an ideal infinite self-referential systems or from a more human and messy finite system and I cannot think of an obvious and clear-cut justification for either approach. What do you think?
Physics will come from the *machine* messy finite system, not necessarily *human*. Actually the machine's psychology G and G* is also the psychology of some "infinite machine" and there exists for each sort of alpha-machine (alpha ordinal) a related physics. So by testing those physics we will be able to evaluate our own degree of comp/non-comp. My thesis shows that quantum sort of logic appears right at the starting point alpha = omega point.
And now the solution of the problems: (I see most people have find the solutions (and even new problem and solution, thanks to John and Russell) ... modulo some details.
<<The native of that Island are all either knight or knaves and knight always tell the truth, and knaves always lie. You go there. Problem 1. A native tell you "I am a knight". Is it possible to deduce the native's type? Problem 2. You meet someone on the island, and he tells you "I am a knave". What can you deduce?>>
Problem 1. The answer is NO. The assertion "I am a knight" can be made by a knight (who then tells the truth as it should), but can be made by a knave (who then tells a lie as it should). "as it should" giving the rule of the island. OK?
Problem 2. Someone says "I am a knave". Suppose it is a knave: well then he says the truth so it cannot be a knave. Suppose it a knight: well then it is a lie so it cannot be a knight, either. So it is neither a knight, nor a knave, but we have been said that all the native of the island are either knight or knave. So we can deduce that it cannot be a native of the island. That "someone" (the trap!) is most probably a (lying) tourist, or a mad explorator ... OK?
;-)
Bruno
http://iridia.ulb.ac.be/~marchal/