62
$\begingroup$

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.

I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.

And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!

Definition of "most powerful": That which can accept any language.
Definition of "Algorithm": Process for doing anything. Machine representation of "Algorithm": A machine that can do anything.

Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?

Improve this question
$\endgroup$
9
  • 10
    $\begingroup$ Turning machine can't solve the halting problem. However, there is no proof there is no machine to solve it. The model is kind of TM with oracle, or completely dofferent approach. If you follow the Church thesis, TM just represents machines we are using nowadays. $\endgroup$
    – Eugene
    Commented Dec 1, 2016 at 4:22
  • 17
    $\begingroup$ It's the most powerful machine we know how to build. Well, actually no, we can only build finite automata. $\endgroup$
    – Raphael
    Commented Dec 1, 2016 at 5:58
  • 13
    $\begingroup$ Your problem is that you think of TMs as something that came after. It was not. It was (and is) used to define the class of Turing-computable problems. Many equivalent models have been found, but that does not change the definition. $\endgroup$
    – Raphael
    Commented Dec 1, 2016 at 5:59
  • 4
    $\begingroup$ There are hundreds of different (Turing-complete) computer architectures out there, all with very different instruction sets. I don't think it's obvious at all that there is no problem that one can solve but another can't. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Dec 1, 2016 at 17:13
  • 5
    $\begingroup$ ... isn't what you are saying simply the Church-Turing thesis? As far as we know nobody disproved the thesis, but we cannot exclude the existence of a different model of computation that is "reasonable" (i.e. in some way implementable) and stronger than TMs. $\endgroup$
    – Bakuriu
    Commented Dec 2, 2016 at 9:10

7 Answers 7

Reset to default
144
$\begingroup$

I agree that a Turing Machine can do "all the possible mathematical problems".

Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).

Is Turing Machine “by definition” the most powerful machine?

No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build. That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.

What's the new thing Alan Turing gave us?

A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?

Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.

If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W. ♦
    Commented Dec 2, 2016 at 1:11
  • $\begingroup$ Don't you mean rational solutions? I think integer solutions is possible to do in a finite number of steps. $\endgroup$
    – Trenin
    Commented Dec 5, 2016 at 16:37
  • 2
    $\begingroup$ @Trenin The Wikipedia page I link says "rational integer", which it explains to be a phrase sometimes used to distinguish the ordinary integers from objects such as Gaussian integers (complex numbers $a+\mathrm{i}b$ where $a,b\in\mathbb{Z}$). $\endgroup$
    – David Richerby
    Commented Dec 5, 2016 at 16:47
  • 1
    $\begingroup$ Got it. Also, what I though was possible turns out to be much more difficult than I thought. $\endgroup$
    – Trenin
    Commented Dec 5, 2016 at 16:50
71
$\begingroup$

You are not correct when you repeatedly make the statements about this or that being "just a tautology". So allow me to put your claims into a bit of historical context.

First of all, you need to make the concepts you use precise. What is a problem? What is an algorithm? What is a machine? You may think these are obvious, but a good part of the 1920's and 1930's was spent by logicians trying to figure these things out. There were several proposals, one of which were Turing machines, which was the most successful. It later turned out that the other proposals were equivalent to Turing machines. You have to imagine an era when the word "computer" signified a person, not a machine. You are just riding the wave and the consequences of the brilliant inventions by brilliant minds from a hundred years ago, without being aware of it.

Turing machines are described concretely in terms of states, a head, and a working tape. It is far from obvious that this exhausts the computing possibilities of the universe we live in. Could we not make a more powerful machine using electricity, or water, or quantum phenomena? What if we fly a Turing machine into a black hole at just the right speed and direction, so that it can perform infinitely many steps in what appears finite time to us? You cannot just say "obviously not" – you need to do some calculations in general relativity first. And what if physicsts find out a way to communicate and control parallel universes, so that we can run infinitely many Turing machines in parallel time?

