On Thu, 24 Jul 2008 22:07:08 +0100, Orchid XP v8 wrote:

>>> Right. And the fact that a mathematical proof of its impossibility
>>> doesn't matter either, right?
>> 
>> 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*.  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.

>>> How many years do you think it will be before somebody solves the
>>> halting problem, or develops a lossless compression algorithm with an
>>> infinite compression ratio?
>> 
>> Who knows?  Technology evolves over time.  Even 10 years ago, the idea
>> of having a computer the size of a notebook that was as powerful as a
>> then- current Cray supercomputer?  Yet here we are.
>> 
>> Can they be solved using current computing technologies?  Probably not.
>> Can they be solved with something that makes our current technology
>> look like a toy?  Possibly.  Who knows?
> 
> 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?

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.

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

> 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.  
It's true that it may never be solved, but if there's one thing humanity 
has proven through the ages is that we usually can find a way - we just 
have to think in ways we haven't thought before.

After all, two thousand years ago, the earth was flat because nobody 
could comprehend the idea that it wasn't.  Well, I say nobody - there 
were some who did, and they were branded as heretics and in many cases 
they were killed for it.  Turns out they were right.

Be a heretic. :-)

Jim

Post a reply to this message