Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

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?

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.

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.

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.

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.

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.

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

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 10¹⁰ states fundamentally different from one with 10²⁰ 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.

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.

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.

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.

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.

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.

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.