1
$\begingroup$

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.

But;

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?

Update

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.

Improve this question
$\endgroup$
4
  • 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$
    – Yuval Filmus
    Feb 7, 2020 at 5:51
  • 4
    $\begingroup$ Perhaps you should migrate this question to Philosophy. $\endgroup$
    – Yuval Filmus
    Feb 7, 2020 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, 2020 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$
    – Dmitri Urbanowicz
    Feb 7, 2020 at 11:21

4 Answers 4

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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, 2020 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, 2020 at 8:54
  • $\begingroup$ So what about Euclidean geometry? It can definitely be tested in practice. In the same sense, Turing machines and their theory can be tested. $\endgroup$
    – reinierpost
    Jun 24, 2022 at 19:20
  • $\begingroup$ @reinierpost, Euclidean geometry itself (the axioms and theorems that follow from them) makes no testable predictions. It is a mathematical model. In contrast, the claim that "the universe follows the axioms of Euclidean geometry" is a plausibly-testable theory of physics. But that's more than just "Euclidean geometry" (a mathematical model); it is a claim about the real world. In any case, we're getting a bit far afield from Turing machines. $\endgroup$
    – D.W. ♦
    Jun 24, 2022 at 19:27
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

Firstly, I recommend you, not to visualize science and math as separate theories. Basically, to induce any kind of new scientific approach, there must be some mathematical model working underneath it.. as to mention math would be providing a background framework

Similarly, in the case of Turing machine or the concept of Automata theory they will be providing a background framework to visualize a computer's regular scenarios i.e., Turing machine is a mathematical model to describe a computer in theoretical sense or on paper scenarios. also Automata theory provides many kinds of mathematical models to assure on paper formations of all computational routines. as it just like we will be using the concept of integral calculus to analyze the irregular or non-newtonian objects or surfaces in physics.

Finally, yes, Turing machine is a kind'a mathematical model but being used as a part of computer science.Over the paradigms if you integrate the math with physical phenomena and logic it will become the physics.

Improve this answer
$\endgroup$
0
$\begingroup$

Short answer: the Turing Machine is a fundamental concept in the Theory of Computability. Like the prime decomposition is a fundamental concept in the Theory of Numbers.

Improve this answer
$\endgroup$

Your Answer

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