 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 24 Jul 2008 21:31:19 +0100, Orchid XP v8 wrote:
>>> It's a basic premise of signal processing that you cannot recover data
>>> that isn't there any more. Shannon's theorum and all that.
>>>
>>> Whether you can *fake* something that "looks" right is another matter.
>>> But *recover*? No. Impossible.
>>
>> At least as far as we know today.
>
> 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.
> 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?
>> If you take a photo of something out of focus, you could never recover
>> the original picture again, right?
>>
>> Wrong. http://refocus-it.sourceforge.net/
>>
>> Pretty cool plugin. Even 5 years ago, something like this would have
>> been thought to be totally impossible.
>
> I've always thought that, logically, this ought to be possible in
> principle. I mean, defocusing is basically a convolution, so it should
> be possible to deconvolute it to some degree... (Similarly with echo
> cancellation.)
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?
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> If Canon had left RAW support in the point-and-shoot digicams, that would
> not have prevented power users to buy SLRs.
Maybe for most of them, but I'm sure there are a group of people who had to
strech their budgets etc to just be able to afford the cheapest Canon with
RAW support. If Canon offered RAW in their cheap models, they would surely
lose some sales of the more expensive models.
But like you say, I'm sure they worked all this out with simulations and
market research etc before making a decision, there is no way their finance
department would have allowed it otherwise ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> If Canon had left RAW support in the point-and-shoot digicams, that
>> would not have prevented power users to buy SLRs.
>
> Maybe for most of them, but I'm sure there are a group of people who had
> to strech their budgets etc to just be able to afford the cheapest Canon
> with RAW support. If Canon offered RAW in their cheap models, they
> would surely lose some sales of the more expensive models.
>
> But like you say, I'm sure they worked all this out with simulations and
> market research etc before making a decision, there is no way their
> finance department would have allowed it otherwise ;-)
>
>
There is also the cost that Canon would have associated if they did
leave RAW support enabled on the point-and-shoot cameras. That being the
cost price of tech support and returns from people who just do not
understand that format. JPEG is pretty well understood, to the extent it
needs to be, by people who just want to take a snap shot and email it to
the family. RAW formats aren't. Simple reason, Windows doesn't
automatically open the picture in preview, and if they just emailed the
RAW file to someone that person probably would not be able to open it.
I'd guess that Canon worked that information into their market research
before they did anything, as well.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
And lo on Thu, 24 Jul 2008 20:31:59 +0100, Jim Henderson
<nos### [at] nospam com> did spake, saying:
> On Thu, 24 Jul 2008 20:24:51 +0100, Orchid XP v8 wrote:
>
>>>> I meant you can't just give a machine a BW picture of a tree and have
>>>> it automatically know to turn it green. That's impossible.
>>>
>>> I don't know that to be the case. Again, a case of one's ability to
>>> fathom how something like that is done doesn't translate to "there's no
>>> way it could possibly be done".
>>
>> It's a basic premise of signal processing that you cannot recover data
>> that isn't there any more. Shannon's theorum and all that.
>>
>> Whether you can *fake* something that "looks" right is another matter.
>> But *recover*? No. Impossible.
>
> At least as far as we know today.
If the grains in the film reacted to colour in some currently unreadable
fashion and/or those alterations were transferred to the photo itself then
you could, in theory, recover colour from a B&W photo or film by reading
those imperfections.
--
Phil Cook
--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Phil Cook wrote:
>>> Whether you can *fake* something that "looks" right is another matter.
>>> But *recover*? No. Impossible.
>>
>> At least as far as we know today.
>
> If the grains in the film reacted to colour in some currently unreadable
> fashion and/or those alterations were transferred to the photo itself
> then you could, in theory, recover colour from a B&W photo or film by
> reading those imperfections.
Now *that* at least makes sense, hypothetically.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> 16 colours out of 16, verses 32 out of 4,096? Seems like a fairly big
>> difference to me. ;-)
>
> Yeh saying that, we've been stuck at 2^24 out of 2^24 for a while now...
> ;-)
Wasn't the Parhelia that board that did 10 bits per channel, back around
2004? It also offered tri-monitor support for "surround gaming", or
something.
I know people claim you can't tell the difference with more bits, but
honestly I still see banding in "truecolor" (ie 8 bits per channel) images.
I can't wait for the day that double precision colors become mainstream,
and DACs offer 16 or 32 bits per channel in the display :)
...Chambers
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Chambers wrote:
> I know people claim you can't tell the difference with more bits, but
> honestly I still see banding in "truecolor" (ie 8 bits per channel) images.
My laptop is 24-bit graphics modes. However, the physical display
hardware only supports 16-bit colour, and does dithering in hardware to
produce the rest. The end result is, obviously, horrid.
[But then my laptop's LCD is horrid anyway. No matter where you put your
head, only 50% of the display is visible at any time - the other 50%
shows up in negative. Talk about narrow viewing angle...!]
I can well understand somebody looking at a "24-bit image" on this
16-bit display and concluding that 24-bits is insufficient. But
honestly, on every *real* 24-bit display I've seen, there is no evidence
of banding at all. Hell, my sister has a gigantic 42-inch LCD TV in her
front room, and I'm watching digital TV and playing COD4 on a PS3, all
in 24-bit colour, and it looks damned *perfect*.
(...and then there are those people who claim to be able to tell the
difference between 44.1 kHz and 48 kHz digital audio - despite the
proven scientific impossibility of this feat.)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
