1
$\begingroup$

Why is there no algebraic definition of algorithm besides recursive functions?

If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?

For example, modern machines do overflowed arithmetic by the rules of modulo $2^{32}, 2^{64}$, etc arithmetic.

So why is there rarely a discussion of a theoretical machine that works on finite groups or just integer quotient groups brought to some power which is the memory length (number of "words").

I think a lot can be done with math to solve algorithmic questions, but when one first approaches the subject, there is very little workable mathematics.

Recursive functions are nice, but mathematically they can be very hard to deal with. Since every recursive algorithm has an iterative counter-part, I wish there were a paper that had operators like $\sum_{i=1}^{g(n)} f(i)$ which mimic a for-loop with bound dependent upon $n$ and that essentially evaluates $f(n)$ every loop.

Why can't we have this type of more traditional mathematics describe algorithms, or can we? Do you have a definition you're working on?

If so, please share it in an answer to this question.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically.

Some examples:

  • Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable functions. The trick is that, to model computation, we need to represent functions, but for any set $S$, the function space $S \to S$ is always larger than $S$. So there's no simple set that captures all computations involving computations. Instead, Dana Scott introduced domains, which impose additional structure on sets to avoid countability problems.

  • SKI Combinators provide a "point-free" description of computation. Every computation can be expressed by composing and applying three base combinators $S$, $K$, and $I$. The equations for the combinators are:

    • $ S\ x\ y\ z = (x\ z)(y\ z)$
    • $ (K\ x) y = x$
    • $ I x = x$

    So these equations, in some sense, give an algebraic account of all of computation.

  • Cartesian closed categories provide models for typed programming languages. They don't capture all of computation, but they do provide an abstract model of it.

  • Topos theory provides a generalization of logic using category theory. And logic corresponds to computation via the Curry-Howard correspondence

As for recursion, it turns out that you can eliminate it by instead using fixed-point combinators like the Y combinator. So recursion can always be eliminated from (untyped) languages, even without using iteration.

Improve this answer
$\endgroup$
0
2
$\begingroup$

There is a definition, take a look at turing machines.

It still is extremely complicated to work with, so it won't be perfect. But it sill does give a different definition of computation, that can be useful in constructing theorems, such as the time hierarchy theorem.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What is the most algebraic version of Turing machine that you know of? $\endgroup$ Commented May 12, 2021 at 16:47
  • 1
    $\begingroup$ It can be defined formally: en.wikipedia.org/wiki/Turing_machine#Formal_definition $\endgroup$ Commented May 12, 2021 at 16:51
  • 1
    $\begingroup$ A TM is more of a graph-like structure than algebraic structure $\endgroup$ Commented May 12, 2021 at 16:51
  • $\begingroup$ Yes, but state machines are known to be described well using the language of monoids. $\endgroup$ Commented May 12, 2021 at 16:52
  • $\begingroup$ Found this: arxiv.org/pdf/1208.5205.pdf $\endgroup$ Commented May 12, 2021 at 16:58

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.