On Thu, 24 Jul 2008 17:00:48 +0100, Invisible wrote:

>>> Yeah, but only with human intervention. You don't just press a button
>>> and out pops an image with colours that correctly match the original.
>> 
>> As the original is B&W, that doesn't make sense...
> 
> 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".

> You must have a
> human there, and they must know what the hell the colours are supposed
> to be.

Maybe.  Maybe not.  Depends on how advanced the technology is.  It 
certainly isn't an *easy* problem to solve, I'll grant that.  
Impossible?  Smarter people than me have figured out how to do things I 
thought weren't possible.

"Any sufficiently advanced technology is indistinguishable from magic."

Jim

Post a reply to this message

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

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

Post a reply to this message

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.

A couple centuries ago, people also believed that if someone's heart 
stopped beating it couldn't be restarted and they were dead forever.  We 
know that to not be the case in all circumstances today.

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.

Jim

Post a reply to this message

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

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?

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

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

Post a reply to this message

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] nospamcom> 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

Invisible <voi### [at] devnull> wrote:
> 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.

  The end result would often be more horrid without the dithering. The
second image at http://en.wikipedia.org/wiki/Ordered_dithering is a rather
good example of how dithering can actually help the quality of the image,
even if the dithering algorithm is braindead simple.

-- 
                                                          - Warp

Post a reply to this message

>> 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.
> 
>   The end result would often be more horrid without the dithering.

Undoubtably so. But all the dithering in the world can't really compare 
to having propper shades. (Unless the spatial resolution is *very* high. 
This is how printers get away with it...)

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

Post a reply to this message

On Fri, 25 Jul 2008 11:13:52 +0100, Phil Cook wrote:

> And lo on Thu, 24 Jul 2008 20:31:59 +0100, Jim Henderson
> <nos### [at] nospamcom> 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.

That's kinda what I'm thinking.

Jim

Post a reply to this message

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

>> 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.
> 
> That's kinda what I'm thinking.

...so in other words, hypothetically the information might not be 
"gone". If that were indeed the case, it is at least plausible that 
somebody could possibly get it back, yes.

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

Post a reply to this message

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

You realise that it's completely possible that at one point today you'll 
try to swallow a mouthful of water and accidentally inhale it, right? 
People actually *die* like this. But I don't see you worrying about it - 
because it's rather unlikely. And yet it is many, many times *more* 
likely than somebody solving the Halting Problem.

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

Scientific facts have been found to be incorrect. There are far fewer 
examples of mathematical truths which have needed to be adjusted. And 
there are vanishingly few examples of widely accepted *proofs* that turn 
out to be wrong - it tends to be things lots of mathematicians "think" 
are true that eventually turn out to be disproven.

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

And like I have explained multiple times, the problem isn't the Turing 
model. Even if we assume some as-yet unknown technology with miraculous 
[but not unlimited] powers, we still have an unsolvable problem. That's 
what is so significant about the Halting Problem. (I mean, face it, what 
*practical* use does HP have? None. It's importance is that it 
demonstrates that some problems are unsolvable.)

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

You're missing my point: It doesn't *matter* that we can't know the 
future. Simple logical deduction demonstrates that ANY machine we can 
construct will have the same problem, REGARDLESS of how it works.

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

Once again, you are talking about science.

In science, it is always possible that some "fact" could turn out to be 
partially or wholely wrong. We think we know how the universe works, but 
we could always be wrong about something.

Mathematics is different. Not quite as different as was originally 
believed, but still. In mathematics, we can construct absolute truths 
which will never be disproven until the end of the universe itself. The 
only question mark is the reliability of the human mind.

For sufficiently complicated proofs, it becomes not merely possible but 
*plausible* that some mistake could exist. For sufficiently simple 
proofs, we can be absolutely certain that only a fundamental flaw with 
renders all of mathematics invalid could disprove the theorum.

In summary: Science can never have absolute truths. Mathematics can.

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

Making transistors out of paper is a question of physics - a branch of 
science. Infinite compression ratios is a question of mathematics. 
Therein lies the critical difference.

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

