41
$\begingroup$

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent models) for studying computers? What is the point of studying these much stronger models with respect to real computers? Why is the finite automata model not enough?

$\endgroup$
  • 7
    $\begingroup$ @Kaveh People usually handwave that yes, computers used in practise are FSMs, but the FSMs are too large and interesting structural properties get lost in FSM view. I've never seen a non-handwavy explanation. Therefore the question is on topic here. $\endgroup$ – Martin Berger Apr 19 '16 at 9:21
  • 15
    $\begingroup$ The real question is, why study Turing machines, when we use the RAM model when we analyze algorithms. $\endgroup$ – Yuval Filmus Apr 19 '16 at 10:25
  • 39
    $\begingroup$ Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$. $\endgroup$ – Andrej Bauer Apr 19 '16 at 15:07
  • 29
    $\begingroup$ Remember, the most famous unsolved problem in theoretical computer science today is: can one kind of physically impossible imaginary computer solve problems as fast as an even more physically impossible imaginary computer? Don't mistake theoretical computer science for practical computer engineering; the details of the physical world are not particularly relevant. $\endgroup$ – Eric Lippert Apr 19 '16 at 23:00
  • 22
    $\begingroup$ Real materials are made of atoms and are discrete in nature, so why study integrals? $\endgroup$ – Peter Shor Apr 20 '16 at 20:37

10 Answers 10

32
$\begingroup$

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or even forgotten.

Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is intimately related to the great effort in the first decades of the 20th century to completely axiomatize mathematics. The hope was that once you have proven a small set of axioms to be correct (which would require substantial effort), you could then use a systematic method to derive a proof for the logical statement you were interested in. Even if someone considered finite automata in this context, they would be quickly dismissed since they fail to compute even simple functions.

Technically, the statement that all computers are finite automata is false. A finite automaton has constant memory that cannot be altered depending on the size of the input. There is no limitation, either in mathematics or in reality, that prevented from providing additional tape, hard disks, RAM or other forms of memory, once the memory in the machine was being used. I believe this was often employed in the early days of computing, when even simple calculations could fill the memory, whereas now for most problems and with the modern infrastructure that allows for far more efficient memory management, this is most of the time not an issue.


EDIT: I considered both points raised in the comments but elected not to include them both of brevity and time I had available to write down the answer. This is my reasoning as to why I believe these points do not diminish the effectiveness of Turing machines in simulating modern computers, especially when compared to finite automata:

  • Let me first address the physical issue of a limit on memory by the universe. First of all, we don't really know if the universe is finite or not. Furthermore, the concept of the observable universe which is by definition finite, is also by definition irrelevant to a user that can travel to any point of the observable universe to use memory. The reason is that the observable universe refers to what we can observe from a specific point, namely Earth, and it would be different if the observer could travel to a different location in the universe. Thus, any argumentation about the observable universe devolves into the question of the universe's finiteness. But let's suppose that through some breakthrough we acquire knowledge that the universe is indeed finite. Although this would have a great impact on scientific matters, I doubt it would have any impact on the use of computers. Simply put, it might be that in principle the computers are indeed finite automata and not Turing machines. But for the sheer majority for computations and in all likelihood every computation humans are interested in, Turing machines and the associated theory offers us a better understanding. In a crude example, although we know that Newtonian physics are essentially wrong, I doubt mechanical engineers use primarily quantum physics to design cars or factory machinery; the corner cases where this is needed can be dealt at an individual level.

  • Any technical restrictions such as buses and addressing are simply technical limitations of existing hardware and can be overcome physically. The reason this is not true for current computers is because the 64-bit addressing allowed us to move the upper bound on the address space to heights few if any applications can achieve. Furthermore, the implementation of an "extendable" addressing system could potentially have an impact on the sheer majority of computations that will not need it and thus is inefficient to have. Nothing stops you from organizing a hierarchical addressing system, e.g. for two levels the first address could refer to any of $2^{64}$ memory banks and then each bank has $2^{64}$ different addresses. Essentially networking is a great way of doing this, every machine only cares for its local memory but they can compute together.

$\endgroup$
  • 4
    $\begingroup$ The second part of this answer is wrong. Computers are finite state automata, even if you bought all RAM and other hardware you could. The amount of RAM you can connect to a computer is limited by the width of its address bus, and the same holds for disks and other periferals. $\endgroup$ – Emil Jeřábek Apr 19 '16 at 8:11
  • 12
    $\begingroup$ @EmilJeřábek not true. Serial interfaces don't have an address bus, and the amount of data I can access on the internet is not limited by any property of my computer. $\endgroup$ – OrangeDog Apr 19 '16 at 8:40
  • 5
    $\begingroup$ @OrangeDog but the universe would still put a limit to how much data can be stored in the observable universe $\endgroup$ – ratchet freak Apr 19 '16 at 8:54
  • 9
    $\begingroup$ @ratchetfreak as the Turing machine demonstrates, you only need local access - the current "end" of the tape need not be within the observable universe ;) $\endgroup$ – OrangeDog Apr 19 '16 at 9:04
  • 6
    $\begingroup$ In mentioning the history, it is worth quoting Church's review of Turing's paper, that Turing machines have "the advantage of making the identification with effectiveness ... evident immediately." That is, to people trying to convince themselves that they had indeed captured everything that could be computed, Turing's definition was compelling. $\endgroup$ – Jim Hefferon Apr 19 '16 at 10:53
43
$\begingroup$

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the state space infinite. This infinity can be perceived as an abstraction of "very big in front of the size of the data". When writing a computer program, you try to save space for efficiency, but you generally assume that you won't be limited by the total amount of space on the computer. That is part of the reason why Turing Machines are a better abstraction of computers than finite automata.

$\endgroup$
  • 14
    $\begingroup$ This is IMHO the right answer. The reasons are purely pragmatic, Turing machines do better than finite automata at explaining what computers do at the scales involved. $\endgroup$ – Emil Jeřábek Apr 19 '16 at 10:55
  • 3
    $\begingroup$ I agree with this except the sentence "you generally assume that you won't be limited by the total amount of space on the computer". On the contrary, almost any non-trivial program is limited by the space available and programmers go to great lengths to deal with it (e.g. garbage collection for automatic memory reuse), but (1) there is nothing we can do about it, and (2) we restrict ourselves to small-enough inputs. It is noteworthy that TMs give us a natural handle on problem size, and that algorithms tend to be downwards-closed w.r.t. this natural notion of problem size. $\endgroup$ – Martin Berger Apr 19 '16 at 13:28
  • 2
    $\begingroup$ @MartinBerger Re "almost any non-trivial program is limited by the space available and programmers go to great lengths to deal with it (e.g. garbage collection for automatic memory reuse)": I'd contend that programs written for systems with garbage collection consider that system, including the gc, as the machine they program against. The garbage collector is not part of the program; it is part of an effort to provide precisely what Denis said: A machine to program against which has virtually unlimited memory resources. $\endgroup$ – Peter A. Schneider Apr 20 '16 at 8:36
  • 2
    $\begingroup$ @PeterA.Schneider I kind-of don't agree. The reason of using the GC provided by the language runtime is one of the economics of software development: program specific memory management mechanism is more performant than GC and most programmers would prefer it if they could pull it off safely and cheaply. But they can't, so rather play safe and use the ambient GC whose cost is amortised over a large number of programs. In that sense using GC is going to great length to deal with the finiteness memory. $\endgroup$ – Martin Berger Apr 20 '16 at 13:44
  • 2
    $\begingroup$ Turing machines aren't abstractions of what computers do, they are abstractions of what computing does, and computers were built after that. Computers happen to do most of their computations using a fixed amount of internal working memory, but Turing Machines weren't invented for reasoning about computation with a bounded amount of working memory. $\endgroup$ – reinierpost Apr 20 '16 at 15:12
10
$\begingroup$

Andrej Bauer gave one important reason in the comments:

Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$.

