Date: Jun 13, 1996 9:10 PM
Author: Alberto C Moreira
Subject: Re: Concrete and Abstract in Mathematics, was "What's wrong with education..."
email@example.com (David K. Davis) wrote:
>I said I'd shut up for while, but I'm having trouble. I believe that there
>is knowledge that is not essentially reducible to algorithm and I believe
>that there is a mathematical argument that shows why.
I don't think anybody can prove that today. Proving it would topple
Church's thesis, at least to the extent that "knowledge" is algorithmic.
But which knowledge isn't ? Anything that depends on logic is based
on an algorithm. A lot of things that seemingly aren't can be
simulated by algorithmic methods. We learn new such algorithms
There's a difference between saying "we can't do it today" and
"it cannot ever be done". The first can be applied freely to
lots of things; the latter cannot, by and large.
>Some (most) (almost
>all actually) data is algorithmically incompressible. That is, the
>algorithm used to encode is almost as long as the data itself. Can it
>be that physical systems implement processes that while perhaps in theory
>are reducible to algorithm, in practice the algorithm would have to be of
>such immense complexity as to not count as an algorithm by ordinary standards,
>that is, be unusable by a computer?
That's not a question of computability itself, but a question of whether
the algorithms we know are efficient. For example, we know how to break
an RSA cypher, but it would take more computer time than one's life.
But the day quantum computers are realized, that limit will have been
blown to pieces, and a new sort of cryptography will be needed. What's
very hard to do today may not be hard at all to do tomorrow; an
algorithm doesn't cease to be classified as such just because it's
>Can a physical (biological) process
>be such that any algorithmic emulation would be impractical? I think
>it's possible, and I think it's likely in the case of the mind. (G. Chaitin
>is the one responsible for the algorithmic complexity ideas, but not
>for my use or abuse of them here.)
Again, we're in the realm of speculation. We can't prove it cannot be
done, and as far as our technology has progressed there's no limit
except those generated by the technology itself. We're very far from
hitting computability limits; our computers are very limited to be
able to reach that far.