40 views

Skip to first unread message

Jun 25, 2004, 7:30:39 PM6/25/04

to

It is becoming increasingly clear that Peter Olcott and Herc have

no coherent mathematical argument for rejecting Godel's theorem

and Turing's proof of the unsolvability of the halting problem.

Their objections are really psychological---they feel that the

proofs are somehow a cheat, but they lack the mathematical ability

to say why.

no coherent mathematical argument for rejecting Godel's theorem

and Turing's proof of the unsolvability of the halting problem.

Their objections are really psychological---they feel that the

proofs are somehow a cheat, but they lack the mathematical ability

to say why.

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"

paradox).

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

quiz:

---------------

| 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

he doesn't.

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.

--

Daryl McCullough

Ithaca, NY

Jun 26, 2004, 12:19:43 PM6/26/04

to

da...@atc-nycorp.com (Daryl McCullough) wrote

> 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.

Charlie Volkstorf

Cambridge, MA

Jun 27, 2004, 5:00:12 PM6/27/04

to

In article <cbici...@drn.newsguy.com>, da...@atc-nycorp.com (Daryl

McCullough) writes:

|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.

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

"combinatorial".

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

almost opposite

[] ([] 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.

Keith Ramsay

Jun 27, 2004, 6:27:02 PM6/27/04

to

KRamsay says...

>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

>almost opposite

>

> [] ([] 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

Jun 29, 2004, 7:01:00 AM6/29/04

to

"Charlie-Boo" <ch...@aol.com> wrote in

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.

Herc

Jun 30, 2004, 4:12:39 AM6/30/04

to

da...@atc-nycorp.com (Daryl McCullough) wrote in message news:<cbici...@drn.newsguy.com>...

> It is becoming increasingly clear that Peter Olcott and Herc have

> no coherent mathematical argument for rejecting Godel's theorem

> and Turing's proof of the unsolvability of the halting problem.

> Their objections are really psychological---they feel that the

> proofs are somehow a cheat, but they lack the mathematical ability

> to say why.

>

> 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"

> paradox).

>

> 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.

> It is becoming increasingly clear that Peter Olcott and Herc have

> no coherent mathematical argument for rejecting Godel's theorem

> and Turing's proof of the unsolvability of the halting problem.

> Their objections are really psychological---they feel that the

> proofs are somehow a cheat, but they lack the mathematical ability

> to say why.

>

> 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"

> paradox).

>

> 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.

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

street-walker mathematicians.

Jun 30, 2004, 11:19:48 PM6/30/04

to

Nice essay Daryl. This little bit specially caught my eye...

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

-----------------------------------------------------------------------------

Jul 1, 2004, 9:06:28 AM7/1/04

to

Jul 1, 2004, 9:27:30 AM7/1/04

to

Bill Taylor says...

>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?"

Jul 2, 2004, 12:51:27 AM7/2/04

to

da...@atc-nycorp.com (Daryl McCullough) wrote

> 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

best interpreter.

> 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

------------------------------------------------------------------------------

Jul 2, 2004, 4:47:08 AM7/2/04

to

Bill Taylor wrote in message

<716e06f5.04070...@posting.google.com>...

>da...@atc-nycorp.com (Daryl McCullough) wrote

>

>> 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.

<716e06f5.04070...@posting.google.com>...

>da...@atc-nycorp.com (Daryl McCullough) wrote

>

>> 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.

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

here:

http://www.rdegraaf.nl/index.asp?sND_ID=708558

--- Jeff

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu