<p>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.</p>

CC BY-SA 3.0
2016-04-19T10:55:58.187Z
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.
Emil Jeřábek
CC BY-SA 3.0
2016-04-19T13:28:05.693Z
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.
Martin Berger
CC BY-SA 3.0
2016-04-20T08:36:45.087Z
@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.
Peter - Reinstate Monica
CC BY-SA 3.0
2016-04-20T13:44:46.270Z
@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.
Martin Berger
CC BY-SA 3.0
2016-04-20T15:12:01.573Z
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.
reinierpost
CC BY-SA 3.0
2016-04-20T15:18:15.737Z
@reinierpost, I agree, but the question was: why are we nowadays using Turing Machines to model computers? I understood it as independent of the original motivation for introducing Turing Machines.
Denis
CC BY-SA 3.0
2016-04-20T17:34:33.503Z
@Denis: We aren't. Computer programming, not computers.
reinierpost
CC BY-SA 3.0
2016-04-19T10:07:34.930Z
2016-04-19T10:07:34.930Z
Denis
<p>Andrej Bauer gave one important reason in the comments:</p>

<blockquote>
  <p>Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$.</p>
</blockquote>

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

<ul>
<li>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.</li>
<li>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.</li>
<li>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.</li>
<li>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 <a href="https://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence">it is equivalent to a $\Pi_1^0$ sentence</a>.</li>
</ul>

CC BY-SA 3.0
2016-04-20T08:36:07.847Z
2016-04-20T08:36:07.847Z
2017-04-13T12:57:54.777Z
Thomas Klimpel
<p>A formalism is useful or not, based on what people want to use the formalism to model and understand.</p>

<p>The Turing machine is a formalism that is useful for understanding <em>programs</em>.  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.</p>

<p>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.</p>

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

<p>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 <em>infinite</em> 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).</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-11-28T18:34:25.470Z
2017-11-28T18:34:25.470Z
Eric Allender
<p>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".</p>

<p>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.</p>

<p>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 <em>without</em> variables"; it has no tape on which to store intermediate results.  This is very unlike programs we actually write, which do have variables.</p>

<p>For a starting point on the literature, I can recommend "<a href="http://arxiv.org/pdf/1207.7149.pdf">On the Existence of Universal Finite or Pushdown Automata</a>", which studies non-existence of universal automata.  You might also look at its references (and so on).</p>

CC BY-SA 3.0
2016-04-19T06:43:55.377Z
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.
amon
CC BY-SA 3.0
2016-04-20T15:14:41.327Z
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.
reinierpost
CC BY-SA 3.0
2016-04-22T00:24:33.430Z
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.
Kaveh
CC BY-SA 3.0
2016-04-19T06:27:09.750Z
2016-04-19T14:12:28.063Z
2016-04-19T14:12:28.063Z
Eric Towers
<p>What makes the Turing machine special is that while being very, very simple, it can run <em>all</em> (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). </p>

<p>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").</p>

CC BY-SA 3.0
2016-04-22T00:27:33.930Z
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.
Kaveh
CC BY-SA 3.0
2016-04-19T16:53:09.723Z
2016-04-19T16:53:09.723Z
AnoE
<blockquote>
  <p>Why is the finite automata model not enough?</p>
</blockquote>

<p>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 <em>data</em> and <em>program</em>. 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<blockquote>
  <p>What is the point of studying these much stronger models with respect to real computers?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2016-04-20T09:01:11.607Z
2016-04-20T09:01:11.607Z
MvG
<h2>Most problems require finite-sized Turing machines</h2>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2016-04-20T23:54:50.277Z
2016-04-20T23:54:50.277Z
Peteris
<p>One important feature of turing machines that finite automata do not share is that they can <em>scale the amount of memory needed</em> to solve the problem with the <em>size of the problem</em>.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-21T17:16:32.567Z
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.
supercat
CC BY-SA 3.0
2016-04-20T18:55:26.377Z
2016-04-28T19:56:34.317Z
2016-04-28T19:56:34.317Z
josinalvo
<blockquote>
  <p>Real computers have limited memory and only a finite number of states. So they are essentially finite automata.</p>
</blockquote>

<p>Turing machines are derivatives of finite automata. Turing machines are practically von Nuemann architecture.</p>

CC BY-SA 3.0
2016-04-22T00:11:33.830Z
2016-07-06T01:16:24.603Z
2016-07-06T01:16:24.603Z
Jesse Enjaian
<p>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.</p>

<p>Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the <a href="https://en.wikipedia.org/wiki/Entscheidungsproblem">Entscheidungsproblem</a>. 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.</p>

<p>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.</p>

<hr>

<p>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:</p>

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ul>

CC BY-SA 3.0
2016-04-19T08:11:28.647Z
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.
Emil Jeřábek
CC BY-SA 3.0
2016-04-19T08:40:12.180Z
@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.
OrangeDog
CC BY-SA 3.0
2016-04-19T08:54:09.300Z
@OrangeDog but the universe would still put a limit to how much data can be stored in the observable universe
ratchet freak
CC BY-SA 3.0
2016-04-19T09:04:39.560Z
@ratchetfreak as the Turing machine demonstrates, you only need local access - the current "end" of the tape need not be within the observable universe ;)
OrangeDog
CC BY-SA 3.0
2016-04-19T09:41:51.507Z
@OrangeDog The usable length of the address is limited by the number of states your computer has. So at least a naive implementation of a network with infinite number of computers each with n bit memory could only have O(2^n) bit of usable memory. Technically you can cascade infinite levels of routers or bridges to do this job, but that's quite different from what we think the internet is like.
user23013
CC BY-SA 3.0
2016-04-19T10:53:51.723Z
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.
Jim Hefferon
CC BY-SA 3.0
2016-04-20T10:03:59.947Z
Your edit suggests that you agree with the point that actual computers are finite automata, but argue that it is conceivable that a Turing-equivalent computer could be physically realizable. But that's besides the point.
Emil Jeřábek
CC BY-SA 3.0
2016-04-20T10:21:53.643Z
That is my conclusion only in the case of a provably finite universe, because then there would be a constant upper bound on the amount of space usable. But I would still prefer to use Turing machines, as I believe they allow for better study of which problems are hard and which are not. If infinite memory is possible, it can be realized with current hardware, as long as it runs software that supports such addressing, as in my example for 64-bit.
chazisop
CC BY-SA 3.0
2016-04-20T15:05:23.213Z
@user23013: not true, the address space doesn't need to be finite, you can have arbitrarily deeply nested indirect addressing
reinierpost
CC BY-SA 3.0
2016-04-20T15:46:02.183Z
@reinierpost Your computer cannot distinguish two addresses after its state is exhausted, though. Depending on the implementation, the computer may just go into an infinite loop and never stop sending this address, or end up visiting a fixed address no matter how many addresses are theoretically available. Thinking again, my statement is indeed wrong. The computer could access other machines and use their memory in the middle of sending another address. The exact upperbound and whether it exists might be a difficult problem...
user23013
CC BY-SA 3.0
2016-04-20T15:56:13.443Z
[Historical reasons for adoption of Turing Machine as primary model of computation](http://cstheory.stackexchange.com/q/3650/)
Kaveh
CC BY-SA 3.0
2016-04-23T15:59:58.060Z
@user23013: It would be possible to design a system with variable length addresses in which a one-byte address could handle up to 128 locations, a two-byte address up to 16Ki, three bytes up to 2Mi, four bytes up to 256Mi, five up to 32Gi, etc. arbitrarily expandable from a logical perspective, and such a computer could be arbitrarily expanded during operation using nothing but an unbounded supply of interchangeable address-expansion blocks and unbounded-length cables to connect them.
supercat
CC BY-SA 3.0
2016-04-23T16:06:57.150Z
@supercat See my previous comment.
user23013
CC BY-SA 3.0
2016-04-19T05:17:45.187Z
2016-04-20T08:32:04.633Z
2016-04-20T08:32:04.633Z
chazisop
<p>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?</p>

CC BY-SA 3.0
2016-04-19T09:21:15.613Z
@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.
Martin Berger
CC BY-SA 3.0
2016-04-19T09:50:53.273Z
@Martin, I agree that this is an interesting philosophical question but IIRC we had this question either here or on [cs.se] some time ago.
Kaveh
CC BY-SA 3.0
2016-04-19T09:57:08.243Z
@Martin, see [1](http://cs.stackexchange.com/q/50887/), [2](http://cs.stackexchange.com/q/42555/), [3](http://cs.stackexchange.com/q/11514/), ... (there are probably more).
Kaveh
CC BY-SA 3.0
2016-04-19T10:25:11.193Z
The real question is, why study Turing machines, when we use the RAM model when we analyze algorithms.
Yuval Filmus
CC BY-SA 3.0
2016-04-19T13:30:03.657Z
@Kaveh thanks, I wasn't aware of these discussions.
Martin Berger
CC BY-SA 3.0
2016-04-19T13:40:06.243Z
A 2^1000000000000 state finite state automate is pretty big. That would be a computer with a 1TB harddisk that solves the algorithm purely on disk. Yes, finite, but enough digits to melt your eyes ;) At scales like that, modelling it as a finite state automata is hard; it is easier to invision it as infinite.
Lan
CC BY-SA 3.0
2016-04-19T15:07:48.767Z
Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$.
Andrej Bauer
CC BY-SA 3.0
2016-04-19T16:28:39.453Z
Why study integers when there are a finite number of atoms in the universe?  You're basically arguing for [Finitism](https://en.wikipedia.org/wiki/Finitism)
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2016-04-19T17:00:01.983Z
Keep in mind that a Turing machine contains a finite-state automaton within it. It doesn't hurt to study a broader computation model.
Nayuki
CC BY-SA 3.0
2016-04-19T23:00:19.633Z
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.
Eric Lippert
CC BY-SA 3.0
2016-04-20T16:01:21.977Z
@Eric, see [What would be the real-world implications of a constructive P=NP proof?](http://cs.stackexchange.com/q/35759/)
Kaveh
CC BY-SA 3.0
2016-04-20T16:03:22.253Z
@Martin, here is another related one: [Why, really, is the Halting Problem so important?](http://cs.stackexchange.com/q/32845/)
Kaveh
CC BY-SA 3.0
2016-04-20T20:37:17.973Z
Real materials are made of atoms and are discrete in nature, so why study integrals?
Peter Shor 
CC BY-SA 3.0
2016-04-22T03:33:31.263Z
@PeterShor : Because the relevant dual spaces aren't discrete.
Eric Towers
CC BY-SA 3.0
2016-04-22T05:16:22.147Z
@PeterShor or more fundamentally: the set of answers to any mathematical (or otherwise) question that could ever be asked, is countable, so why consider uncountable sets?
Frames Catherine White
<soft-question><fl.formal-languages><automata-theory><big-picture><turing-machines>
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
Rahul
# Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

(Asked by: username_0 on 2016-04-19)

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?

**Tags:** soft-question, fl.formal-languages, automata-theory, big-picture, turing-machines
> **Comments:**
> **username_1**: @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.  
> **username_2**: @Martin, I agree that this is an interesting philosophical question but IIRC we had this question either here or on [cs.se] some time ago.  
> **username_2**: @Martin, see [1](http://cs.stackexchange.com/q/50887/), [2](http://cs.stackexchange.com/q/42555/), [3](http://cs.stackexchange.com/q/11514/), ... (there are probably more).  
> **username_3**: The real question is, why study Turing machines, when we use the RAM model when we analyze algorithms.  
> **username_1**: @Kaveh thanks, I wasn't aware of these discussions.  
> **username_4**: A 2^1000000000000 state finite state automate is pretty big. That would be a computer with a 1TB harddisk that solves the algorithm purely on disk. Yes, finite, but enough digits to melt your eyes ;) At scales like that, modelling it as a finite state automata is hard; it is easier to invision it as infinite.  
> **username_5**: Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$.  
> **username_6**: Why study integers when there are a finite number of atoms in the universe?  You're basically arguing for [Finitism](https://en.wikipedia.org/wiki/Finitism)  
> **username_7**: Keep in mind that a Turing machine contains a finite-state automaton within it. It doesn't hurt to study a broader computation model.  
> **username_8**: 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.  
> **username_2**: @Eric, see [What would be the real-world implications of a constructive P=NP proof?](http://cs.stackexchange.com/q/35759/)  
> **username_2**: @Martin, here is another related one: [Why, really, is the Halting Problem so important?](http://cs.stackexchange.com/q/32845/)  
> **username_9**: Real materials are made of atoms and are discrete in nature, so why study integrals?  
> **username_10**: @PeterShor : Because the relevant dual spaces aren't discrete.  
> **username_11**: @PeterShor or more fundamentally: the set of answers to any mathematical (or otherwise) question that could ever be asked, is countable, so why consider uncountable sets?  

---

## 10 answers

### Answer by username_25 on 2016-04-19. Score: 32 | Accepted answer

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_13**: 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.  
> **username_26**: @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.  
> **username_27**: @OrangeDog but the universe would still put a limit to how much data can be stored in the observable universe  
> **username_26**: @ratchetfreak as the Turing machine demonstrates, you only need local access - the current "end" of the tape need not be within the observable universe ;)  
> **username_28**: @OrangeDog The usable length of the address is limited by the number of states your computer has. So at least a naive implementation of a network with infinite number of computers each with n bit memory could only have O(2^n) bit of usable memory. Technically you can cascade infinite levels of routers or bridges to do this job, but that's quite different from what we think the internet is like.  
> **username_29**: 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.  
> **username_13**: Your edit suggests that you agree with the point that actual computers are finite automata, but argue that it is conceivable that a Turing-equivalent computer could be physically realizable. But that's besides the point.  
> **username_25**: That is my conclusion only in the case of a provably finite universe, because then there would be a constant upper bound on the amount of space usable. But I would still prefer to use Turing machines, as I believe they allow for better study of which problems are hard and which are not. If infinite memory is possible, it can be realized with current hardware, as long as it runs software that supports such addressing, as in my example for 64-bit.  
> **username_15**: @user23013: not true, the address space doesn't need to be finite, you can have arbitrarily deeply nested indirect addressing  
> **username_28**: @reinierpost Your computer cannot distinguish two addresses after its state is exhausted, though. Depending on the implementation, the computer may just go into an infinite loop and never stop sending this address, or end up visiting a fixed address no matter how many addresses are theoretically available. Thinking again, my statement is indeed wrong. The computer could access other machines and use their memory in the middle of sending another address. The exact upperbound and whether it exists might be a difficult problem...  
> **username_2**: [Historical reasons for adoption of Turing Machine as primary model of computation](http://cstheory.stackexchange.com/q/3650/)  
> **username_23**: @user23013: It would be possible to design a system with variable length addresses in which a one-byte address could handle up to 128 locations, a two-byte address up to 16Ki, three bytes up to 2Mi, four bytes up to 256Mi, five up to 32Gi, etc. arbitrarily expandable from a logical perspective, and such a computer could be arbitrarily expanded during operation using nothing but an unbounded supply of interchangeable address-expansion blocks and unbounded-length cables to connect them.  
> **username_28**: @supercat See my previous comment.  

---

### Answer by username_12 on 2016-04-19. Score: 45

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.

> **Comments:**
> **username_13**: 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.  
> **username_1**: 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.  
> **username_14**: @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.  
> **username_1**: @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.  
> **username_15**: 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.  
> **username_12**: @reinierpost, I agree, but the question was: why are we nowadays using Turing Machines to model computers? I understood it as independent of the original motivation for introducing Turing Machines.  
> **username_15**: @Denis: We aren't. Computer programming, not computers.  

---

### Answer by username_16 on 2016-04-20. Score: 10

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](https://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence).


---

### Answer by username_17 on 2017-11-28. Score: 9

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.


---

### Answer by username_10 on 2016-04-19. Score: 6

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](http://arxiv.org/pdf/1207.7149.pdf)", which studies non-existence of universal automata. You might also look at its references (and so on).

> **Comments:**
> **username_18**: 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.  
> **username_15**: 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.  
> **username_2**: 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.  

---

### Answer by username_19 on 2016-04-19. Score: 2

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

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_20 on 2016-04-20. Score: 1

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


---

### Answer by username_21 on 2016-04-20. Score: 1

## 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?


---

### Answer by username_22 on 2016-04-20. Score: 1

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.

> **Comments:**
> **username_23**: 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.  

---

### Answer by username_24 on 2016-04-22. Score: -2

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


---

