9
$\begingroup$

According to the Bekenstein bound, Turing machines are not realizable in real life. So why are they accepted as the standard for effective computation? You may as well consider more powerful machines since neither is realizable in real life.

Furthermore, why not use a finite-state machine (FSM) with very large number of states as our accepted effective computation definition since that would be capable of being implemented?

$\endgroup$
7
  • 32
    $\begingroup$ Do you also think that pysicists should not use differential equations to describe the basic law of fluid dynamics? After all, a fluid is just finitely many molecules. $\endgroup$ Commented May 21 at 23:40
  • 8
    $\begingroup$ I suppose you could take some basic theorems in computability theory and see how they get destroyed if you try to apply them to finite state automata. $\endgroup$ Commented May 21 at 23:59
  • 2
    $\begingroup$ If we care about the finite capacity of real computers, and how much of that capacity is needed to execute certain algorithms, then we don't need to abandon the Turing machine model of computation. We can analyse the resource usage of an algorithm in terms of its time and space complexity. Then you don't need to change your model of computation or your methodology every time the "real computers" you care about get better. 10^10 might sound like a big number, but it's not much larger than the number of different IPv4 addresses, and we've already run out of those. $\endgroup$
    – kaya3
    Commented May 22 at 11:50
  • 3
    $\begingroup$ A FSM with 10^20 states will not be able to determine if a 200-character (binary) string is a palindrome. A TM with only a few states and, say, a bounded tape of length 500 will easily do so. Your computer will too. A FSM with 10^20 states will be able to check if your input equals the first 10^20 binary digits of pi (by hardcoding them). Said bounded TM won't. Your computer also won't. $\endgroup$
    – ManfP
    Commented May 22 at 14:46
  • 6
    $\begingroup$ When computer scientists ask "Is it computable?" they mean, without regard for how much memory or how much time or how much of any other resource the computation needs. We could argue all day about whether or not that makes any sense, but there's no point in arguing about whether or not that's what they really mean. It's just a simple fact. $\endgroup$ Commented May 22 at 21:51

14 Answers 14

35
$\begingroup$

In addition to the fine answer by D.W. let me point out the difference between actual and potential infinity.

A Turing machine is not actually infinite because at no point of its execution do we actually need an entire infinite tape. The assumption that we can always get more tape if needed means that the tape is potentially infinite. Sometimes the phrase unbounded tape is used to avoid talking about infinity, which trips up many people. This is quite a bit more reasonable than asking, say, that an infinite tape be made available upfront.

In fact, assuming some hard (arbitrary) bound on the size of avialable tape, say $10^{10}$, is not going to be mathematically insighful or useful, nor will it tell us much about the practice of computing, and will in fact be quite annoying. A much better way to approach the practice of computing is to refine the Turing machine model and incorporate computational complexity.

So let us compare this to a real situation. When you run out of cloud disk space for photos, do you start lamenting about how the universe is only finite, or do you pay for more disk space, not worrying too much where it's going to come from?

$\endgroup$
14
  • 25
    $\begingroup$ @JobHunter69 Have you tried writing proofs about a FSM with 10^10 states? Turing machines are a lot easier to work with mathematically! $\endgroup$
    – Draconis
    Commented May 22 at 3:56
  • 5
    $\begingroup$ I think it's useful to discuss some specifics about why that's true: TMs can arbitrarily use other TMs as subroutines; FSMs with bounded size can't. TMs can take arbitrary amounts of data as input; FSMs with bounded size can't. TMs can take each other's descriptions as input; FSMs with bounded size can't. Complexity bounds, which apply in the limit, all become uninteresting, O(1), with bounded size. $\endgroup$ Commented May 22 at 10:32
  • 1
    $\begingroup$ There are countless TM which require an infinite tape, even machines where all paths halt. $\endgroup$ Commented May 22 at 16:26
  • 3
    $\begingroup$ @JobHunter69 Do you want to throw away all previous research when a FSM with 10^11 states becomes practical, or 10^12, or perhaps 10^13? $\endgroup$ Commented May 22 at 20:38
  • 5
    $\begingroup$ What you don't seem to be considering is that your choice for an unreasonably large FSM corresponds to using ~34 bits of memory to store the current state. Meanwhile, the FSM program (transition table) for such a machine takes nearly 1 TB to store. This is not how real programs on real computers are structured. They are actually much more like Turing machines. $\endgroup$
    – Dan Doel
    Commented May 23 at 2:30
24
$\begingroup$