I'm not sure what your point is.

If your point is that science is sometimes wrong, or at least needs to 
be amended, then I agree. If your point is that widely held beliefs are 
sometimes wrong, then I also agree. If your point is that every proven 
mathematical result could actually be wrong, then I completely disagree.

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

Post a reply to this message

Invisible wrote:
>>> Yeah, but only with human intervention. You don't just press a button
>>> and out pops an image with colours that correctly match the original.
>>
>> As the original is B&W, that doesn't make sense...
> 
> 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. You must have a 
> human there, and they must know what the hell the colours are supposed 
> to be.
> 

Right. The restorations shown in the posts above did require some human 
intervention. The one of the baby (me) in the gold chair gave some weird 
blotchiness in the gold color, so that had to be cleaned up, basically 
using a colorization technique.

But, generally human intervention is required to do the best at 
correction and restoration. I can't just push a button that says "Fix 
cracks", I have to at the very minimum tell it where those cracks are 
that I want fixed.

You have PS elements, right? Find a picture that's scratched and use the 
healing (or spot healing) brush on the scratches. The brush looks like a 
bandage. I know the tool exists in Elements. I use a lot of Clone and 
Heal, often both to get the results. I should upload a copy of the 
layers palette of the images to give you an idea as to how much is 
really involved.

Post a reply to this message

Orchid XP v8 wrote:

> 
> Whether you can *fake* something that "looks" right is another matter. 
> But *recover*? No. Impossible.
> 

Or, you find another source for the missing data.

Post a reply to this message

Jim Henderson wrote:

> 
> Wrong.  http://refocus-it.sourceforge.net/
> 

Ooh, new toy! Could prove to be very useful!

Post a reply to this message

Mike Raiford wrote:

> You have PS elements, right? Find a picture that's scratched and use the 
> healing (or spot healing) brush on the scratches. The brush looks like a 
> bandage. I know the tool exists in Elements. I use a lot of Clone and 
> Heal, often both to get the results. I should upload a copy of the 
> layers palette of the images to give you an idea as to how much is 
> really involved.

I don't know about you, but every time *I* look at either the GIMP or 
PhotoShop, I can never figure out what magical trick I'm missing that 
lets you do the impressive stuff everybody else does. To me, it just 
seems to be a small set of pretty simple tools that don't appear to give 
you much power to do anything.

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

Post a reply to this message

Invisible wrote:

> 
> All I know is that when I take a dark image and try to make it brighter, 
> it comes out hopelessly noisy.
> 

As you push those low RGB values up, values in-between maintain their 
relationship by scaling. You're also scaling the baseline noise of your 
camera. S/N ratio is still the same, the only difference is that there 
was very little signal to begin with. You might be able to stretch this 
a small amount, using a noise reduction algorithm, but this will eat 
details, which you have very little of, so the image will be soft and 
begin to show artifacts. You could also take advantage of human 
perception of color and smooth the color channels, which will reduce the 
apparent color noise, you'll still have luminance noise, but this is 
generally regarded as more pleasant than chroma noise.

Also, with 8 bit images, the risk of posterization becomes greater the 
more drastic the changes. You only have 32 levels to work with in an 
image that is underexposed by 3 stops. (which would be rather dark) as 
opposed to 256 levels had the image been properly exposed in the first 
place. Now, lets say you have an image that had been recorded in 12 
bit-- which is common in most digital SLR's, though 14bit is becoming 
more common-- , now that same image has 512 levels, therefore on current 
displays and print technologies, there really is no posterization. This 
gives a much greater lattitude when performing color adjustments.

Post a reply to this message

Nicolas Alvarez wrote:

> I definitely remember Windows 98 slowly redrawing the desktop as if it was
> raytracing the damned wallpaper, while the hard disk made horrible
> insane-seeking noises.

I remember that, too. I attributed it to the Wallpaper being somewhat 
dispensable, and being swapped to disk as soon as memory was being 
needed by the application.

What was more likely happening is as applications are opened, and worked 
with, more memory is needed, and the least recently used block happened 
to be the wallpaper.

