5
$\begingroup$

I know the term "Algorithm" is used in "Computer science" and "Computer programming" as any set of operations done in an ordered way to solve a problem. But this definition seems not a rigorous mathematical definition.

Is there any rigorous definition of the concept of "Algorithm" in the scope of "Pure mathematics"?

$\endgroup$
5
  • 1
    $\begingroup$ My first answer would be, the word "algorithm" is too vague of a concept to admit a formal definition without specifying a context. Does the notion of a transition scheme of a Turing machine satisfy your question? $\endgroup$ Nov 8 '16 at 15:54
  • 1
    $\begingroup$ See Computability theory : "The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation." $\endgroup$ Nov 8 '16 at 15:57
  • $\begingroup$ @MeesdeVries What bothers me is "Turing machine" is a computer theoretical concept rather than a purely mathematical concept(I know nowadays computer science is considered as a branch of mathematics but its mainly "Applied mathematics" rather than "Pure mathematics") $\endgroup$ Nov 8 '16 at 16:00
  • 4
    $\begingroup$ It seems to me that when concepts such as Church's Thesis and the Turing machine were being developed, they were pure mathematics. The branching-off of computer science as a separate discipline came later. $\endgroup$
    – David K
    Nov 8 '16 at 16:04
  • 1
    $\begingroup$ See here. $\endgroup$ Nov 8 '16 at 17:07
6
$\begingroup$

Speaking as a computer scientist here, I think the important thing to understand is that in practice the word "algorithm" is generally not used to denote any rigorous technical concept.

When people speak about "an algorithm" what they're referring to in 95% of cases is a fuzzy concept of the idea behind how a computer program does what it does. (In this context a "program" is generally imagined to be an mainframe-era batch-mode thing that takes some input and produces some output, not one of those newfangled 'applications' that you interact with). In this context the program itself is a precise formal object, but when we speak about "which algorithm does this program use for such-and-such" or "this program and that one use the same algorithm", what we're speaking about is ideas in the programmer's head, not a formal thing that can be written down and compared for equality.

At least in computer science (and practical software engineering) this usage is ubiquitous and non-controversial. And it looks very much to me like it is also this way in mathematics.

In mathematics and theoretical computer science we do make claims such as "there is an algorithm for such-and-such" (or "there is no algorithm ...") as if they are precise technical statements that are subject to proof or disproof. And they are, by a kind of terminological sleight of hand, namely that such claims are supposed to be interpreted as "there is a program that behaves like such-and-such". Or "there is a Turing machine", or "there is a set of mutually recursive definitions", or whichever formalism for computations we prefer to work in.

The underappreciated reason why this sleight-of-hand works in practice is that it doesn't really matter what you take a "program" to mean in this case, as long as it's a halfway reasonable one. The tasks that there are Turing machines that solve are exactly the same tasks that there are Haskell programs or rewrite systems or lambda terms to solve -- this is Church's thesis and is why we can get away with just saying "there is an algorithm" without bothering to explain up front what the exact kind of thing we assert exists is.

Saying "there is an algorithm ..." is useful in practice because it allows us to communicate the interesting content of the claim without being sidetracked by which precise formalism the speaker prefers working with. At least if both the speaker and listener both know that all of the formalisms are equivalent anyway.

There the many concrete formalisations of what it means for an algorithm to exist, each of which can be defined mathematically with all the rigor you want. Turing machines is one of them, and there's a wide selection of other similar "machine" concepts that make different trade-offs between definitional simplicity, ease of programming, and "realism": counter machines, random access machines, and so forth. Then there are various rigorously defined programming languages, including the lambda calculus which also counts as an example of general rewrite systems that can express computation. Finally there are more purely number theoretic formalizations, such as Gödel's concept of primitive recursive functions (appropriately extended to give all the computable functions), and so forth.

Again, each of these particular formalism can be rigorously defined. If I say "I'm thinking of an algorithm for such-and-such", what I have in mind is a mental concept that can be realized (with greater or less ease) in each of all of these formalisms, but I usually haven't committed to use any particular one among them.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. That was really insightful. But since the other one was in a more formal manner, I accepted that. I voted your answer up but sorry for not accepting it. $\endgroup$ Nov 8 '16 at 19:01
5
$\begingroup$

If you don't like turing machines because they seem to be insufficiently mathematical, you may prefer the theory of $\mu$-recursive functions. These were formalized around the same time as turing machines, for the same reason: to try to formalize the intuitive notion of a computable algorithm. But the definition has more of the flavor of pure mathematics:

  1. The constant function $Z() = 0$ is primitive recursive
  2. The successor function $S(n)= n+1$ is primitive recursive
  3. The projection functions $P_i^n(x_1, x_2, \ldots, x_n)= x_i$ are primitive recursive
  4. Compositions of primitive recursive functions are primitive recursive
  5. If $f$ and $g$ are primitive recursive then so is $h$, where $h$ defined recursively with $f$ as its base case and $g$ as its recursive case:

$$\begin{align} h(0, x_1, \ldots, x_k) & = f(x_1, \ldots, x_k) \\ h(y, x_1, \ldots, x_k) & = g(y-1, h(y-1, x_1, \ldots, x_k), x_1, \ldots, x_k)\qquad\text{if $y>0$} \end{align} $$