Let me complete the other answers by some points, which were probably too obvious to mention:

  • If your goal is to study real computers, then both finite automata and Turing machines will often be too simple models for the relevant questions. Real computers have multiple processing cores with a cache hierarchy (or some other smart management scheme), access to a decent amount of fast memory, access to huge amount of slow external memory (hard disks), and can communicate with other similar computers at a speed roughly comparable to the access speed to the slow external memory.
  • If you now ask yourself why you need all those details, then it turns out that your real goal is the study of problem instances and how efficiently you can solve them. If you are talking about real computers, this can also mean that you run experiments with actual problem instances on different type of (real) computer architectures.
  • The model of real computers described above is still idealized, because it ignores the various failure modes of real computers. Because power off failure might be more frequent than hard disk failure (and hard disks might have backups anyway), certain problem domains like reliable database operation might need to take that into account.
  • If we now accept that problem classes and problem instances are what really interests us, then Turing machines (and finite automata too) become mathematical (and linguistic) tools for stating (and proving) interesting propositions about problem classes and problem instances. For example, the concrete problem instance could be the Riemann Conjecture, and the proposition about it would be that it is equivalent to a $\Pi_1^0$ sentence.
$\endgroup$
7
$\begingroup$

A formalism is useful or not, based on what people want to use the formalism to model and understand.

The Turing machine is a formalism that is useful for understanding programs. Programs are worth understanding; most actual computation is performed by programs, rather than by special-purpose machines. The Turing machine formalism allows us to model important real-world concerns such as time- and space-complexity. It is much less natural to try to study these notions using finite-state automata.

Turing machines are not very useful when trying to study the complexity of computing finite functions (say, functions whose domain consists of inputs of length at most 10 million). Circuit complexity is much better at describing the complexity of finite functions ... but Turing machines in turn have been very useful in understanding circuit complexity.

Finite automata have also been useful in understanding circuit complexity; all of these models have their place in the mathematical arsenal.

I reject the argument that says that finite-state automata are a better model of reality purely because real-world computers have only a finite number of internal states. The study of finite-state automata crucially deals with inputs coming from the infinite set of strings, whereas real-world computers deal with inputs of only some fixed maximal length (unless you believe that we live in an infinite universe, either in terms of space or time).

A model should be judged in terms of its utility in understanding those aspects of reality that we care about. Or (alternatively) in terms of its utility in understanding a mathematical universe that people find sufficiently compelling, even if that mathematical universe has no obvious physical manifestation.

Turing machines, finite-state machines, and circuits (and other models besides) all have proved their utility.

$\endgroup$
6
$\begingroup$

Actual computers are not FSAs. An actual computer is a universal computer, in the sense that we can describe a computer for a computer to emulate and the computer will emulate it. For many examples, search for "virtual machine".

It is possible to construct a Universal Turing Machine -- a TM that receives a description of another TM then emulates the operation of that TM on a supplied input.

It is not possible to construct a Universal Finite State Automaton. Say an FSA has been supplied that is described as a Universal FSA. It has a finite number of states, $n$. Write down an FSA that has $2^{2^n}$ distinct states. It is hopeless that the proposed Universal FSA can represent so many states. (The TM can do so by just using more tape.) This is also summarized as "an FSA implements a program without variables"; it has no tape on which to store intermediate results. This is very unlike programs we actually write, which do have variables.

For a starting point on the literature, I can recommend "On the Existence of Universal Finite or Pushdown Automata", which studies non-existence of universal automata. You might also look at its references (and so on).

$\endgroup$
  • 3
    $\begingroup$ This is a useful approach to intuitively grasp different levels of “computational power”. However, OP seems to think that real computers are FSMs because the number of states is limited, e.g. because of finite RAM. By your argument, this means real computers are more like FSMs than Turing Machines because I can't freely double the number of states in a simulated machine; I don't have an infinite tape as storage. $\endgroup$ – amon Apr 19 '16 at 6:43
  • 1
    $\begingroup$ Turing Machines don't need to have an infinite tape, either. Computers can use an arbitrarily large amount of external storage in their computations (and it becomes particularly easy with the cloud providers we have today), so they are fundamentally like Turing Machines rather than FSMs. $\endgroup$ – reinierpost Apr 20 '16 at 15:14
  • 1
    $\begingroup$ If we assume that a computer has a fix amount of memory it will ran out of memory when simulating a computer with more memory, so with that assumption it is not really universal. $\endgroup$ – Kaveh Apr 22 '16 at 0:24
3
$\begingroup$

What makes the Turing machine special is that while being very, very simple, it can run all (classes of) algorithms we can think of. There is no known machine that is more powerful (in that it can run algorithms the Turing machine is not capable of).

