2
$\begingroup$

Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same way we regard a number or a set (an abstract)?

If yes could I similarly use a Turing angel with infinite scroll instead, would that be ok?

EDIT: since I cannot comment. This question is somewhat different from infinity in mathematics because a set even infinite can have a finite representation. On the other hand there is no finite representation for an infinite tape That is the algorithm that generates the output.

Computation requires resources, that means that it takes place in a time-space, not in an abstract timeless dimension. While it could be ok to draw on demand more time for the computation pushing on to infinity, space has a cap on the amount of information it can hold, and before reaching that point the tape would revert to write only, that is implode into a black hole. So even if an algorithm is "finite" its output could be big enough to become "unreadable". For example lets say we have a machine that counts all numbers at some Number H when trying to add more information on the tape the tape colapses forms a black hole and number H+1 becomes unreadable. Counting up to H+2 is a finite process but cannot be completed. One could argue that space and time restrictions should not concern us but I m not convinced that is true when dealing with objects embedded in spacetime

I could accept a definition of a machine with sufficiently large tape. But I think that the size does matter. Can for example 2 Turing machines with different tape-size considered equivalent?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to CS.SE! It's hard for me to tell exactly what you're asking or what kind of answer you're looking for. I encourage you to edit your question to flesh it out, so that we can provide you a more useful answer; it can be considered for re-opening if the question is edited to be clearer. What are your thoughts? Have you read standard textbooks and resources on Turing machines? Why do you think we wouldn't be able to talk about it? See also cs.stackexchange.com/help/how-to-ask for more about how to use this site effectively. $\endgroup$
    – D.W. ♦
    Dec 17, 2015 at 23:57
  • 1
    $\begingroup$ If the machine stops after a finite number of steps, then it didn't actually need an infinite tape. It only needed a tape that was big enough. If the machine does not stop after a finite number of steps, then that's the same as saying the computation was not possible. So, saying "infinite" really is just a convenient way to say "big enough" without getting tangled up in the question of how big that actually is. $\endgroup$
    – Solomon Slow
    Dec 18, 2015 at 17:25
  • 1
    $\begingroup$ According to original description, the tape is not limited, and oversimplifying - it should be endless, but inreasing tape at will (when needed) is not in opposition to it's description. So I would stick to abstraction, but building such machine I would compare to making subAtlantic fiber optic cable - it was produced on ship while cables were put, not produced in advance. $\endgroup$
    – Evil
    Dec 18, 2015 at 17:48
  • 1
    $\begingroup$ The natural numbers also suffer from similar problems – should we stop using them as well? $\endgroup$
    – Yuval Filmus
    Dec 18, 2015 at 22:30
  • 1
    $\begingroup$ "Do we have the right to regard a machine (a construct) in the same way we regard a number or a set (an abstract)?" -- why, of course! In mathematical models, the mind is the limit. $\endgroup$
    – Raphael ♦
    Jan 13, 2016 at 7:25

2 Answers 2

Reset to default
15
$\begingroup$

The tape is not infinite. It is unbounded. There is an important difference. We don't need infinite memory. We only need to be able to add more memory over time as needed. This is actually pretty close to what people do in practice. When a program needs more memory it asks the operating system and receives more memory. If we see that a computer is short on memory we increase its memory. It is becoming even easier with cloud computing. So the assumption is not that the machine has infinite memory. The assumption is that we can increase the memory as needed.

If your question is about the limit where the needed memory reaches the limit of information that can be stored in the universe (assuming that it is finite and bounded by some fixed number) then yes, we will not be able to add any more memory at that point. In fact, if you assume that the amount of information is bounded by a fixed number then the world is a finite state machine. However that is not the usual case.

However if you try to design programs as finite state machines you are going to have a very difficult time because the number of states is huge. The number of states for a Turing machine with $m$ bits of memory would be something like $2^m$. Turing machines (and other similar models) simplify things. This is a rather common thing in sciences. It is important to know the limits of a model but the fact that a model is not a completely accurate representation of the world doesn't imply it is useless.

Improve this answer
$\endgroup$
8
$\begingroup$

In some sense, your question has been answered by switching from computability theory to computational complexity theory. In the latter, we care mostly about problems which a Turing machine can solve in polynomial time. In particular, such machines only use polynomial space. This is more realistic than the unrestricted Turing machine model.

However, even computational complexity suffers from similar problems, since we only care about the asymptotic behavior of Turing machines, whereas in real life we only care about the behavior on inputs of a certain size. Nevertheless, empirically computational complexity has shown some predictive power in some (but not all) cases.

A similar issue happens in classical mathematics – the natural numbers are potentially unlimited, and some people don't like it. They are called ultrafinitists.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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