You minimize a few windows, The desktop is made visible again, 
Explorer's paint routine for the background is executed, it hits the 
image, and gets a page fault, Windows then gets that page from memory, 
GDI draws a bit of the image, hits another page fault, etc... until the 
image is painted in, All the while paging out more data from other apps 
to draw the background. These other apps may need the data just paged 
out, and so begins the harddrive-pounding swap.

Adding more RAM usually resolved the problem. ;) 3MB in a 16MB memory 
space is an awful heavy load on memory for something like a pretty 
background. (Based on a 1024x768 32bpp screen, not unheard of in those days)

Post a reply to this message

On Tue, 29 Jul 2008 09:12:12 -0500, Mike Raiford wrote:

> Jim Henderson wrote:
> 
> 
>> Wrong.  http://refocus-it.sourceforge.net/
>> 
>> 
> Ooh, new toy! Could prove to be very useful!

It's not easy to use, and documentation is thin - but I've found it 
useful as well.

Jim

Post a reply to this message

On Tue, 29 Jul 2008 09:23:54 +0100, Invisible wrote:

>> True.  But unlikely != impossible.
> 
> You realise that it's completely possible that at one point today you'll
> try to swallow a mouthful of water and accidentally inhale it, right?
> People actually *die* like this. But I don't see you worrying about it -
> because it's rather unlikely. And yet it is many, many times *more*
> likely than somebody solving the Halting Problem.

Have you calculated the odds of both? ;-)

We're not talking about comparative probabilities.  Impossible means *no* 
chance of it ever happening.

>> Maybe.  But then again, throughout history there are examples of really
>> fundamental things needing to be adjusted.  Knowledge continues to
>> grow.
> 
> Scientific facts have been found to be incorrect. There are far fewer
> examples of mathematical truths which have needed to be adjusted. And
> there are vanishingly few examples of widely accepted *proofs* that turn
> out to be wrong - it tends to be things lots of mathematicians "think"
> are true that eventually turn out to be disproven.

Exactly my point, but with a narrower focus.  Things lots of *people* 
"think" are true sometimes/frequently/often turn out to be disproven.

>> This is the problem, though:  The assumption is that computing will
>> always use a Turing model, like I said.
> 
> And like I have explained multiple times, the problem isn't the Turing
> model. Even if we assume some as-yet unknown technology with miraculous
> [but not unlimited] powers, we still have an unsolvable problem. That's
> what is so significant about the Halting Problem. (I mean, face it, what
> *practical* use does HP have? None. It's importance is that it
> demonstrates that some problems are unsolvable.)

<sigh>  We're going in circles here....

>> Maybe.  It's hard to say that that would be the case, because the
>> future is unknowable.
> 
> You're missing my point: It doesn't *matter* that we can't know the
> future. Simple logical deduction demonstrates that ANY machine we can
> construct will have the same problem, REGARDLESS of how it works.

It's simple logical deduction that unless I have a screwdriver, I can't 
drive a screw.

Until you realise that the screw has a hex head and an allen wrench will 
do the job just as nicely.

*Sometimes* all you need is a new tool.  Sometimes the new tool hasn't 
been invented yet.

>> 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.
> 
> Once again, you are talking about science.
> 
> In science, it is always possible that some "fact" could turn out to be
> partially or wholely wrong. We think we know how the universe works, but
> we could always be wrong about something.
> 
> Mathematics is different. Not quite as different as was originally
> believed, but still. In mathematics, we can construct absolute truths
> which will never be disproven until the end of the universe itself. The
> only question mark is the reliability of the human mind.

I think it's a mistake to say "we know all there is to ever know about 
'x'".  There have been many points in history where humankind has made 
such declarations about many things - including mathematics - and it has 
turned out that we'd only scratched the surface.  It's the height of 
hubris to assume we can't learn anything new.

> For sufficiently complicated proofs, it becomes not merely possible but
> *plausible* that some mistake could exist. For sufficiently simple
> proofs, we can be absolutely certain that only a fundamental flaw with
> renders all of mathematics invalid could disprove the theorum.
> 
> In summary: Science can never have absolute truths. Mathematics can.

