>>> Mathematical proofs have been proven wrong before, you know.
>> Yes - but it's really extremely rare. Especially for very simple proofs.
>> The ones that turn out to be wrong are usually the highly complex ones.
> 
> True.  But as I said, not *impossible*.

Not impossible, no.

Also, taking a shattered piece of glass and throwing the pieces at each 
other in such a way that the individual atomic laticies just happen to 
line up perfectly and you end up with the original, unshattered piece of 
glass is perfectly "possible", it's merely "unlikely".

...unlikely enough that no sane person bothers worrying about it. 
Similarly, the proof of the impossibility of an infinite compression 
ratio is *so* absurdly trivial that the chances of it being wrong are 
vanishingly small.

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.

> I don't like absolutes when it 
> comes to things like this; people who think in absolutes usually limit 
> themselves, and also tend to have a very jaded view of the world.
> 
> To borrow a line from Patriot Games:  Shades of grey.  The world is 
> shades of grey.

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.

>> See, that's just it. The halting problem is unsolvable in a theoretical
>> computer with an infinite amount of memory, allowed to run for an
>> infinite amount of time. It's not a question of computers not being
>> "powerful enough", the problem is unsolvable even theoretically.
> 
> Using current thinking about how computers work.  If/when the computer 
> science geniuses crack true AI, then the halting problem can be solved, 
> can it not?  Can not humans evaluate the halting problem, at least in 
> limited cases?

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

> If you only thing in terms of turing machine-style computers, then you're 
> absolutely right.  But turing machines are not (or rather, may not be) 
> the end-all be-all of computing for the rest of the life of the universe.
> 
>> Unless quantum computing ever works some day, and it turns out to have
>> _fundamentally_ different capabilities, the halting problem will never
>> be solved.
> 
> *Bingo*, that's my point.  There's that "unless" phrase.

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.

The halting problem is not a consequence of the exact way a Turing 
machine works. It is a very basic consequence of simple logic, and 
applies to any hypothetical detministic machine. (That's WHY it's such 
an important result.)

>> The impossibility of a lossless compression algorithm with an infinite
>> compression ratio doesn't even depend on the model of computing used; it
>> is a trivial exercise in logic.
> 
> Again, someday we may have really exceptional AI that can figure this 
> stuff out, not based on current computing technologies.

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.

Now if we were talking about some phenominon of physics, there would be 
at least some degree of uncertainty - we might be wrong about one of the 
"laws" of physics. There could be some edge case we don't know about 
yet. (E.g., Newton's laws of motion aren't quite 100% correct.)

But we're talking about simple logic here. Unless there is some fatally 
dire flaw in our ability to comprehend logic [in which case, we're 
basically screwed anyway], infinite compression is entirely impossible, 
and always will be. It's not about current computer technologies; this 
is impossible for any deterministic technology that would hypothetically 
exist.

>> And *my* point is that some things are "impossible" because nobody has
>> yet figured out how, while other things are "impossible" because they
>> defy the laws of causality. And there's a rather bit difference.
> 
> Sure, but solving the halting problem or properly colouring a photo that 
> started in black and white is not something that defies the laws of 
> causality.  It merely defies our technological abilities at this time.

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

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

Post a reply to this message