In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this problem as undecidable.

I know computational models like Lambda Calculus are equivalent due to Turing-completeness, but why do we only consider the Turing machine as a model of general-purpose computation?

For example, in Physics, the Newtonian Framework has its own theory about light and about interaction time speed, but that framework fundamentally changed in 20th century which gave us new capabilities(or restrictions) theoretically. Is such a fundamental change viable in computer science, or we do consider Turing and early 20th century foundations similarly as quantum physics is to realm of physics.

Why do we work within the framework and don't try to change fundamentals such that things that may be undecidable become decidable within another framework?


1 Answer 1


Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are:

However, we can prove that all these models of computation are equivalent, i.e., the functions they can compute are exactly the same (they're called Turing-computable functions, or just computable functions).

(Side note: Pure λ-calculus is Turing-complete, i.e., equivalent to Turing machines and all the others, but many typed λ-calculi are not. Also note that I'm speaking about equivalence in expressive power here, not in complexity. Some of these models allow to naturally define a notion of the time and memory used by an algorithm, and some do not; and among those which do, there can be large differences.)

Consequently, it is not useful to change your model of computation if you just want to study computability, because computability is the same in all these models.

There are also various commonly studied models that are more restrictive (e.g., finite automata, pushdown automata, various subclasses of grammars, primitive recursive functions, ...).

We do also occasionally study models which allow computing functions that aren't Turing-computable. For example, oracle machines with uncomputable oracles, when studying Turing degrees (degrees of uncomputability). Another example from complexity theory is the study of the P/poly class.

However, there is a simple but deep reason that we reserve the word "computable" for Turing computability: it is that we do not know any physical device that could compute a function which is not Turing-computable. This is called the Church-Turing thesis. It states that Turing-computable functions are exactly the functions which can actually be computed in real life, by a human or computer or any physical system. Because we have so many models of computation, which match our intuition of how computation works, and nobody so far (in the 90 years since λ-calculus and Turing machines were invented) came up with evidence of being able to compute something not Turing-computable, it is widely believed that Turing computability is "the right notion" for the world we live in. This doesn't mean that other notions aren't interesting, but Turing computability is particularly interesting for this reason.

Also, we can't exclude finding, someday, some physical effect in quantum mechanics/black holes/whatever that would disprove the Church-Turing thesis. But this doesn't mean the Church-Turing thesis is not useful, if only because it's what we have to live with on today's computers. (By the way, there is consensus among those studying quantum computing that it would not change the notion of computability, in the current state of knowledge.)

  • $\begingroup$ wow, very detailed answer, thank you so much. yeah, after all Newtonian physics still co-exist with quantum physics, so after all, we've to appreciate what was so fundamental in the beginning. I currently can't upvote your answer, but definitely answered my question. $\endgroup$
    – math boy
    Commented Mar 10 at 17:58
  • $\begingroup$ What would have to be proved in order to show that hypercomputing (some computing model more powerful than a Turing-equivalent computer) is either physically realizable or not physically realizable in this universe? $\endgroup$ Commented Mar 17 at 22:04
  • $\begingroup$ @LukeHutchison You cannot prove it mathematically, as it is a matter of physics. To demonstrate the possibility of hypercomputation you would have to show a physical experiment where hypercomputation can be observed. And you simply cannot prove that hyper computation is impossible, since you cannot prove a physical theory is correct (only corroborate it by experience). $\endgroup$ Commented Mar 18 at 7:20
  • $\begingroup$ @JeanAbouSamra there are good reasons to believe that physics and mathematics are one and the same thing. en.m.wikipedia.org/wiki/… $\endgroup$ Commented Mar 19 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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