Turing machine are accepted because they are useful as a theoretical model. They are (relatively) easy to reason about, and the theory leads to insights that are useful. Please make sure to read Does our PC work as Turing Machine? for more discussion that is closely related. Roughly speaking, approximating $10^{10}$ with $\infty$ is a fairly decent approximation for many purposes.

In general, a model rarely perfectly captures all elements of reality. Instead, it is a simplification that captures the most essential elements, enough to be useful, while omitting some details that are messy to think about but are not essential. As you can tell, it requires some taste and judgement to choose models. Many models can be useful for different things; the Turing machine model happens to be especially useful.

It's hard to discuss more powerful machines without knowing specifically what you have in mind, but generally they are even worse -- they often are less useful, because they more often make predictions that aren't a good match for our experience. Just because nothing is perfect is not a sufficient reason to switch from something that is a little imperfect to something that is more imperfect.

$\endgroup$
6
  • 9
    $\begingroup$ @JobHunter69, because the distinctions are useful. Empirically, it is useful to know that a problem is decidable or undecidable; that a language is regular or non-regular. It's helpful to know that some problems are unsolvable even if you buy more memory. And it turns out that for many problems, it is often easier to prove "it cannot be computed by a Turing machine" than "it cannot be computed by a FSM with $10^{10}$ states". $\endgroup$
    – D.W.
    Commented May 21 at 19:02
  • 6
    $\begingroup$ Tangentially, the number $10^{10}$ is way too small. My laptop is a finite state machine with way more than $10^{10}$ states; it has more than $10^{10^{10}}$ states! $\endgroup$ Commented May 22 at 4:02
  • 7
    $\begingroup$ @JobHunter69 there already is a subfield which considers exclusively realistic models of computation, it’s called “programming” :P $\endgroup$ Commented May 22 at 8:33
  • 4
    $\begingroup$ @AwkwardWhale Who would want to study that, it's muddied up by all those icky, unpredictable "programmers"? $\endgroup$
    – Barmar
    Commented May 22 at 14:26
  • 1
    $\begingroup$ @JobHunter69 The most basic practical use of the concept of a Turing machine is that we know that any computer is equivalent to a Turing machine can solve the same problems as any other computer that is equivalent to a Turing machine. You need not compare every language to every other one to determine if they can solve the same problems, you just need to show Turing equivalence. An FSM doesn't generalize in that way. $\endgroup$
    – JimmyJames
    Commented May 22 at 15:21
8
$\begingroup$

This is like asking, "Why do we use real numbers like pi to model physical processes when human ability to measure is necessarily imprecise and finite?"

First off, a Turing machine is not a physical device. It is a mathematical model. It can handle infinitely long tapes just fine. The Beckenstein bound is just the idea that we cannot make an exact, physical Turning machine without having access to infinite space for infinite data.

The reason this doesn't matter: all computation (assuming Church-Turing) can be modeled with a Turing machine. If Turing machines can also be used to model programs and data that are too big to fit into the accessible universe, that's just fine.

Why would we want a mathematical model that stops working at an arbitrary number? If our understanding of the universe changes and we realize the bound is different, it could break the model.

Moreover, there is significant utility to being able to represent "impossibly large" machines. We can and do use them in mathematical proofs, sometimes revealing facts that actually apply to the real world.

$\endgroup$
2
  • $\begingroup$ Are you sure the Church-Turing thesis (being based on the universality of TM) is not based essentially on infinity as well? $\endgroup$
    – Nikos M.
    Commented May 22 at 16:57
  • 1
    $\begingroup$ @NikosM. The thesis simply states that every natural function which you can "effectively" calculate in reality can be modeled with a Turing machine. If there is no way in reality to calculate a given function on naturals (due to, for example, finitary constraints), the thesis does not apply. $\endgroup$ Commented May 22 at 17:22
5
$\begingroup$

It's not clear your invocation of the 'Bekenstein bound' is sensible. This constrains the information in some volume, but why should your infinite tape need to be located in some small box near the head? If you need a humongous number of instructions, maybe you start with the other end of the tape in Andromeda. If the 10^78 m^3 of the current Hubble volume is too small, imagine dark energy is actually quintessence and the Hubble volume will continue to grow indefinitely.

$\endgroup$
4
$\begingroup$

The Turing machine is not necessary, either as an actual machine or an imaginary one, in order to prove the theorems that typically refer to it. It is only an easy-to-describe encapsulation of a mathematical structure, such as, for instance, the set of bounded mappings $\mathbb N \to \{0,1\}$ (the “tape”) each with some description of internal states and a transition map.

