The English Wikipedia article about Turing machine opens with:

A Turing machine is a mathematical model of computation that defines an abstract machine,[1]

As a Hebrew speaker, I read a similar explanation in Hebrew Wikipedia:

מכונת טיורינג היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

My problem

I understand this term as reflecting a scientific theory in CS or Math, but interestingly, none of the two opening sentences presented this concept as a scientific theory in either CS or Math.

By scientific theory I meant:

An idea or set of ideas that can be falsified by principle (falsifiability as a condition for it to be real) and that one or more reinforcements can make it somewhat more plausible in reality.


If it's a theory in Math, maybe my approach is wrong, because, as far as I understand, in Math the paradigm is different so something is either true or false (i.e, not true).

My question

Is Turing machine a scientific theory in CS?


In comment section, Yuval Filmus said (minor paraphrase):

Turing machines are a mathematical abstraction.
They're neither a scientific theory nor a practical engineering idea;
Actual computers are much better modeled using a different abstraction → RAM machines;
The relevant scientific theory is the Church-Turing thesis.

This made me wonder "what is the difference between a mathematical model and a mathematical abstraction and does the former or the latter or both, can be based in a "scientific theory"?

This isn't the main question, but you are welcome to explain this in an answer as I think it's relevant.

  • 1
    $\begingroup$ Turing machines are a mathematical abstraction. They're neither a scientific theory nor a practical engineering idea (actual computers are much better modeled using a different abstraction, RAM machines). The relevant scientific theory is the Church-Turing thesis. $\endgroup$ Feb 7 '20 at 5:51
  • 4
    $\begingroup$ Perhaps you should migrate this question to Philosophy. $\endgroup$ Feb 7 '20 at 5:55
  • 3
    $\begingroup$ The idea of falsifiability is more related to empirical sciences like biology or physics. In formal sciences like math or theoretical CS, the word 'theory' is usually used for statements that have been proven true by an unbroken chain all the way back to the fundamental assumptions, i. e. axioms, and definitions. Turing machines are defined, purely artificial and don't make any statement about properties of the real-world objects. $\endgroup$
    – Albjenow
    Feb 7 '20 at 7:38
  • 1
    $\begingroup$ This is like asking “is light a scientific theory?”. No, it’s not a theory by itself, scientific or not. QED, though is a theory about light. $\endgroup$ Feb 7 '20 at 11:21

No, as Yuval Filmus explained, a Turing machine is not a scientific theory.

Furthermore, something can be both a mathematical model and a mathematical abstraction; for example, if the model is an abstraction.

Types of scientific theories

In the physical sciences, a scientific theory is a set of rules or models that makes testable predictions that could potentially be falsified. A Turing machine just isn't any of those.

In mathematics, the word "theory" may be used to describe a framework for reasoning where we have axioms, definitions, and inference rules for making deductions that follow from those axioms and definitions. A Turing machine isn't that, either.

Personal opinion

I don't think it's a good use of time to devote a lot of energy to these kinds of questions. Instead, I would suggest that you learn the basic material in textbooks on Turing machines and computability and decidability, and don't worry too much about how to categorize or classify it or what words can be applied to it. From a computer science perspective, it's more useful to focus on the mathematics without trying to put it into a philosophical framework or trying to come up with definitions of these broad, vague concepts (abstraction, theory, model).

  • $\begingroup$ We always study, until death; most often many things; you don't know what goes in my mind and hence what "my studies" are; I could have many motivations for asking the above question - expanding general knowledge is one of them; I come across a lot of the terms "turing completeness" and "turing machine" and I think I should have at least a little bit better understanding of what they really mean (yes, without being a CS B.A student); without being explained what a scientific theory in physical sciences or natural sciences is, because I already done that, quite good, I think, humbly. $\endgroup$
    – user109446
    Feb 7 '20 at 8:45
  • 1
    $\begingroup$ @JohnDoea, ok, good point, I agree with removing the phrase "At this point in your studies". My comment wasn't really about you. Thanks for suggesting several improvements to my answer! $\endgroup$
    – D.W.
    Feb 7 '20 at 8:54

More precisely, a "theory" in mathematics (and by extension in other deductive branches of science) is a collection of axioms, definitions and propositions proved from the above, typically acompanied by a set of tools and techniques. So, newtonian mechanics, general relativity, group theory, thermodynamics, number theory, and a host of others are "theories". In experimental sciences (like physics), a "theory" is an explanation for a collection of somehow related phenomena, typically in the form of a deductive theory as above. That can be falsified (shown wrong, or be just an approximation).

Turing machines are one specific model of the idea of what "computation" is all about. There are theories around that concept (computability and complexity theories, the last one a central area of active research in theoretical CS and pivotal in practical algorithm development).


Your Answer

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