It does not matter that at present we cannot do these things. What is important, however, is that you understand that Turing had to think about what was physically possible (based on the knowledge of physics at the time). He did not just write down "a mere tautology". Far from it, he carefully analyzed what computation means in an informal sense, then he proposed a formal model, argued very carefully that this model captures what people understood by "computation", and he derived some important theorems about it. One of these theorems says that Turing machines cannot solve all mathematical problems (contrary to one of your false statements). All of this, in a single paper, written during summer vaccation, while he was a student. His theorem about the existence of universal machines was the invention of the idea of the modern general purpose computer. After that it was only a simple matter of engineering.

Does that answer what Turing contributed to humanity beyond a mere tautology? And did you actually read his paper?

Improve this answer
$\endgroup$
6
  • 23
    $\begingroup$ "You have to imagine an era when the word "computer" signified a person, not a machine." This is a really helpful reminder. In essence, Turing tried to effectively simulate, with his "machine", the operations a person could do with pen and paper at that time in order to calculate something. $\endgroup$
    – Sorrop
    Commented Dec 1, 2016 at 9:53
  • 2
    $\begingroup$ "His theorem about the existence of universal machines was the invention of the modern general purpose computer." -- Well.... in the mathematical world, maybe. People like Konrad Zuse developed general purpose computers independently. $\endgroup$
    – Raphael
    Commented Dec 1, 2016 at 18:16
  • 6
    $\begingroup$ @AndrejBauer That still suggests a timeline and dependency that wasn't there, not in all cases. I don't blame you -- few people know of what Zuse did when. Fact is, he built computers from 1935 all through WW2 without much if any input from outside Germany. He also developed his Plankalkül during that time. I guess it was with computers as with many other things: the time was ripe, so many minds thought along similar lines. Point being, for all his contributions, Turing did not invent computing. $\endgroup$
    – Raphael
    Commented Dec 1, 2016 at 21:10
  • 16
    $\begingroup$ @Raphael: Konrad Zuse did not know that his machine can process all computable problems (we now know that his machines ARE Turing complete - modulo memory). What Turing contributed was NOT the idea that machines can do computation - Babbage did that before either Zuse or Turing. What Turing contributed was the idea that instruction sets and programming languages don't really matter in theory. This is not an obvious idea. Ironically it is this idea that drives the development of CPUs and programming languages $\endgroup$
    – slebetman
    Commented Dec 2, 2016 at 7:51
  • 1
    $\begingroup$ "instruction sets and programming languages don't really matter in theory" -- that's clearly false. Differences can matter, but they don't always. Turing defined a certain model of computation and claimed it was as powerful as it would get. Caught between the caveat of infinite memory and more powerful models, I'm not too sure that claim holds any water. So, in a way, he did nothing else than Zuse, if with mathematics instead of metal. $\endgroup$
    – Raphael
    Commented Dec 5, 2016 at 21:45
23
$\begingroup$

That "anything that is solvable can be represented by an algorithm" is not obvious, at all.

This has been the object of intense debate, since Alan Turing, reworking ideas of Alonzo Church, proposed a definition of computable numbers that took the form of the machine you are referring to. Importantly, those were not the only people working on this kind of thing, at that time.

We still call it a thesis - or a conjecture - since "anything that can be calculated" is clearly not a precise mathematical object, whose structure and range could be studied in a non-speculative way.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ But anything that is solvable has to be solved by a "process" (by definition). We may not know the process to solve a particular "solvable" problem at the current time. In which case it means that the problem is solvable but cannot be solved now. Does it not effectively mean that "anything that is solvable can be represented by an algorithm" because "process"="algorithm". Why do you say it is not obvious? $\endgroup$
    – Sounak Bhattacharya
    Commented Dec 1, 2016 at 4:27
  • 15
    $\begingroup$ What is a "process"? See, it is easy to run in circles, substituting one unclear concept for another. Turing attempt was actually a thought experiment incarnated, that is still feeding our imagination, even today. That's not a small thing. $\endgroup$
    – André Souza Lemos
    Commented Dec 1, 2016 at 4:31
  • $\begingroup$ @SounakBhattacharya By some process (of years and genius) Sir Andrew Wiles proved Fermat's Last Theorem to be true. Do you imagine there's a TM that could have made that determination? $\endgroup$
    – OJFord
    Commented Dec 1, 2016 at 23:06
  • 2
    $\begingroup$ @OllieFord Well, if the proof is sufficiently rigorous that each step can be expressed in terms of existing well specified axioms, then the proof can be verified by a Turing machine. We could then specify a Turing machine that enumerates all possible proofs and surely (but very very slowly) the machine would find such a proof. A simple physical implementation of that Turing machine would take more than 400 years though, and much longer than the expected lifetime of the universe. $\endgroup$
    – gmatht
    Commented Dec 2, 2016 at 23:54
