Is a Turing machine too strong of a model to model physical computation?

Question

I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing thesis is wrong and that a Turing machine does not accurately model any possible real world computation. To me, it seems that not only is the Turing machine not too restrictive, it's actually unrealistically strong. Namely, it has unbounded tape and time in which to perform its computation!

I suppose that the counterargument to this would be that unbounded is not the same as infinite, and in an idealized model of the physical universe we really have unbounded space and time in which to perform computations (neglecting minor details like the expected heat death of the universe and the possibility of finite space). But still, it seems as though we are basing our ideas of what is computable on an unreasonably strong model.

So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature? Or is there some deep inherent reason why unboundness is a requirement of any such model?

Edit: To address the comments so far - I know that a Turing machine with bound tape is equivalent to a DFA, and therefore definitely does not capture in any reasonable way the notion of possible real world computations. I was rather referring to models that might not resemble Turing machines at all.

Answer 1

No, it is not too strong. We fundamentally conceive of computation as an activity with unlimited resources.

For instance, take a very popular and simple algorithm such as long division. It takes two arbitrarily large numbers and can produce an arbitrarily large resulting number. During the computation, an arbitrarily large amount of scrap paper may be needed. The natural numbers are an infinite set. This is absolutely fundamental to our notion of mathematics, calculation, and algorithms. Without it, you lose expressive power: you lose the ability to write down many algorithms. With only a fixed amount of numbers, we cannot really say what division is.

Long division is a simple algorithm in that it is linear: the amount of scrap paper and time needed to execute it is directly proportional to the size of its input.The only reason it needs an arbitrarily large amount of space and time to execute is that the input can be arbitrarily large. What is more, some versions of long division only need constant space: with an eraser and paper of infinite quality, we can make do with a fixed amount of paper, if we don't need to write the input and output down on it, but instead, feed them through as streams of digits.

Turing machines do not share this property. Some do: they only use a constant amount of tape or steps, or only a linear amount, as a function of input size; or the amount of time and size they use is limited by some other function of the input size. But for many other Turing machines, it is not: the amount of resources their execution may use has no expressible (computable) relationship with the size of the input at all. This is a higher order sense of unboundedness. Can we at least say that this amount of unboundedness is excessive and unnecessary?

The answer, once again, is no: if we rule this out, we lose calculation power! Certain functions from inputs to outputs can only be computed by algorithms whose resource usage is unbounded by any function of the input size. So there is nothing frivolous or unrealistic about this property of Turing machines: computation is fundamentally like that.

In terms of practical imperative programming, what this means is that we fundamentally need dynamic memory allocation. It would be very nice if we could rewrite all C programs such that they first compute how much memory they possibly need, allocate it all, and only then start the computation process. Doing so would completely eliminate the dreaded runtime Out of memory error. The theory of computation shows us that this is fundamentally impossible: some algorithms do not have an equivalent of this type that computes the same input-output function.

Answer 2

Is it too strong?
The concern should not be that a Turing machine is a too strong model because of the way we construct a Turing machine. Turing machine is essentially a framework for defining a notion of algorithm in its basic, simple steps. Every algorithm executed on a Turing machine can be executed by hand, meaning it is effectively calculable (one direction of Church-Turing thesis). The real question is - is there an effectively calculable function whose computation cannot be encoded in a Turing machine. This all seems that it must hold (and therefore many computer scientists accept Church-Turing thesis as true), but cannot formally be proven just because the term "effectively calculable" is not formally defined.

Why not bound it?
I am not sure if this satisfies your quest for "deep inherent reason why unboundness is a requirement", but think about it this way: What if we bound the tape? Say, a Turing machine must have tape of length at most $M$, for some $M \in \mathbb{N}$. Let's look at $2$ examples:

1. We can choose/construct a Turing machine $T_M$ that uses exactly $M$ distinct positions on a tape. Then, we can construct a Turing machine $T_{M+1}$ that runs exactly as $T_M$ with additional step - that it writes a symbol after the last symbol on its tape, once it finishes all the running steps of $T_M$.
   This Turing machine (algorithm) $T_{M+1}$ therefore could not exists if we bounded the tape at $M$, but obviously - this algorithm is effectively computable.

2. Say you want to construct a Turing machine that adds two numbers. What if the length of numbers is more than $M$? We could not add them (nor even write them) with a Turing machine, but can obviously add them (say, by hand) via standard known algorithms for addition (that also doesn't have restrictions on length/tape).

Therefore, we must not bound the tape if we want to be able to compute things that we can in theory compute (by hand). The same arguments holds if we would want to bound the number of steps (time).

Computatioal complexity deals with resources required by an algorithm depending on size of the input, so you might want to look at that subject.

---

So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature?

Turing machine is a finite model.

---

Different model
$\lambda$-calculus is a computational model invented by Turing’s doctoral advisor Alonzo Church. It does not resemble Turing machine and it is based on a concept of definition and application of functions. Turing and Church proved that their models are equal in computational power.

Answer 3

No, the Turing machine isn't unreasonably strong. You could build a physical Turing machine by giving it a finite length of tape and the ability to say "I've run out of tape – please give me more!" and that's something an ordinary computer can do, too, if it has removable media.

After any finite amount of time, a Turing machine will have used only a finite amount of tape, so you'll never need to give it an infinite amount. Yes, there are the limitations of the physical universe, which seems to place a limit on how much tape you can actually make, but we don't have a good model of what can be computed within some fixed but mind-bogglingly large amount of resource. And there doesn't seem to be much point in producing such a model: restricting to computations that can be performed within the universe's physical resources still allows for computations that would take longer than the extinction of the human race, and even that isn't a very practical limitation to place. The Turing machine is a reasonable approximation, which abstracts away all these fiddly details about computations that we can't physically do and simultaneously avoids us having to argue about what is physically possible, anyway.