`At 09:54 27/07/04 -0700, Hal Finney wrote:`

I am confused about how "belief" works in this logical reasoner of type 1. Suppose I am such a reasoner. I can be thought of as a theorem-proving machine who uses logic to draw conclusions from premises. We can imagine there is a numbered list of everything I believe and have concluded. It starts with my premises and then I add to it with my conclusions.

OK.

In this case my premises might be:

1. Knights always tell the truth 2. Knaves always lie 3. Every native is either a knight or a knave 4. A native said, "you will never believe I am a knight".

Now we can start drawing conclusions. Let t be the proposition that the native is a knight (and hence tells the truth). Then 3 implies:

5. t or ~t

Point 4 leads to two conclusions:

6. t implies ~Bt 7. ~t implies Bt

Here I use ~ for "not", and Bx for "I believe x." I am ignoring some complexities involving the future tense of the word "will" but I think that is OK.

Perfect. Here "Hal believes p" means that sooner or later Hal will assert, believe or prove p. It means p belongs to the list you mentionned.

However now I am confused. How do I work with this letter B? What kind of rules does it follow?

I understand that Bx, I believe x, is merely a shorthand for saying that x is on my list of premises/conclusions.

Correct. This means Bx is a equivalent with "Hal believes x". The only difference is that "Bx" is supposed to be in the language of the machine.

If I ever write down "x" on my numbered list, I could also write down "Bx" and "BBx" and "BBBx" as far as I feel like going. Is this correct?

Well, not necessarily. Unless you are a "normal machine", which I hope you are! So let us accept the following definition: a machine is normal when, if it ever assert x, it will sooner or later asserts Bx. Normality is a form of self-awareness: when the machine believes x, it will believe Bx, that is it will believe that it will believe x.

But what about the other direction? From Bx, can I deduce x? That's pretty important for this puzzle. If Bx merely is a shorthand for saying that x is on my list, then it seems fair to say that if I ever write down Bx I can also write down x. But this seems too powerful.

You are right. It is powerful, but rather fair also. let us define a machine to be stable if that is the case. When the machine believes Bx the machine believes x.

So what are the correct rules that I, as a simple machine, can follow for dealing with the letter B?

Actually we will be interested in a lot of sort of machine. But I do hope you are both normal and stable. Actually I'm sure you are.

The problem is that the rules I proposed here lead to a contradiction. If x implies Bx, then I can write down:

8. t implies Bt

Note, this does not mean that if he is a knight I believe it, but rather that if I ever deduce he is a knight, I believe it, which is simply the definition of "believe" in this context.

Here you are mistaken. It is funny because you clearly see the mistake, given that you say 'attention (t implies Bt) does not mean "if he is a knight the I believe it". But of course (t implies Bt) *does* mean "if he is a knight the I believe it". You add it means only (and here I add a slight correction) "if I ever deduce he is a knight I will deduce I believe he is a knight" which really is, in the machine language: (Bt implies BBt) instead of (t implies Bt). To be sure: a machine is normal if for any proposition p, if the machine believes p, it will believe Bp. But this is equivalent with saying that for any proposition p, the proposition (Bp implies BBp) is true *about* the machine. Same remark for stability: you can say a machine is stable if all the propositions (BBp implies Bp) are true about the machine. This does not mean the stable or normal machine will ever believe being stable or normal. You have (momentarily) confuse a proposition being true on a machine, and being believe by a machine.

But 6 and 8 together mean that t implies a contradiction, hence I can conclude:

9. ~t

He is a knave. 7 then implies

10. Bt

I believe he is a knight. And if Bx implies x, then:

11. t

and I have reached a contradiction with 9.

So I don't think I am doing this right.

By taking into account the confusion above, you should be able to prove, with t still the same proposition (that is (t <-> -Bt)), that (in case you are a normal reasoner of type 1): if you are consistent, then t is not provable (believable, assertable by you) if you are consistent and stable, then -t is not provable either.

That's Godel's first incompleteness theorem. (once we eliminate the KK island from the reasoning to be sure). Bravo.

To sum up; any normal stable reasoner of type 1 meeting a knight saying "you will never believe I'm a knight" will be forever incomplete. (incomplete = there is a proposition like t, which is neither provable nor refutable). And so a machine cannot be omniscient because, although the KK island does not exist, the diagonalization lemma will supply the necessary believable self-referential propositions.

The distinction between "true about the machine" and "believed by the machine" is the key for the G / G* distinction.

Bruno

http://iridia.ulb.ac.be/~marchal/