Sometimes the devil is in the details (and how detailed your data is).

>> 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?
> 
> Making transistors out of paper is a question of physics - a branch of
> science. Infinite compression ratios is a question of mathematics.
> Therein lies the critical difference.

And yet you agreed with another post in this thread that said that 
something was possible.  Look at the refocusing capabilities of some of 
the tools for that to reconstruct detail in blurred images.  Blurring is 
lossy compression, yet being able to recover that data isn't impossible; 
that's been proven.

>>> 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.
> 
> I'm not sure what your point is.

That I chose a poor example.

> If your point is that science is sometimes wrong, or at least needs to
> be amended, then I agree. If your point is that widely held beliefs are
> sometimes wrong, then I also agree. If your point is that every proven
> mathematical result could actually be wrong, then I completely disagree.

I believe that's just a limitation of our understanding of things as they 
are now.

Jim

Post a reply to this message

Invisible wrote:

> 
> I don't know about you, but every time *I* look at either the GIMP or 
> PhotoShop, I can never figure out what magical trick I'm missing that 
> lets you do the impressive stuff everybody else does. To me, it just 
> seems to be a small set of pretty simple tools that don't appear to give 
> you much power to do anything.
> 

There are lots of tools, though. Some are quite sophisticated, such as 
the aforementioned healing brush. Layers, masking and blend modes are 
also quite powerful features.

If you look at the brush tool in PS, it's extremely powerful, pressure 
sensitive, can create brush strokes that splatter and scatter, etc, PSE 
is significantly neutered, though and had much less options on the brush 
tool.

Post a reply to this message

>> Scientific facts have been found to be incorrect. There are far fewer
>> examples of mathematical truths which have needed to be adjusted. And
>> there are vanishingly few examples of widely accepted *proofs* that turn
>> out to be wrong - it tends to be things lots of mathematicians "think"
>> are true that eventually turn out to be disproven.
> 
> Exactly my point, but with a narrower focus.  Things lots of *people* 
> "think" are true sometimes/frequently/often turn out to be disproven.

Show me one single mathematical result which was *proven* to be true, 
and verified independently by a large number of mathematicians, and 
subsequently turned out to actually be false.

I can think of any number of results in *science* that were widely 
believed to be true but turned out not to be. But mathematics is different.

>> You're missing my point: It doesn't *matter* that we can't know the
>> future. Simple logical deduction demonstrates that ANY machine we can
>> construct will have the same problem, REGARDLESS of how it works.
> 
> It's simple logical deduction that unless I have a screwdriver, I can't 
> drive a screw.
> 
> Until you realise that the screw has a hex head and an allen wrench will 
> do the job just as nicely.
> 
> *Sometimes* all you need is a new tool.  Sometimes the new tool hasn't 
> been invented yet.

And I suppose next you'll be telling me that some day, some future 
technology might enable us to find a sequence of chess moves whereby a 
bishop can get from a black square to a white square, despite it being 
trivially easy to mathematically prove the impossibility of this...

> I think it's a mistake to say "we know all there is to ever know about 
> 'x'".  There have been many points in history where humankind has made 
> such declarations about many things - including mathematics - and it has 
> turned out that we'd only scratched the surface.  It's the height of 
> hubris to assume we can't learn anything new.

I'm not claiming that nothing new can be learned - I am saying that, at 
least in mathematics, learning new things doesn't invalidate what we 
already know.

>> Making transistors out of paper is a question of physics - a branch of
>> science. Infinite compression ratios is a question of mathematics.
>> Therein lies the critical difference.
> 
> And yet you agreed with another post in this thread that said that 
> something was possible.  Look at the refocusing capabilities of some of 
> the tools for that to reconstruct detail in blurred images.  Blurring is 
> lossy compression, yet being able to recover that data isn't impossible; 
> that's been proven.

Hey, guess what? Blurring isn't compression. It might *look* like it is, 
but it isn't.

