On Fri, 25 Jul 2008 09:28:11 +0100, Invisible wrote:

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

Well, there you go. :-)

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

True.  But unlikely != impossible.

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

Maybe.  But then again, throughout history there are examples of really 
fundamental things needing to be adjusted.  Knowledge continues to grow.

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

This is the problem, though:  The assumption is that computing will 
always use a Turing model, like I said.

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

Maybe.  It's hard to say that that would be the case, because the future 
is unknowable.

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

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.

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

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?

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

Not necessarily in our ability to comprehend logic, but perhaps in our 
ways of understanding how to process it.

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

There again, maybe I chose a poor example to illustrate my point.

Jim

Post a reply to this message