Galois Theory of Algorithms

Galois Theory of Algorithms

[Noson S. Yanofsky]

Hi,

I posted a new paper on the arxiv:

Title: Galois Theory of Algorithms

http://arxiv.org/abs/1011.0014

Abstract: Many different programs are the implementation of the same
algorithm. This
makes the collection of algorithms a quotient of the collection of programs.
Similarly, there are many different algorithms that implement the same
computable function. This makes the collection of computable functions into
a
quotient of the collection of algorithms. Algorithms are intermediate
between
programs and functions: Programs -> Algorithms -> Functions. Galois theory
investigates the way that a subobject sits inside an object. We investigate
how
a quotient object sits inside an object. By looking at the Galois group of
programs, we study the intermediate types of algorithms possible. Along the
way, we formalize the intuition that one program can be substituted for
another
if they are the same algorithm.

I would be most interested in any comments or criticisms.

All the best,
Noson



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]