<p>I haven't seen this written down, but I'd define an algorithm as "a series of well-defined steps for solving a problem". By well-defined, I mean that each step is either an algorithm itself (like a subroutine), or else a simple and completely mathematically unambiguous operation.</p>

<p>A more precise mathematical definition can follow by defining your model of computation, which mathematically specifies exactly which steps are allowed and in what sequence. For example, a Turing Machine formally specifies what steps it may take and the order it takes them in. Similarly for, say, a pushdown automata, and close to similarly for many programming languages.</p>

<p>One cannot have a universal definition that encompasses all possible models of computation, unless one somehow could formalize the notion of "all possible models of computation", which seems impossible. For example, tomorrow I may invent a model of computation involving dropping beads into buckets, and as long as I formally specify the model of what steps can be taken and in what order, one could write algorithms for my new type of computer.</p>

<p>The Church-Turing thesis is related: It is a proposed natural law stating that any such model of computation could be "simulated" by a Turing Machine. So in that sense, my algorithm for my new type of computer would be no more "powerful" than algorithms for Turing Machines. Because of this, if one accepts the Church-Turing thesis, then it is without loss of generality to define an algorithm as a type of Turing Machine. (But on the other hand, in theoretical CS we often think of models beyond Turing Machines, such as TMs with access to randomness, access to oracles for the halting problem, etc.)</p>

CC BY-SA 3.0
2015-05-30T12:43:24.840Z
2015-05-30T12:43:24.840Z
usul
<p>A friend of mine usually talks to me about Church's thesis. Some days ago I found a <a href="http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf" rel="nofollow noreferrer">proof</a> and talked about it to him. He said that <em>"it's possible to prove the thesis using an arbitrary definition of algorithm, the problem is that it is a consensus that algorithm is something without mathematical definition and this is why it's a thesis, not a theorem or lemma"</em>. But sometimes in my readings, it seems that there is one and other times, it seems that there isn't one. </p>

<p>I've also seen <a href="https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis">this</a>, but it didn't had anything about mathematical definition of algorithms (or at least, not something I could understand).</p>

<p>So, my questions are: </p>

<ul>
<li><p>Is there a mathematical definition for algorithms?</p>

<ul>
<li>If not, what would be a mathematical definition for it? What would it need to be in order to be a definition?</li>
</ul></li>
</ul>

CC BY-SA 3.0
2015-05-30T14:48:43.077Z
Your first link leads to a paper containing a formal mathematical definition of "algorithm". So, yes, there is one.
Jeffε
CC BY-SA 3.0
2015-05-30T14:50:33.563Z
@JɛﬀE Yes. I also assumed that it could have in here: *(or at least, not something I could understand).* - I'm not a specialist in the field, but wanted to know a little about it.
Red Banana
CC BY-SA 3.0
2015-06-02T16:59:17.117Z
Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope.
chazisop
CC BY-SA 3.0
2015-06-03T13:34:35.767Z
@chazisop Yes. Sorry, I forgot about it. Can someone transfer my question to there?
Red Banana
CC BY-SA 3.0
2015-06-04T07:35:45.763Z
@JesusChrist I guess a moderator can do it. You can also copy the question yourself, but don't forget to mention it is a cross-post, as this is common policy.
chazisop
<ds.algorithms>
Is there a mathematical definition of algorithm?
Red Banana
# Is there a mathematical definition of algorithm?

(Asked by: username_0 on 2015-05-30)

A friend of mine usually talks to me about Church's thesis. Some days ago I found a [proof](http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf) and talked about it to him. He said that *"it's possible to prove the thesis using an arbitrary definition of algorithm, the problem is that it is a consensus that algorithm is something without mathematical definition and this is why it's a thesis, not a theorem or lemma"*. But sometimes in my readings, it seems that there is one and other times, it seems that there isn't one.

I've also seen [this](https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis), but it didn't had anything about mathematical definition of algorithms (or at least, not something I could understand).

So, my questions are:

* Is there a mathematical definition for algorithms?

  + If not, what would be a mathematical definition for it? What would it need to be in order to be a definition?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Your first link leads to a paper containing a formal mathematical definition of "algorithm". So, yes, there is one.  
> **username_0**: @JɛﬀE Yes. I also assumed that it could have in here: *(or at least, not something I could understand).* - I'm not a specialist in the field, but wanted to know a little about it.  
> **username_2**: Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope.  
> **username_0**: @username_2 Yes. Sorry, I forgot about it. Can someone transfer my question to there?  
> **username_2**: @JesusChrist I guess a moderator can do it. You can also copy the question yourself, but don't forget to mention it is a cross-post, as this is common policy.  

---

## 1 answers

### Answer by username_3 on 2015-05-30. Score: 3

I haven't seen this written down, but I'd define an algorithm as "a series of well-defined steps for solving a problem". By well-defined, I mean that each step is either an algorithm itself (like a subroutine), or else a simple and completely mathematically unambiguous operation.

A more precise mathematical definition can follow by defining your model of computation, which mathematically specifies exactly which steps are allowed and in what sequence. For example, a Turing Machine formally specifies what steps it may take and the order it takes them in. Similarly for, say, a pushdown automata, and close to similarly for many programming languages.

One cannot have a universal definition that encompasses all possible models of computation, unless one somehow could formalize the notion of "all possible models of computation", which seems impossible. For example, tomorrow I may invent a model of computation involving dropping beads into buckets, and as long as I formally specify the model of what steps can be taken and in what order, one could write algorithms for my new type of computer.

The Church-Turing thesis is related: It is a proposed natural law stating that any such model of computation could be "simulated" by a Turing Machine. So in that sense, my algorithm for my new type of computer would be no more "powerful" than algorithms for Turing Machines. Because of this, if one accepts the Church-Turing thesis, then it is without loss of generality to define an algorithm as a type of Turing Machine. (But on the other hand, in theoretical CS we often think of models beyond Turing Machines, such as TMs with access to randomness, access to oracles for the halting problem, etc.)


---