>> If your point is that science is sometimes wrong, or at least needs to
>> be amended, then I agree. If your point is that widely held beliefs are
>> sometimes wrong, then I also agree. If your point is that every proven
>> mathematical result could actually be wrong, then I completely disagree.
> 
> I believe that's just a limitation of our understanding of things as they 
> are now.

Sure. And no doubt some day we'll discover that 2+2 isn't actually 4. I 
won't hold by breath for that though. :-P

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

Post a reply to this message

>> Whether you can *fake* something that "looks" right is another matter. 
>> But *recover*? No. Impossible.
> 
> Or, you find another source for the missing data.

Yeah, but that wouldn't be "recovering" the data, that would be getting 
it from another source. ;-)

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

Post a reply to this message

>> I definitely remember Windows 98 slowly redrawing the desktop as if it 
>> was
>> raytracing the damned wallpaper, while the hard disk made horrible
>> insane-seeking noises.
> 
> I remember that, too. I attributed it to the Wallpaper being somewhat 
> dispensable, and being swapped to disk as soon as memory was being 
> needed by the application.

It just amused me that a 33 MHz machine would struggle so much to draw 
16 colour graphics when my puny little 7 MHz Amiga could draw 32 colour 
graphics instantly, and at higher resolutions...

...and then, like I said, the Amiga's hardware stood still for 10 years. 
Kinda lost the edge after that.

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

Post a reply to this message

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

Quantum computing (today) doesn't even solve NP problems in P time, let 
alone non-computable problems. :-)

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message

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

No, computing doesn't today using a Turing model, and the Halting 
problem applies to many more computing models than the Turing model.

The Halting problem isn't solvable. If you come up with a new computing 
model that "solves" it, what you're solving isn't the halting problem 
any more.

It's like arguing "Maybe 2+2 will equal 6 some day, if 2 turns into 3." 
But if 2 turns into 3, you're not longer adding 2+2.

The halting problem is a precisely defined mathematical construct. Maybe 
  newer computing models might conceivably obsolete the implications of 
the halting problem, but they won't actually negate its proof. (In the 
same sense, that computers are far faster may obsolete the problems 
caused by some algorithms taking O(N^3) instructions, but that doesn't 
make the algorithm take fewer instructions.)

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message

scott wrote:
> But "fine" is nowhere near what you see in real life. 

I'm pretty sure it is. Try going to where you took that photo, looking 
at the wall, and without moving your eyes, see if you can see the 
details in the clouds. Then look at the clouds, and without moving your 
eyes, see if you can see the detail on the wall.

Even medical X-Rays only use 12 bits of greyscale.

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message

On Tue, 29 Jul 2008 09:10:38 +0100, Invisible wrote:

>>> 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.
>> 
>> That's kinda what I'm thinking.
> 
> ...so in other words, hypothetically the information might not be
> "gone". If that were indeed the case, it is at least plausible that
> somebody could possibly get it back, yes.

Oh, the information could well be gone, but it could be reconstructed 
from the available data.

Kinda like rebuilding a RAID-5 array using parity data.

Jim

Post a reply to this message

On Tue, 29 Jul 2008 18:17:34 +0100, Orchid XP v8 wrote:

>>> Scientific facts have been found to be incorrect. There are far fewer
>>> examples of mathematical truths which have needed to be adjusted. And
>>> there are vanishingly few examples of widely accepted *proofs* that
>>> turn out to be wrong - it tends to be things lots of mathematicians
>>> "think" are true that eventually turn out to be disproven.
>> 
>> Exactly my point, but with a narrower focus.  Things lots of *people*
>> "think" are true sometimes/frequently/often turn out to be disproven.
> 
> Show me one single mathematical result which was *proven* to be true,
> and verified independently by a large number of mathematicians, and
> subsequently turned out to actually be false.

The most obvious answer I can provide (but I don't know how many 
confirmed the proof) is Fermat's Last Theorem - at least from my read, it 
was proven for n=3 in the 10th century, but the proof was later 
invalidated.