Being mechanically simple, it is easy to show whether, or to which degree, other machines are equivalent to a Turing machine. This in turn makes it relatively easy to show whether a given computer (or computer language) is truly universal (c/f "Turing-complete").

$\endgroup$
  • $\begingroup$ The question is about the relation of the Turing machine model with real computers. If we assume that a computer has fixed amount of memory it is not really universal. $\endgroup$ – Kaveh Apr 22 '16 at 0:27
1
$\begingroup$

Why is the finite automata model not enough?

While other answers have already mention many relevant aspects, I believe that the stronges advantage of Turing machines over finite automata is the separation of data and program. This allows you to analyze a quite finite program and make statements about how that program would handle different inputs, without restricting the size of the input.

While it is theoretically possible to describe both an actual computer and something like a Turing machine with finite tape as a state machine, that is not really feasible: the number of states is exponential in the amout of memory your machine has, and the general finite state automaton formalism requires you to explicitely list the transitions between these states. So for a general finite state automaton of that size it's quite infeasible to make any deductions based on a full enumeration of all state transitions.

Of course, in a real computer, states transitions can't happen arbitrarily. There is no command to swap a third of the bits in memory in a single step of the computation. So you could try to come up with a more compact specification for the state transitions. Something like the instruction set specification of your architecture. Of course, real computer architectures are complicated for the sake of performance, so you could simplify this further, to some very simple instruction set, which just performs very small steps using very limited input and output. In the end you may find that your architecture resembles something like a Turing machine interpreter: using some bits of program code and one bit of input, generate a bit of output and move around in your program code.

One alternative would be using the states of a finite state automaton just to represent the data being processed by the program, while encoding the program itself into the state transitions. That would entail the same problem of how to enumerate all states, and a compact representation might again be close to what a Turing machine does.

What is the point of studying these much stronger models with respect to real computers?

On the whole I'd say that a finite-tape Turing machine would probably be a better model for actual computers. But for many scientific questions, the distinction between a finite but large and an infinite tape is irrelevant, so just claiming an infinite tape makes things easier. For other questions, the amout of tape used is at the core of the question, but the model easily allows you to speak about the amount of tape usage without the hassle of specifying what happens if the computation runs out of tape.

$\endgroup$
1
$\begingroup$

Most problems require finite-sized Turing machines

While assuming unbounded tape is a useful simplification, most problems/algorithms in fact require a finite amount of tape, and the bounds of the required memory (possibly depending on the size of input) can be analyzed and often proved.

This also often generalizes to other types of computers (for which bound analysis or proof may be much messier than on a Turing machine), and allows to estimate the amount of temporary storage required for a particular problem - can it be done in a fixed amount of space? Proportional to the input? Does it require exponential amounts of space as the inputs grow?

$\endgroup$
1
$\begingroup$

One important feature of turing machines that finite automata do not share is that they can scale the amount of memory needed to solve the problem with the size of the problem.

Lets say (numbers invented) that check if a graph has a hamiltonian path, given a graph with $n$ vertices, you need $n\cdot2$ bits of memory. You can fully describe this relationship using a turing machine. You also can describe this relationship using an infinite number of finite automata: the implementations of this turing machine with limited tape. You probably need to account for some details, but you can somewhat convince yourself with a simple argument: This is what we usually do with computers! We implement a solution that uses more space for larger problems, and the computer runs our solution with its bounded number of states.

The point: many problems have natural solutions that use more memory the bigger the problem is. So, it is natural to describe these solutions with representations that can use infinite memory - not because any one instance will use infinite amounts it, but because there is an instance that uses each amount. You can do it with turing machines, but also with sequences of finite automata.

$\endgroup$
  • $\begingroup$ On a related note, if a Turing machine with N states is started with a tape that has a finite number of C non-blank characters before and after the initial position, there will be some number T(N,C) such that any machine which will ever terminate could be emulated by one machine a machine whose tape was limited to T(N,C) characters. $\endgroup$ – supercat Apr 21 '16 at 17:16
-2
$\begingroup$

Real computers have limited memory and only a finite number of states. So they are essentially finite automata.

Turing machines are derivatives of finite automata. Turing machines are practically von Nuemann architecture.

$\endgroup$

protected by Lev Reyzin Apr 22 '16 at 2:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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