A Turing machine cannot be built in the same sense that, for instance, the set of all natural numbers cannot be built out of bolts and screws, or even out of quarks. You may object to mathematics referring to actual infinities, but that is an issue that is not specific to the Turing machine.

$\endgroup$
4
$\begingroup$

I assume the OP is reacting to an assertion like this at the start of the Wikipedia article on the Bekenstein bound. That is, the primary criticism is about Turing machines being infinite:

In computer science this implies that non-finite models such as Turing machines are not realizable as finite devices.

Note that it is useful to consider a model that's infinite, in that it simplifies reasoning about the model in many cases. There are no boundary or special-case conditions to consider. We don't need to adjust conclusions as technology advances, or debate what a reasonable bound is. If we find that a task is impossible in the infinite model, then it's an obvious corollary that the task is impossible in any finite model as well.

Here are other examples from mathematics where this occurs:

  • Must numeration systems (natural numbers, real numbers, etc.) assume we can count upwards without limit. There are mathematical theories that assume some universal upper bound, but they are more complex to reason with, and have not found widespread public usage.

  • Dense number systems like the rationals or reals (that can be subdivided infinitely) are useful and widely used, but we know from atomic and quantum mechanical physics that things in reality cannot be divided infinitely. Nonetheless, the model is more useful than the alternatives. Likewise for things like continuous functions and probability distributions.

  • In inferential statistics, the simplest assumption for computing a standard error is to say that a random sample is drawn from an infinite population. If one wants to handle drawing from a finite population, that requires more complex adjustment factor, the finite population correction (FPC). But doing so makes such a tiny difference that people usually ignore it (i.e., effectively assuming an infinite population).

So, assuming an infinite memory space for Turing machines fits squarely into the family of useful mathematical models where removing the boundary conditions provides a lot of simplifying power, at negligible reduction in the quality of the conclusions.

$\endgroup$
4
  • 2
    $\begingroup$ The particular claim on WP also seems suspect. The claim has no reference. Also, this discussion on the talk page of the WP article suggests the Bekenstein bound does not rule out a tape of infinite length, it only notes that this must fit an infinitely large universe. (as opposed to an infinitely dense tape) There are likely other physical laws which prevent infinite tapes, but this one alone doesn't seem to be sufficient. $\endgroup$
    – Discrete lizard
    Commented May 23 at 7:59
  • $\begingroup$ "If we find that a task is impossible in the infinite model, then it's an obvious corollary that the task is impossible in any finite model as well" that is not correct as it depends on how the infinity is used in the impossibility result. For example, for TM's that run up to some finite time (eg if the universe has finite lifetime), the halting problem is decidable in at most that finite time.. $\endgroup$
    – Nikos M.
    Commented May 23 at 14:44
  • $\begingroup$ In other words, Turing's halting theorem depends essentially on infinity existing for its proof. In a finite universe it does not hold. $\endgroup$
    – Nikos M.
    Commented May 23 at 14:58
  • $\begingroup$ "The count increases to 16 or infinity, whichever comes first" (regarding the RIP network protocol, which has a 4-bit representation of distance). $\endgroup$ Commented May 23 at 15:56
3
$\begingroup$

Starting with the Bekenstein bound means you are already lost at the starting gate in terms of mathematics.

Take. for example, addition. The existence of a number x + y is no longer true (no representation exists for certain values), not to mention the set of integers and reals. There is no realistic representation of addition with a machine of finite size. One has to deal with overflow.

An machine that can become infinite like a touring machine can match the mathematics of reals, integers, and a TM exists for addition. This is just one demonstration on why abstract machines are better suited towards certain forms of analysis.

$\endgroup$
2
$\begingroup$

Suppose we do as you suggest, how would we decide how many states to use in our model? Is there something that makes an FSM with 1010 states fundamentally different from one with 1020 states? If you prove a theorem for the first FSM, is it necessarily true for the second FSM?

If these theorems are true/false regardless of the actual number of states we assign to the FSM, then why should the number of states be fixed at all? We've got conclusions that work for any number of states, so for theoretical purposes the number of states is effectively unbounded.

Adding more states is like adding more memory to a real computer -- it simply allows you to work with larger problems, but doesn't change the fundamental nature of what you can do. Hardware limits don't really come into play unless you're writing real-world applications that are pushing the boundaries, they don't impact theoretical analysis of algorithms.

