Re: Category Theory of Algorithms
- From: me@xxxxxxxxxxx (Jamie Andrews; real address @ bottom of message)
- Date: 10 Apr 2007 20:01:43 GMT
the.theorist <the.theorist@xxxxxxxxx> wrote:
See what I'm after is an algebra of algorithms. I'd like to know if
it's possible to take some small set of simple algorithms, and by
repeated application of some operators build up to more complex
algorithms. An, Algebra or Calculus of Algorithms, if you will.
Others have answered this in ways that I agree with.
Here's another view on the same opinions.
In order to create a calculus of algorithms, you need to
have mathematical objects standing for algorithms. In order to
do this, you have to formalize algorithms in some way. I can't
see any way of formalizing them that would not end up as some
kind of simple programming language. You would therefore end up
in the well-studied area of category-theoretic foundations of
programming languages.
Put another way, the thing that distinguishes an algorithm
from a program in a programming language is that there are some
more or less vague, unformalized aspects to it, such as English
sentence fragments that we assume the reader can convert to the
more formal text required by a programming langauge. So, the
nature of an algorithm (as opposed to a program) is antithetical
to formalism.
As far as developing a system that will give you
information about how fast a particular program will run, Martin
Hofmann (Univ. of Munich) and others have worked on type systems
that do this. See
Programming languages capturing complexity classes
ACM SIGACT News 31(1), 31-42, March 2000
for a survey.
--Jamie. (efil4dreN)
andrews .uwo } Merge these two lines to obtain my e-mail address.
@csd .ca } (Unsolicited "bulk" e-mail costs everyone.)
.
- References:
- Category Theory of Algorithms
- From: the.theorist
- Re: Category Theory of Algorithms
- From: Jym
- Re: Category Theory of Algorithms
- From: Pummelo
- Re: Category Theory of Algorithms
- From: the.theorist
- Category Theory of Algorithms
- Prev by Date: Re: Category Theory of Algorithms
- Next by Date: Linear programming?
- Previous by thread: Re: Category Theory of Algorithms
- Next by thread: Re: Category Theory of Algorithms
- Index(es):
Relevant Pages
|