A correct proof was later constructed in the mid-20th century, again, 
from what I understand.

>> It's simple logical deduction that unless I have a screwdriver, I can't
>> drive a screw.
>> 
>> Until you realise that the screw has a hex head and an allen wrench
>> will do the job just as nicely.
>> 
>> *Sometimes* all you need is a new tool.  Sometimes the new tool hasn't
>> been invented yet.
> 
> And I suppose next you'll be telling me that some day, some future
> technology might enable us to find a sequence of chess moves whereby a
> bishop can get from a black square to a white square, despite it being
> trivially easy to mathematically prove the impossibility of this...

You're still missing my point....

>> I think it's a mistake to say "we know all there is to ever know about
>> 'x'".  There have been many points in history where humankind has made
>> such declarations about many things - including mathematics - and it
>> has turned out that we'd only scratched the surface.  It's the height
>> of hubris to assume we can't learn anything new.
> 
> I'm not claiming that nothing new can be learned - I am saying that, at
> least in mathematics, learning new things doesn't invalidate what we
> already know.

Except that it can.  That was demonstrated in the example I provided 
above - proof done, proof invalidated, new proof done again.  Will the 
new proof be invalidated?  Probably not, but who's to say it never will 
be?

>> And yet you agreed with another post in this thread that said that
>> something was possible.  Look at the refocusing capabilities of some of
>> the tools for that to reconstruct detail in blurred images.  Blurring
>> is lossy compression, yet being able to recover that data isn't
>> impossible; that's been proven.
> 
> Hey, guess what? Blurring isn't compression. It might *look* like it is,
> but it isn't.

My point is that there's plenty of examples where raw data is lost but it 
can be reconstructed.

> Sure. And no doubt some day we'll discover that 2+2 isn't actually 4. I
> won't hold by breath for that though. :-P

Well, who knows?  There are ancient civilizations that had no concept of 
zero.  The introduction of imaginary numbers didn't come along until the 
late 1500s.  Up until that point, sqrt(-1) was undefined.

Who knows what we don't know about mathematics even today?

Jim

Post a reply to this message

On Tue, 29 Jul 2008 11:42:47 -0700, Darren New wrote:

> Jim Henderson wrote:
>> This is the problem, though:  The assumption is that computing will
>> always use a Turing model, like I said.
> 
> No, computing doesn't today using a Turing model, and the Halting
> problem applies to many more computing models than the Turing model.
> 
> The Halting problem isn't solvable. If you come up with a new computing
> model that "solves" it, what you're solving isn't the halting problem
> any more.
> 
> It's like arguing "Maybe 2+2 will equal 6 some day, if 2 turns into 3."
> But if 2 turns into 3, you're not longer adding 2+2.
> 
> The halting problem is a precisely defined mathematical construct. Maybe
>   newer computing models might conceivably obsolete the implications of
> the halting problem, but they won't actually negate its proof. (In the
> same sense, that computers are far faster may obsolete the problems
> caused by some algorithms taking O(N^3) instructions, but that doesn't
> make the algorithm take fewer instructions.)

Well, like I said, perhaps I chose a bad example - I should stick to 
things I know, maybe.  :-)

Jim

Post a reply to this message

On Tue, 29 Jul 2008 18:18:16 +0100, Orchid XP v8 wrote:

>>> Whether you can *fake* something that "looks" right is another matter.
>>> But *recover*? No. Impossible.
>> 
>> Or, you find another source for the missing data.
> 
> Yeah, but that wouldn't be "recovering" the data, that would be getting
> it from another source. ;-)

Which is often what data recovery *is* - reconstruction based on 
available data.

Jim

Post a reply to this message

On Tue, 29 Jul 2008 15:19:10 +0100, Invisible wrote:

