-2

A friend of mine usually talks to me about Church's thesis. Some days ago I found a proof 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, 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?
Community
  • 1
Red Banana
  • 105
  • 2
  • 2
    Your first link leads to a paper containing a formal mathematical definition of "algorithm". So, yes, there is one. – Jeffε May 30 '15 at 14:48
  • @JɛffE 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 May 30 '15 at 14:50
  • 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. Your question might be suitable for Computer Science which has a broader scope. – chazisop Jun 02 '15 at 16:59
  • @chazisop Yes. Sorry, I forgot about it. Can someone transfer my question to there? – Red Banana Jun 03 '15 at 13:34
  • @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 Jun 04 '15 at 07:35

1 Answers1

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.)

usul
  • 7,615
  • 1
  • 26
  • 45