Re: Category Theory of Algorithms

On Apr 9, 12:20 am, "the.theorist" <the.theor...@xxxxxxxxx> wrote:
I'm not myself very well versed in the study of algorithms (my
training is bachelor-level physics and applied math), but I found
myself pondering the computational road ahead. Especially the
transition into parallel computing.

It seems to me that most of the literature about the study of
algorithms details aspects such as bounds on time, number of
operations, amount of memory required, etc... All focus has been
primarily on efficiency. As we transition to a parallel architecture I
foresee a need for a different sort of algorithmic study, one that
focuses more on the mathematical properties of algorithms. Properties
such as closure, contanenation, OR-ing, AND-ing, etc.. (I don't fully
know what those terms might mean when applied to algorithms, which is
why I think there's research to be done here.) What are the natural
operations that can be performed on algorithms?

Category Theory has been really nice for the study of type systems,
and for providing a lens with which to view mathematics, and the
relationship between mathematical objects. Has it been applied to the
study of the mathematical properties of algorithms (as a mathematical
object)? I wasn't able to find a strong link between the two
disciplines using google, (maybe I'm barking up the wrong tree?)

Can anyone recommend some textbooks in this area? And what are the
current thoughts on what is needed for the transition to the parallel
paradigm?

For category theory applied to algorithmics, look at the very nice
book "Algebra of Programming" by Richard Bird and Oege de Moor.

sjr

.

Relevant Pages

  • Category Theory of Algorithms
    ... I'm not myself very well versed in the study of algorithms (my ... myself pondering the computational road ahead. ... focuses more on the mathematical properties of algorithms. ... and for providing a lens with which to view mathematics, ...
    (comp.theory)
  • 6P=NP: Proof: Harvey Friedman Revised
    ... The equation P = NP concerns algorithms for deciding ... Discrete complexity theory is dependent on a formal ... that discusses Turing machines without resource bounds ... comparable to some of the great problems of mathematics ...
    (sci.math)
  • ebooks forum..
    ... Lie-Backlund Transformations in Applications Robert L. Anderson and 1 ... Interior Point Polynomial Algorithms in Convex Programming Yurii ... Linear Matrix Inequalities in System and Control Theory Stephen Boyd, ... Mathematics Applied to Deterministic Problems in the Natural ...
    (sci.med.nutrition)
  • Re: Formal Semantics of the Java "new" Operator
    ... of mathematics by and large does not try to describe computations. ... Algorithms belong to computer science --- if pressed, ... "random access memory," which is essentially a big pool of "storage," ... which are typically some sort of integers. ...
    (comp.theory)
  • Re: Epistemology 201: The Science of Science
    ... > Lots of mathematics is verified with pencil and paper. ... is the lack of correctness proof in algorithms, trust in their implementation, ... > Although there was some initial controversy over the idea of using a ...
    (sci.cognitive)