Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Concrete and Abstract in Mathematics, was "What's wrong with education..."
Posted:
Jun 13, 1996 9:10 PM


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.



