# Turing machine - infinite tape - does that thing exist?

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?

• 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. – Solomon Slow Dec 18 '15 at 17:25
• 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. – Evil Dec 18 '15 at 17:48
• The natural numbers also suffer from similar problems – should we stop using them as well? – Yuval Filmus Dec 18 '15 at 22:30
• "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. – Raphael Jan 13 '16 at 7:25

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.