$\endgroup$
6
  • $\begingroup$ Well my point was, we should take a FSM with some number of states such that its impossible to build a computer in real life with more states than that. Thus we have a tighter bound on the problems that can be computed or not in real life. $\endgroup$ Commented May 22 at 15:03
  • 4
    $\begingroup$ But we can theoretically always build a bigger computer. 50 years ago it wasn't feasible to build computers with more than a few KB of RAM and a few MB of secondary storage. These sizes have since increased by several orders of magnitude. The nature of what is theoretically computable hasn't changed, although what is practical has. $\endgroup$
    – Barmar
    Commented May 22 at 15:25
  • $\begingroup$ For the second time, that's not what I'm saying. "some number of states such that its impossible to build a computer in real life with more states than that" - means theoretically largest computer possible. i'm talking about possibility with current technology $\endgroup$ Commented May 22 at 20:36
  • $\begingroup$ And the point everyone is making is that "current technology" is not usually interesting on a theoretical level. Anything you determine about it will be obsolete a year later. $\endgroup$
    – Barmar
    Commented May 22 at 20:43
  • 2
    $\begingroup$ @JobHunter69 If you take something like a "10^10^(number of electrons in the universe)" as the number of states, then (a) all the proofs will become much more complicated (unless they just revert to "it's impossible in the turing machine, so it'll also be impossible in this huge impossible computer") and whenever you get some possibility result, you still don't know whether it will work on a real-life computer. So the usefulness is limited. $\endgroup$ Commented May 22 at 22:06
2
$\begingroup$

Turing machines are accepted as the standard for effective computation because we don't think of computation as bounded by a fixed amount of resources.

Take, for instance, adding two numbers. That's a computation, right? How much memory do we need to add two arbitrary numbers? The answer is: arbitrarily much, because natural numbers can be arbitrarily large, so even to just represent the input we need arbitrarily much tape.

If you don't like this example, consider another: suppose you want to define an algorithm for sorting arbitrary strings. What sort of mathematical description would you propose for that? One that can only sort up to some given length? No, we want a description how to sort arbitrary strings, no matter how long. That's how we think of sorting, so that's what we want to describe. If the string has more characters than there are atoms in the universe, the description will still say how to sort that string.

Hence, if we want to model the notion of computation, we need a model that has an arbitrarily large amount of working space at its disposal. Exactly what the Turing machine provides. We're not modeling things in the physical universe, we're modeling general stepwise processes defined for infinitely many different potential inputs.

Turing machines model computation, they don't model computation with fixed resources, because we don't think of computation that way. The Bekenstein bound has nothing to do with computation.

Don't believe people who say that Turing machines can't be built because they need infinite memory. If these people were consistent, they would also say that addition of numbers or sorting of strings is impossible because natural numbers and strings need infinite space to be represented. And they never say that, because it isn't true.

Addition, or any computation, is an abstract process. We can mathematically express adding the total number of atoms in the universe to itself, even though we cannot physically add these atoms together. The bounds of physical reality are not what computation is about, so they don't belong in the models, unless of course you explicitly want to reason about computing with fixed resources.

$\endgroup$
1
$\begingroup$

I think we prefer TM as a model for its extended properties which not only allow us to answer quantitative questions about computing algorithms, but also more abstract questions which go beyond "can I and how strong does my machine need to be in order to do x bound by y in t?" and answer the next level of questions about possible expansions of machines. Most importantly TM models allowed us in some sense to reveals not just an infinite amount of boundries which correspond to the infinite amount of possible SM of different configurations and "power", but to find the one true boundry which divides certain algorithms where no possible extention of your machine could ever help you get to the end as opposed to "eventually the problem can be cracked". I think its an important result, because otherwise we might consider ourselves involved into a mathematical theorem eternally asking the question: is my machine strong enough now? when studying incomputable functions without getting any answer, as opposed to knowing that no such thing could exist in the first place beforehand.

$\endgroup$
1
$\begingroup$

I would like to present an answer that evokes the historical motivation for defining the Turing machine.

You're solving mathematical problems. What kind of problems can you solve without any leap of intuition or inspiration; just each step of your solution clearly following from the previous one? Let's call this manner "mechanical".

Let's consider one example: adding together two numbers $x$ and $y$ in base 10. You know a procedure which requires taking pairs of digits of the two numbers from least significant to more significant, then looking up this pair in a table that holds, for each pair, two values: one digit of the result and a carry etc. (I'll skip the rest of this annoyingly detailed description).

The numbers we usually add are quite small, but in principle we could add two numbers of any length with this method. So let's imagine long decimal representations.

