Date: Jun 13, 1996 9:10 PM
Author: Alberto C Moreira
Subject: Re: Concrete and Abstract in Mathematics, was "What's wrong with education..."

davis_d@spcunb.spc.edu (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

every day.

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

not efficient.

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

Alberto.