I'd like to talk about the psychology of why people sometimes feel
that Godel's and Turing's proofs are somehow cheats. Partly, it is
the fault of informal intuitive expositions of the results.
Both Godel's proof and Turing's proof have the flavor of using
self-reference to force someone to make a mistake. Both cases
seem a little like the following paradox (call it the "Gotcha"
You ask someone (we'll call him "Jack") to give a truthful
yes/no answer to the following question:
Will Jack's answer to this question be no?
Jack can't possibly give a correct yes/no answer to the question.
While the Gotcha paradox gives some of the flavor of Godel's
proof or Turing's proof, there is one big difference, and this
difference is what makes people feel like there is something
fishy going on: In the case of the Gotcha paradox, it
is possible for Jack to *know* the answer, but to be
prevented by the rules from *saying* the answer.
In other words, there is a gap between what Jack knows
and what he can say. He knows that the answer to the question
is "no", but he can't say that answer, because that would
make the answer incorrect. So this informal paradox doesn't
really reveal any limitations in Jack's knowledge---it's
just a quirk of the rules that prevents Jack from telling
the answer. It's a little like the following one-question
| 5 5 5 5 |
| How many 5's |
| appear inside |
| this box? |
| Answer: ___ |
If you write "5" in the space provided, then the correct answer
is "6", and if you write "6" the correct answer is "5". The fact
that you can't write the correct answer in the space provided
doesn't prove that you have problems counting.
Someone hearing some variant of the Gotcha paradox might be led
to think (as Peter Olcott and Herc do) that Godel's and Turing's
proofs might be cheats in a similar way.
Of course, the difference is that there is no "gap" involved in
Turing's or Godel's proofs. It makes no sense to suppose that
Peano Arithmetic really knows that the Godel statement is true,
but just can't say it, because there is no notion of PA "knowing"
something independently of what it can prove. In the case of Turing's
proof, given a purported solution H to the halting problem,
one comes up with a program Q(x) such that
Q halts on its own input if and only if H(Q,Q) = false
There is no sense in which H "knows" that the answer is true
but is unable to say it.
We could try to modify the Gotcha paradox to eliminate the gap
between what you know and what you can say. Let's consider the
following statement (called "U" for "Unbelievable").
U: Jack will never believe this statement.
Apparently, if Jack believes U, then U is false. So we are left
with two possibilities:
Either (A) Jack believes some false statement, or (B)
there is some true statement that Jack doesn't believe.
This is a lot like Godel's sentence G that shows that PA is
either inconsistent or incomplete. However, it still seems like
a joke, or a trick, rather than something that reveals any
limitations in Jack's knowledge. U doesn't seem to have any
real content, so who cares whether it is true or not, or whether
Jack believes it or not. It isn't a claim about anything tangible,
so who could ever tell if Jack believes it or not, or what it even
*means* for Jack to believe it?
Okay, let's try one more time to get something meaningful that
really reveals a gap in Jack's knowledge akin to Godel's
incompleteness. Suppose that at some future time, the mechanisms
behind the human mind are finally understood. Suppose that it is
possible to insert probes into a person's brain to discover what
the person is thinking, and what he believes.
So we take our subject, Jack, and hook him up with our brain scanning
machine. We give Jack a computer monitor on which we can display
statements for Jack to consider, and we connect his brain scanning
machine to a bell in such a way that if Jack agrees with the statement
on the screen (that is, if the scanning machine determines that Jack
believes the statement) then the bell will ring. Then we display
on the screen the following statement:
The bell will not ring.
Now, there is no way out for Jack. The statement is now a completely
concrete claim---there is no ambiguity about what it means, and there
is no ambiguity about whether it is true or false. There is no "knowledge
gap" possible---either Jack believes that the statement is true, or
Does Jack believe the statement, or not? It seems to me that in this
circumstance, Jack is forced to doubt his own reasoning ability, or
to doubt the truth of the circumstances (that the brain scanning machine
works as advertised, or that it is connected to the bell as described).
If he *really* believes in the soundness of his own reasoning, and he
really believes in the truth of the claims about the scanning machine,
then it logically follows that the bell will not ring. But as soon as
he makes that inference, the bell will ring, showing that he made a
mistake, somewhere. So the only way for Jack to avoid making a mistake
is if he considers it *possible* that he or his information is mistaken.
> Of course, the difference is that there is no "gap" involved in
> Turing's or Godel's proofs. It makes no sense to suppose that
> Peano Arithmetic really knows that the Godel statement is true,
> but just can't say it, because there is no notion of PA "knowing"
> something independently of what it can prove.
Cool examples (sources?) but I think there is more of a parallel than
that. The equivalent of PA knowing something is the fact that the
question definitely does have an an answer (true or false.)
Also, consider this parallel:
Liar: "This is not true." has no truth value.
Godel: "This is not provable." does have a truth value.
Conclusion: "True" and "provable" are not the same.
I have read that Goedel took great pains to avoid any ingredients
in his proof that could be misinterpreted as a source of paradox,
and hence was scrupulous in keeping all the reasoning
I think at least part of the distraction when it comes to Goedel's
theorem is that a formal system is described in the terms one
would use for a creature that "knows" things, and our intuitions
about knowledge run counter to facts about formal systems. If
the provability or knowability of X is written as X, then for
knowledge we have an intuition saying
 ( X -> X),
that for any X, we know that if we know X then it's true. On the
other hand for a standard type of formal system we have the
 ( X -> X) ->  X,
namely that it's a theorem that X is true if it's provable, only if
X is a theorem already independent of provability.
>If the provability or knowability of X is written as X, then for
>knowledge we have an intuition saying
>  ( X -> X),
>that for any X, we know that if we know X then it's true. On the
>other hand for a standard type of formal system we have the
>  ( X -> X) ->  X,
>namely that it's a theorem that X is true if it's provable, only if
>X is a theorem already independent of provability.
I think that rather than *knowing*, provability is closer to *believing*
While you can't know something that is false, you can believe something
that is false.
I'm not sure whether Lob's theorem applies to human belief, or not.
I don't think so, because human beliefs are really not deductively
closed. We can believe a bunch of things which, if we worked out
the logical consequences, would be inconsistent. But we don't believe
any out-and-out contradictions. So our beliefs don't necessarily
obey the rule
(A -> B) -> A -> B
2 & 3 are also not the same.
So HOW do you get rid of 2? do you only consider a subset of Godel numbers?
WHY STOP THERE? Why are mathematicians intent on consistency and consistency alone?
Why does Daryl insist this isn't a possible formula.
S = Forall x, isTrueFormula(x) <-> hasProof(x)
S, for SuperConsistent has a godel number too, just like liar statement, just like godel statement.
Why can't you just disprove Peters conjecture?
As Peter originally put it, the output of halt should reasonably be
expected to have 3 options :
1 / the input halts
2 / the input wont halt
3 / the input contains a reference to Halt()
there's some lack of mathematical ability around here alright, and ignoring
simple mathematical conjecture is its fertiliser.
That's not the objection. The objection is that
Jack's knowledge is not even knowledge, since
Jack is a fictous character. So Jack's
"knowledege" is nothing more Jack's
back-stage pass to a play written by
some amauter Shakespearian philosophers,
and published by unemployed
da...@atc-nycorp.com (Daryl McCullough) wrote
> Will Jack's answer to this question be no?
> Jack can't possibly give a correct yes/no answer to the question.
This appears to be correct, and, given the usual caveats surrounding this
topic, as clear-cut as it may be. That is, Jack CANNOT give a correct
yes/no answer to this question.
So we may ask, is this a "bad thing" ? I doubt it. Just as (as you later
point out) Godel and Turing and Cantor find ways around it, so can we here.
Certainly, Jack can make an effective *response* to the query, as Godel etc do.
Jack might easily give a correct answer, just not a "yes/no" answer.
He might say "Not at all", or suchlike. We might then reword the question
to include such possibilities. He might then observe that "Anyone else
answering the question would correctly say no, so make your deductions
from that"; a response which would find favour among political interviewees.
So could we re-word the question so extensively, that it would cover all
possible attempts by Jack to execute such workarounds? I doubt it.
We might think of trying something like,
"Will Jack's answer to this question be in the negative, either directly,
or indirectly by alluding to other matters that imply a negative answer?"
But I suspect all such attempts are doomed to failure. I suspect they are
doomed for the same old same-old reasons that always tend to apply here;
either they would prove to be too imprecisely worded to be of any use,
or they would admit a sufficiently cunning response by Jack that
could work around the restrictions by jumping up another level.
The whole thing has very much the smell of the attempt, a while ago, to try
to define precisely, "all possible precise definitions of a real number".
Whatever you do, you can jump beyond. To try to circumvent matters by
referring to "all possible negative repsonses" is a bit like asking about
the set of all sets. It just doesn't go.
We have learned to live with the non-existence of a set of all sets,
or of a defintion of all definitions, so it should be no sweat to live
with an question that excludes all answers.
So in sum, I assert, no, it is not a "bad thing", it is not worrying,
it is just another case of what always happens here.
The original question, "Will Jack's answer to this question be no?",
is no more worrying than saying,
"Please respond at length to this inquiry without communicating in any way."
It is not a worry. It doesn't even need responding to, really.
As with all these paradoxes -
- once you have seen the answer, there is no question left.
Bill Taylor W.Ta...@math.canterbury.ac.nz
"The auto-destruct mechanism just blew itself up!" -- Dr Strangelove
>da...@atc-nycorp.com (Daryl McCullough) wrote
>> Will Jack's answer to this question be no?
>> Jack can't possibly give a correct yes/no answer to the question.
>This appears to be correct, and, given the usual caveats surrounding this
>topic, as clear-cut as it may be. That is, Jack CANNOT give a correct
>yes/no answer to this question.
>So we may ask, is this a "bad thing"? ...
>Jack might easily give a correct answer, just not a "yes/no" answer.
>He might say "Not at all", or suchlike.
No, it's not a bad thing that Jack is unable (given the rules,
that the answer must be "yes" or "no") to give the correct answer.
If I put duct tape over his mouth, he'll be unable to give a
correct answer, but it doesn't mean anything about limitations
for Jack's *reasoning* ability. It's like the sick joke about
the sadistic scientist who is measuring the correlation between
the number of legs of an animal and how far it can jump: He
tells the test animal, a dog, "Jump, Fido!" and Fido jumps 8 feet.
The scientist writes down "Dog with 4 legs jumps 8 feet." He
amputates one leg, then says "Jump, Fido!" and Fido jumps 6 feet.
The scientist writes down "Dog with 3 legs jumps 6 feet." He
amputates the three remaining legs, recording how far Fido jumps.
Finally, when the poor dog has no legs whatsoever, the scientist
says "Jump, Fido!" Fido doesn't jump at all. He says "Jump, Fido!"
again, same result. The scientist then writes down "Dog with 0
legs cannot hear."
As I said in my post, this failure of Jack to give the correct
answer does *not* indicate any limitation in Jack's ability to
reason---instead, it indicates a "knowledge gap"; there is a
gap between what Jack knows and what Jack is able to convey
(within the rules, given his situation).
So is there any way to eliminate this knowledge gap? Maybe not,
but if we imagine that we have a device that can directly
measure what a person believes, then we could construct a
scenario for humans that was analogous to the incompleteness
theorem---a statement that causes a person to be uncertain
about the correctness of his own reasoning ability or knowledge:
I connect the "belief detector" to your brain and tell you
that I'm going to show you a statement on a computer screen.
I tell you that the detector is detected to a bell so that
if (within the next 60 seconds, say) you come to believe the
statement on the screen, the bell will ring, otherwise the
bell will not ring. Then I show you the statement "The bell
will not ring in the next 60 seconds."
Perhaps this thought experiment shows that there can be
no perfect belief detector. I think that's plausible---even
if we completely understood the way the brain works, there
will still be fuzziness about whether this or that brain
state constitutes being in the state of "believing statement
S". A set-up such as the one above would then be impossible,
since it requires an unambiguous yes/no answer to the question
"Does Jack believe S?"
> Perhaps this thought experiment shows that there can be
> no perfect belief detector.
I agree. In fact, this argument and thought experiment and conclusion,
were pretty much the subject of a similar essay by... I forget, it was
either in "Godel Escher Bach" or By Daniel Dennet in (possibly) "The Mind's I",
(great title for this sort of book, BTW!), or some similar work.
Maybe someone else can help me out with this reference? The protagonist was
trying to find out a subject's true beliefs, and invented such a machine,
and found the same paradox, was severely chastised by (the author) for having
been so irresponsible as to invent such a machine, possibly by causing
the universe to collapse in a great explosion of self-contradiction.
Well, maybe I'm embellishing my memory somewhat with that last bit;
but that was the theme.
> I think that's plausible--
Yes indeed! There are a great many reasons to suppose that we can never
precisely encompass anyone's beliefs, including our own. Or even that
the term has any precise meaning. But certainly the thought experiment
is a snazzy way of establishing this.
> -even if we completely understood the way the brain works,
Which is also different from understanding how any *particular* brain works;
but both seem to be permanently beyond the realm of the achievable, for
reasons of technical information storage if nothing else.
Just as the universe is its own fastest simulator, so is the brain its own
> there will still be fuzziness about whether this or that brain
> state constitutes being in the state of "believing statement S".
Precisely. That is also my exact belief! ;-)
Bill Taylor W.Ta...@math.canterbury.ac.nz
Free will the inability to predict what you are going to do next
I think you mean Raymond Smullyan's "An Epistemological Nightmare", which is
in _The Mind's I_ (Dennett and Hofstadter). Actually, it appears on the web