>> There are far more elaborate proofs that *might* be wrong - the four
>> colour map theorum immediately leaps to mind - but when one speaks about
>> a proof so simple it can be stated in a few sentences... it's really
>> astonishingly unlikely to be wrong.
> 
> True.  But unlikely != impossible.

You realise that it's completely possible that at one point today you'll 
try to swallow a mouthful of water and accidentally inhale it, right? 
People actually *die* like this. But I don't see you worrying about it - 
because it's rather unlikely. And yet it is many, many times *more* 
likely than somebody solving the Halting Problem.

>> Well... that's very nice, but unless somebody proves that the laws of
>> logic as currently formulated have some really deeply *fundamental* flaw
>> [in which case all of mathematics and science as we currently understand
>> it is completely wrong], the halting problem isn't going to be disproved
>> any time soon.
> 
> Maybe.  But then again, throughout history there are examples of really 
> fundamental things needing to be adjusted.  Knowledge continues to grow.

Scientific facts have been found to be incorrect. There are far fewer 
examples of mathematical truths which have needed to be adjusted. And 
there are vanishingly few examples of widely accepted *proofs* that turn 
out to be wrong - it tends to be things lots of mathematicians "think" 
are true that eventually turn out to be disproven.

>> Let me be 100% clear about this: NO, even human beings CANNOT solve the
>> halting problem. (I have a simple and easy counterexample to this.)
>>
>> It is not a question of "not having good enough AI". It's a question of
>> "there is a proof of a dozen lines or so that shows that no Turing
>> machine program can ever exist which solves this problem".
> 
> This is the problem, though:  The assumption is that computing will 
> always use a Turing model, like I said.

And like I have explained multiple times, the problem isn't the Turing 
model. Even if we assume some as-yet unknown technology with miraculous 
[but not unlimited] powers, we still have an unsolvable problem. That's 
what is so significant about the Halting Problem. (I mean, face it, what 
*practical* use does HP have? None. It's importance is that it 
demonstrates that some problems are unsolvable.)

>> I would like to point out that even if you assume that some hypothetical
>> device exists which can easily solve the Turning machine halting
>> problem, there is now a *new* version of the halting problem (namely,
>> does a program for this new machine ever halt?) which will still be
>> unsolvable. And if you design a new machine that can somehow solve even
>> this new "super-halting problem", you just end up with a
>> super-super-halting problem. And so on ad infinitum.
> 
> Maybe.  It's hard to say that that would be the case, because the future 
> is unknowable.

You're missing my point: It doesn't *matter* that we can't know the 
future. Simple logical deduction demonstrates that ANY machine we can 
construct will have the same problem, REGARDLESS of how it works.

> Maybe the halting problem was a bad example to illustrate my point; the 
> bottom line on my point still stands, though.  What's "impossible" 
> yesterday became an everyday occurrence.  It was "impossible" that the 
> solar system was heliocentric a thousand years ago.  Today, it's common 
> knowledge that that is untrue.

Once again, you are talking about science.

In science, it is always possible that some "fact" could turn out to be 
partially or wholely wrong. We think we know how the universe works, but 
we could always be wrong about something.

Mathematics is different. Not quite as different as was originally 
believed, but still. In mathematics, we can construct absolute truths 
which will never be disproven until the end of the universe itself. The 
only question mark is the reliability of the human mind.

For sufficiently complicated proofs, it becomes not merely possible but 
*plausible* that some mistake could exist. For sufficiently simple 
proofs, we can be absolutely certain that only a fundamental flaw with 
renders all of mathematics invalid could disprove the theorum.

In summary: Science can never have absolute truths. Mathematics can.

>> Intelligence - artificial or not - isn't the problem. It's not that
>> nobody can work out *how* to do it, it's that IT'S IMPOSSIBLE.
> 
> Using today's technologies, maybe.  Again, we don't know what the future 
> holds.  It is impossible to use paper in transistors.  Or is it?

Making transistors out of paper is a question of physics - a branch of 
science. Infinite compression ratios is a question of mathematics. 
Therein lies the critical difference.

>> This is precisely my point: Solving the halting problem DOES defy the
>> laws of causality. It is NOT just a problem of technology. It is a
>> problem of "if this algorithm were to exist, it would cause a logical
>> paradox, regardless of the technology used".
> 
> There again, maybe I chose a poor example to illustrate my point.

I'm not sure what your point is.

If your point is that science is sometimes wrong, or at least needs to 
be amended, then I agree. If your point is that widely held beliefs are 
sometimes wrong, then I also agree. If your point is that every proven 
mathematical result could actually be wrong, then I completely disagree.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message