You have a pen and a sheet of paper and you proceed to scribble symbol after symbol, composing your solution.

What will you do when you reach the end of the page? Turn it and continue writing on the next one.

But what will you do when you reach the end of the notebook? Get a new one and continue your solution on page 1 of the second notebook.

And so on.

The question is: can you "mechanically" add two natural numbers represented in base 10?

You are limited in many ways; how many notebooks do you own? How many new ones can you afford? How much paper is there in the world to allow you to go on with your calculation?

We could make a best-case scenario calculation (in which you may employ all the paper on Earth) and we would come up with a gigantic, but finite length for $x$ and $y$, beyond which you simply do not have paper to continue your calculation. But what if then you could import some more from Mars?

All this seems quite irrelevant to the core of the question; you, as a mathematician, can obviously "mechanically" add two numbers together and the only limitation lies in the resources available. This is hard to quantify or predict and seems besides the point: for any length $n$, as long as there's a sufficient, finite quantity of paper, you can do it.

Similarly, a Turing machine can compute the sum of $x$ and $y$ and anything computable. If you realize one in the physical world, it will solve any instance of the problem. When it reaches the end of the tape, just feed it some more.

$\endgroup$
0
$\begingroup$

Turing machines aren't really about "can be implemented in physics", but rather as a formalization of things that can be described by an algorithm. For example, there is an algorithm to check if a number is prime or not (despite there being no finite state machine describing them), but there is no algorithm to check if a mathematical statement is true or not.

The notion of algorithm is a bit vague tho, hence why we use Turing machines as a formalization of the notion of algorithm.

$\endgroup$
1
  • $\begingroup$ Thats not correct, this definition was chosen because it could be implemented $\endgroup$ Commented May 22 at 20:33
0
$\begingroup$

Turing machines were developed to mathematically formalize abstract concepts about computability. They serve that purpose quite well.

It's unfortunate that the word "machine" and references to tapes and heads etc. makes people imagine some concrete, real world implementation, but the subject matter is arguably more abstract than math itself because if we define math as "the study of patterns" and mathematical notation as "a language to describe patterns", then turning machines deal with the capabilities and limitations of any such language no matter the form.

Expanding on that definition of math: the beauty is that we can study patterns beyond what our specific universe allows. It's up to physicists to identify the specific patterns that govern our universe.

Math is unconstrained by such limits. If one doesn't need to assume some specific universe to prove a general property of computation, one shouldn't. Adding unnecessary assumptions and constraints often obscures the problem.

This is kind-of key to interpreting some of the proofs based on the TM model.

For example: Kolmogorov proved using the pigeon hole concept that a general lossless compression algorithm can't exist. Yet, people use general lossless compression every day like zip-files. What gives? Was Kolmogorov wrong? No. We live in a low entropy universe which means most files have some structure to them which a zip algorithm can exploit. So the zip algorithm isn't general. It only works on bit streams that have sufficient structure. If you took a file with N bits, theoretically, the vast majority of possible N-bit strings would be so lacking in structure that zip would actually increase their size. But theoretically, the vast majority of possible digital photographs are indistinguishable from TV static. Only a vanishingly tiny subset would have discernable shapes and features.

You can always constrain the general model to a more specific case if you think it will provide insight. Nothing's stopping you from doing that.

I personally think if we constrained resource analysis to a model based in 3 special dimensions, such that memory access takes O(N^1/3) where N is the size of the working set . It would yield more insight that assuming random memory access is O(1). But that's for another day.

I don't think the Beckenstein bound actually does preclude a turning machine. The bound is the upper limit on information that can fit in a finite space. AFAIK there is no known limit to the size of the universe.

I'm also not sure if an infinite tape is part of the definition of a turning machine or just a common assumption for convenience. I think one could discuss turning machines with finite tapes. I don't think the math police are going to bust down your door and arrest you for referring to such constructs as turning machines in your proof about the implications of bounded-tape TMs.

$\endgroup$
0
$\begingroup$

A small caveat to infinity, from both a mathematical and philosophical perspective, you can never prove anything is infinite. You can prove it's much larger than any bound you test, but there could always be a stop further past that. So if Infinity is to be used as a concept, which to some extent it must be if we're going to use finite as a concept, then we must acknowledge a concept that can only be posited or stated to be true, not proven to be true in any sort of practical sense.

$\endgroup$
1
  • $\begingroup$ (Split that hair with Peano?) $\endgroup$
    – greybeard
    Commented May 26 at 8:23

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.