So far this defines the primitive recursive functions, which do not include all the intuitively computable functions; the usual counterexample is Ackermann's function, which is computable but which is not primitive recursive. One way to extend the primitive recursive functions to better match the intuitive notion of computability is to add the so-called $\mu$ operator, which finds the minimum number at which a function's value is zero. That is, suppose we have some function $f(n, x_1, \ldots, x_k)$. Then we define $\mu f( x_1, \ldots, x_k)$ to be the smallest number $m$ such that

$$\begin{align} f(m, x_1, \ldots, x_n) & = 0\\ f(n, x_1, \ldots, x_n) & > 0\qquad\text{for all $n < m$}\\ \end{align} $$

if that $m$ exists. If not, $\mu f( x_1, \ldots, x_k)$ is undefined. (For example, $\mu S()$ would be the smallest argument for which the $S(n)$ function is zero, but there is no such argument.)

Extended in this way, the class of primitive recursive functions is expanded to become the $\mu$-recursive functions. Just as there is no general method for deciding if a particular turing machine halts on a particular input, there is no general method for deciding if a given $\mu f( x_1, \ldots, x_k)$ exists,

The $\mu$-recursive functions turn out to be exactly the same as the functions that can be computed by turing machines, and the turing machine halts on all inputs if and only if the function is defined for all arguments.


If you also don't like this, you may prefer the $\lambda$-calculus, also invented around the same time for the same reasons.

The equivalence of these three different models of computation, each very plausible, is probably the strongest evidence we have that they are all reasonable.

$\endgroup$
1
  • $\begingroup$ Thank you. Your formal answer was so helpful too and I voted it up. Now I think I'm finally able to formulate what I consider to be a mathematical definition of algorithm with aggregating all the answers. $\endgroup$ Nov 9 '16 at 19:58
3
$\begingroup$

As pointed in the comments, the best formalization of what is an algorithm uses the theory of Turing machines.

This definition is surprisingly robust, in the sense that for all other sensible attempts at formalizing the notion of an algorithm (perhaps the other famous one is the model of lambda calculus) we have found the resulting model to be equivalent to Turing's, in the sense that every function from the natural numbers to the natural numbers computed in the model can be computed by a properly designed Turing machine.

In fact, the evidence is so strong that computer scientists conjecture that every possible sensible model of computation will be reducible to Turing's model. This is known as the Church-Turing thesis.


As requested per the OP, here is a possible formalization of Turing machines in a set theory friendly presentation.

A Turing machine is a function from the set $Q\times \Sigma$ to the set $Q \times \Omega$, where $Q$ is a finite set of states with two special states $START$ and $HALT$ that designate initialization and ending of the computation, $\Sigma$ is a finite set of symbols (typically $1$ and $0$) and $\Omega$ is a set of possible actions that the TM may take (typically writing a $1$, writing a $0$, moving left and moving right).

Thus in each step the machine reads the contents of the cell it is in, and according to its internal state and the reading changes its state and does an action.

Now, the Turing machine starts over a tape with an input of finitely many ones and infinitely many 0's (or other symbols depending on your choice of formalism). If we specify a codification for inputs and outputs, then we can define "running" the algorithm as starting the TM over a valid input in the $START$ state, and applying repeatedly the transition table we have defined and performing the indicated actions over the tape until we reach the $HALT$ state. Then we can decodify the contents of the tape in that moment as the output of the algorithm.

Of course, this formalism is quite useful to reason about TMs, but if we want to embed them in Set Theory we will have to step up our game.

We can construct the TMs as functions which transform an set representing the state of the machine, its position and the infinite tape into new states, positions and tapes, subject to a series of conditions.

Under this interpretation, the TM is a function $Q\times\mathbb{Z}\times T \to Q\times\mathbb{Z}\times T$, where $Q$ are the states, the second member of the tuple is the position and $T$ is the infinite tape, itself a function from $\mathbb{Z}$ to $\Sigma$.

To be a proper TM, some restrictions have to be imposed, such that you can only modify the cell you are in, there must be special start and end states, etc. $Q$ and $\Sigma$ can be seen as finite sets of numbers.

This is a powerful enough formalization to talk about TMs in the language of set theory.

If you are interested in a beautiful and thorough treatment of computability theory and its embedding in FOL, I suggest reading Computability and logic, by Boolos et al.

$\endgroup$
11
  • $\begingroup$ Yes but it does not satisfy me. See my comment under my question. That's the reason. $\endgroup$ Nov 8 '16 at 16:03
  • $\begingroup$ How about we come up with a rigorous definition of "pure mathematics" before rejecting answers as not "pure" enough? $\endgroup$
    – David K
    Nov 8 '16 at 16:10
  • $\begingroup$ That's not really a good reason. Church and Turing were around before computer science was a discipline. $\endgroup$
    – Nitin
    Nov 8 '16 at 16:10
  • 1
    $\begingroup$ @HamedBegloo done ^^ $\endgroup$ Nov 8 '16 at 18:50
  • 1
    $\begingroup$ OP - if you want to read more consider looking at Sipser's Theory of Computation. $\endgroup$
    – Nitin
    Nov 8 '16 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.