> Mike Raiford wrote:
> 
>> You have PS elements, right? Find a picture that's scratched and use
>> the healing (or spot healing) brush on the scratches. The brush looks
>> like a bandage. I know the tool exists in Elements. I use a lot of
>> Clone and Heal, often both to get the results. I should upload a copy
>> of the layers palette of the images to give you an idea as to how much
>> is really involved.
> 
> I don't know about you, but every time *I* look at either the GIMP or
> PhotoShop, I can never figure out what magical trick I'm missing that
> lets you do the impressive stuff everybody else does. To me, it just
> seems to be a small set of pretty simple tools that don't appear to give
> you much power to do anything.

ie, they allow you to do the "impossible". ;-)

(which is my point - don't let the limits of what you know - or what 
humankind collectively knows - define what is possible and what is not)

Jim

Post a reply to this message

>> Show me one single mathematical result which was *proven* to be true,
>> and verified independently by a large number of mathematicians, and
>> subsequently turned out to actually be false.
> 
> The most obvious answer I can provide (but I don't know how many 
> confirmed the proof) is Fermat's Last Theorem - at least from my read, it 
> was proven for n=3 in the 10th century, but the proof was later 
> invalidated.
> 
> A correct proof was later constructed in the mid-20th century, again, 
> from what I understand.

See, now from what I understand,

1. Fermat claimed to have a proof, but to this day nobody knows what it was.

2. In the intervining several centuries, various proofs have been put 
forward. Some special cases were successfully proven. Some proofs put 
forward were quickly shown to be incorrect.

3. Recently a group of related mathematical proofs finally settled the 
matter.

I am not aware - despite possessing a book detailing the entire history 
of Fermat's Last Theorum - of any proof that was widely held to be 
correct for a long time before being found wrong. All the incorrect 
proofs were discovered to be incorrect fairly quickly.

It's easy for one person to make a mistake. (I saw a very neat example 
of this actually...) It's rather rarer for a large body of 
mathematicians to all fail to spot a flaw. Usually once a theorum gets a 
propper peer review, you can state the validity or otherwise of the 
proof with a pretty high degree of confidence. [Depending on how complex 
the proof is, of course...]

One of the reasons the Four Colour Map "proof" is not widely accepted is 
that it's just about impossibly to peer review it properly. Obviously 
the authors think it's correct, but nobody can easily check it, so it 
could actually be balony. [Regardless of whether the thing it's trying 
to prove is actually correct or not.]

>> And I suppose next you'll be telling me that some day, some future
>> technology might enable us to find a sequence of chess moves whereby a
>> bishop can get from a black square to a white square, despite it being
>> trivially easy to mathematically prove the impossibility of this...
> 
> You're still missing my point....

You're still missing *my* point. :-P

>>> And yet you agreed with another post in this thread that said that
>>> something was possible.  Look at the refocusing capabilities of some of
>>> the tools for that to reconstruct detail in blurred images.  Blurring
>>> is lossy compression, yet being able to recover that data isn't
>>> impossible; that's been proven.
>> Hey, guess what? Blurring isn't compression. It might *look* like it is,
>> but it isn't.
> 
> My point is that there's plenty of examples where raw data is lost but it 
> can be reconstructed.

Blurring doesn't actuallly "lose" nearly as much data as you'd think. 
That's why it can be mostly reversed.

>> Sure. And no doubt some day we'll discover that 2+2 isn't actually 4. I
>> won't hold by breath for that though. :-P
> 
> Well, who knows?  There are ancient civilizations that had no concept of 
> zero.  The introduction of imaginary numbers didn't come along until the 
> late 1500s.  Up until that point, sqrt(-1) was undefined.
> 
> Who knows what we don't know about mathematics even today?

If I were you, I'd be far more worried about the sky falling - it's 
about as logically plausible...

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

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> 1. Fermat claimed to have a proof, but to this day nobody knows what it was.

  Some people have the opinion that, regardless of being an exceptionally
gifted mathematician, Fermat was simply wrong when he wrote that margin
note.

  There's some evidence of this. IIRC, Fermat provided proofs for the cases
n=3 and n=4 some time *after* he wrote that margin note. Why would he do
that if he had a simple proof for *all* values of n?

  The most logical explanation is that Fermat was wrong, realized it
