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

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

Unless quantum computing ever works some day, and it turns out to have 
_fundamentally_ different capabilities, the halting problem will never 
be solved.

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.

> My point, though, is that there are people - even exceptionally smart 
> people - who say "no way no how is 'x' ever going to be possible" and 
> they're proven wrong.  Maybe not in their lifetimes, but who's to say 
> what's really possible?

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.

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

Post a reply to this message