19
$\begingroup$

First, it is important to keep in mind that Turing Machines were initially devised by Turing not as a model of any type of physically realizable computer but rather as an ideal limit to what is computable by a human calculating in a step-by-step mechanical manner (without any use of intuition). This point is widely misunderstood -- see [1] for an excellent exposition on this and related topics.

The finiteness limitations postulated by Turing for his Turing Machines are based on postulated limitations of the human sensory apparatus. Generalizations of Turing's analyses to physically realizable computing devices (and analogous Church-Turing theses) did not come until much later (1980) due to Robin Gandy -- with limitations based on the laws of physics. As Odifreddi says on p. 51 of [2] (bible of Classical Recursion Theory)

Turing machines are theoretical devices, but have been designed with an eye to physical limitations. In particular, we have incorporated in our model restrictions coming from:

  • (a) ATOMISM, by ensuring that the amount of information that can be coded in any configuration of the machine (as a finite system) is bounded; and

  • (b) RELATIVITY, by excluding actions at a distance, and making causal effect propagate through local interactions. Gandy [1980] has shown that the notion of Turing machine is sufficiently general to subsume, in a precise sense, any computing device satisfying similar limitations.

and on p. 107: (A general theory of discrete, deterministic devices)

The analysis (Church [1957], Kolmogorov and Uspenskii [1958], Gandy [1980]) starts from the assumptions of atomism and relativity. The former reduces the structure of matter to a finite set of basic particles of bounded dimensions, and thus justifies the theoretical possibility of dismantling a machine down to a set of basic constituents. The latter imposes an upper bound (the speed of light) on the propagation speed of causal changes, and thus justifies the theoretical possibility of reducing the causal effect produced in an instant t on a bounded region of space V, to actions produced by the regions whose points are within distance c*t from some point V. Of course, the assumptions do not take into account systems which are continuous, or which allow unbounded action-at-a- distance (like Newtonian gravitational systems).

Gandy's analysis shows that the THE BEHAVIOR IS RECURSIVE, FOR ANY DEVICE WITH A FIXED BOUND ON THE COMPLEXITY OF ITS POSSIBLE CONFIGURATIONS (in the sense that both the levels of conceptual build-up from constituents, and the number of constituents in any structured part of any configuration, are bounded), AND FIXED FINITE, DETERMINISTIC SETS OF INSTRUCTIONS FOR LOCAL AND GLOBAL ACTION (the former telling how to determine the effect of an action on structured parts, the latter how to assemble the local effects). Moreover, the analysis is optimal in the sense that, when made precise, any relaxing of conditions becomes compatible with any behavior, and it thus provides a sufficient and necessary description of recursive behavior.

Gandy's analysis gives a very illuminating perspective on the power and limitations of Turing Machines. It is well-worth reading to gain further insight on these matters. Be forewarned however that Gandy's 1980 paper [3] is regarded as difficult even by some cognoscenti. You may find it helpful to first peruse the papers in [4] by J. Shepherdson, and A. Makowsky.