himself some time after, and then proceded studying his own theorem
further by, among other things, giving proofs for n=3 and n=4. He simply
didn't go back and erase the margin note (maybe he just forgot about it).

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
> (Kinda amusing how not denying access to data is a "feature", eh?)

http://www.fsf.org/blogs/community/antifeatures

Post a reply to this message

scott wrote:
>> Well... it looks fine to me, that's all I'm saying. ;-)
> 
> But "fine" is nowhere near what you see in real life.  While there is
> still an obvious gap between real life and what you can reproduce, there
> will no doubt be improvements in the future.

"But this is HDTV. It's got better resolution than the real world."

Post a reply to this message

>> 1. Fermat claimed to have a proof, but to this day nobody knows what it was.
> 
>   Some people have the opinion that, regardless of being an exceptionally
> gifted mathematician, Fermat was simply wrong when he wrote that margin
> note.

That seems perfectly plausible to me...

Some have also speculated that Fermat spotted a "simple" proof that has 
eluded the rest of the community for over 300 years. This seems rather 
less plausible.

(The modern day proof could not possibly be the one Fermat had. Well, I 
mean, unless he invented several entire branches of mathematics in his 
head that day...)

Some folks think he might have had a broken proof similar to Cauchy, but 
not realised it was broken. The margin note looks like an off-hand 
remark, so maybe he didn't check it out too much... People certainly 
make mistakes.

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

Post a reply to this message

>> Unless quantum computing ever works some day, and it turns out to have 
>> _fundamentally_ different capabilities, the halting problem will never 
>> be solved.
> 
> Quantum computing (today) doesn't even solve NP problems in P time, let 
> alone non-computable problems. :-)

But you get what I'm saying. Maybe there is some fundamentally new 
system that changes the rules, so to speak.

Even if such a system were to exist, you would still have a new, 
generalised Halting Problem, and you're back to square one.

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

Post a reply to this message

>> I don't know about you, but every time *I* look at either the GIMP or
>> PhotoShop, I can never figure out what magical trick I'm missing that
>> lets you do the impressive stuff everybody else does. To me, it just
>> seems to be a small set of pretty simple tools that don't appear to give
>> you much power to do anything.
> 
> ie, they allow you to do the "impossible". ;-)
> 
> (which is my point - don't let the limits of what you know - or what 
> humankind collectively knows - define what is possible and what is not)

And my point - which you seem hell-bent on ignoring - is that there is a 
difference between "we don't know if/how to do this" and "we know for a 
fact that this is impossible". :-P

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

Post a reply to this message

>> (Kinda amusing how not denying access to data is a "feature", eh?)
> 
> http://www.fsf.org/blogs/community/antifeatures

Yeah, that's where I got the idea from. ;-)

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

Post a reply to this message

And lo on Tue, 29 Jul 2008 15:42:40 +0100, Mike Raiford  
<mra### [at] hotmailcom> did spake, saying:

> Nicolas Alvarez wrote:
>
>> I definitely remember Windows 98 slowly redrawing the desktop as if it  
>> was
>> raytracing the damned wallpaper, while the hard disk made horrible
>> insane-seeking noises.
>
> I remember that, too. I attributed it to the Wallpaper being somewhat  
> dispensable, and being swapped to disk as soon as memory was being  
> needed by the application.

What do the pair of you mean remember? I've still got a 98 machine here  
that does just that if you dare to use more memory then is physically  
present.

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

And lo on Tue, 29 Jul 2008 21:45:13 +0100, Jim Henderson  
<nos### [at] nospamcom> did spake, saying:

> On Tue, 29 Jul 2008 09:10:38 +0100, Invisible wrote:
>
>>>> 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.
>>>
>>> That's kinda what I'm thinking.
>>
>> ...so in other words, hypothetically the information might not be
>> "gone". If that were indeed the case, it is at least plausible that
>> somebody could possibly get it back, yes.
>
> Oh, the information could well be gone, but it could be reconstructed
> from the available data.

In that case the information hasn't really gone merely converted into  
another pattern?

For an example of destroyed information tell me the equation I used to  
derive the answer of 9.

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