[1] Sieg, Wilfried. Mechanical procedures and mathematical experience.[ pp. 71--117 in Mathematics and mind. Papers from the Conference on the Philosophy of Mathematics held at Amherst College, Amherst, Massachusetts, April 5-7, 1991. Edited by Alexander George. Logic Comput. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m:00006 (Reviewer: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Classical recursion theory. The theory of functions and sets of natural numbers. With a foreword by G. E. Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-New York, 1989. xviii+668 pp. ISBN: 0-444-87295-7 MR 90d:03072 (Reviewer: Rodney G. Downey) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Church's thesis and principles for mechanisms. The Kleene Symposium. Proceedings of the Symposium held at the University of Wisconsin, Madison, Wis., June 18--24, 1978. Edited by Jon Barwise, H. Jerome Keisler and Kenneth Kunen. Studies in Logic and the Foundations of Mathematics, 101. North-Holland Publishing Co., Amsterdam-New York, 1980. xx+425 pp. ISBN: 0-444-85345-6 MR 82h:03036 (Reviewer: Douglas Cenzer) 03D10 (03A05)

[4] The universal Turing machine: a half-century survey. Second edition. Edited by Rolf Herken. Computerkultur [Computer Culture], II. Springer-Verlag, Vienna, 1995. xvi+611 pp. ISBN: 3-211-82637-8 MR 96j:03005 03-06 (01A60 03D10 03D15 68-06)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thanks very much! I always felt that Turing machines were a oddly inelegant, but this goes a fair way in explaining why that may be misconceived. $\endgroup$
    – PJTraill
    Commented Dec 2, 2016 at 19:43
7
$\begingroup$

The best popular discussion of this question that I've ever read is MIT professor Scott Aaronson's essay Who Can Name the Bigger Number?, in which he explores, among other things, the implications of super-Turing machines, super-duper-Turing machines, and super-duper-pooper-Turing machines.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ After "super-duper-pooper" comes "super-duper-ooper-flooper", or at least that's what I seem to recall from when I was maybe 7 or 8. It's probably the correct formal terminology. $\endgroup$
    – Peter Cordes
    Commented Dec 6, 2016 at 14:06
4
$\begingroup$

No, TMs are not most powerful. Two examples:

a) There could be other machines that compute the same results as a TM but algorithmically faster (e.g. quantum computers computing prime factors). "Faster" is a type of power.

b) TMs cannot represent general Real numbers with perfect precision. But an Analog Computer (AC) might be able to represent and do arithmetic with Real numbers with perfect precision. This would be more powerful than any TM.

Of course (b) requires our universe to have some continuous properties (gravity?) which the AC can use to represent Real values. Maybe every physical property, including gravity, is quantized. But we can speculate about machines in a continuous universe. So TMs are not most powerful "by definition".

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome to the site! "More powerful" in the context of computation theory is usually taken to mean "able to compute more functions", rather than "able to compute in fewer steps", so I'm not sure your (a) really counts. Also, it's not clear how a computer could use real values. How would you input a real value that wasn't, say, a computable real? How would you tell somebody else what value they should input to their continuous machine, and how would you deal with noise? But maybe that's a silly objection like, "How would you produce enough tape for the Turing machine to use". $\endgroup$
    – David Richerby
    Commented Dec 5, 2016 at 12:42
-5
$\begingroup$

If you look at computational complexity, a Turing Machine is the most powerful machine - because it has unlimited memory, and no real machine has that. Any real machine cannot solve problems of arbitrary size; they cannot even read a problem, much less solve it.

On the other hand, if you tried to implement a real Turing Machine, let's say with the provision that it stops and sounds an alarm if it runs out of tape, you would find that it would take many more steps for doing any kind of computation than let's say the real machine in a cheap phone, and would be much much slower at solving real problems. You would also find that writing an answer on a tape is not a very good user interface. And you would find that lots of people use computers not for solving problems, but for sending nude photos to their friends and for watching cat videos, and a Turing Machine isn't any use for that at all.

Improve this answer
$\endgroup$
3
  • 14
    $\begingroup$ Could you clarify how this answers the question? $\endgroup$
    – David Richerby
    Commented Dec 1, 2016 at 10:54
  • 1
    $\begingroup$ Obviously a real Turing Machine would be able to process photos and videos. Some kind of image output device would of course be needed for humans to see them, but that applies to any computer; a CPU+memory on a circuit board isn't "any use for that at all" alone, either. $\endgroup$
    – hyde
    Commented Dec 5, 2016 at 10:32
  • 1
    $\begingroup$ Among machine models with infinite memory, TMs are not the most powerful ones! $\endgroup$
    – Raphael
    Commented Dec 5, 2016 at 21:41

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.