In a nutshell: Turing Machine can do (finitely specified) infinite
computations on (finitely specified) infinite data and produce
(finitely specified) infinite results. The basic idea is that those
infinities can be defined as the limit of finite entities, defined in
a mathematically appropriate way. This is the basis of mathematical
semantics of computation. If you consider programs rather than Turing Machines, these programs can also contain (finitely specified) infinite data-structures. The case of a tabulated function
fact as a possible algorithm is analyzed
in the end, as a program, or as a TM model, with a hint regarding the relation with lazy evaluation of infinite objects.
With many more details
Regarding your final question, a TM does not compute on arbitrary numbers,
but on symbolic representation of these numbers as arbitrarily
(unbounded) long strings of symbols representing them. Modulo proper
encoding, it is correct that they can compare or do arithmetics with
such numbers through these representations.
But the original question is about the role of infinity in Turing
Machines in general.
A common answer to this question is that Turing Machines never deal
with infinity. They are finitely defined, and whatever they compute is
computed in finite time on a finite part of the tape (hence a finite
tape that is larger would be enough). What is true is that the time of
space requirement of the TM are unbounded, which is not the same as
Hence, any answer that is computed by a TM could be computed as well
by a finite-state automaton (FSA), which is "to some extent" one way
to look at tabulation. The difficulty there is that some input sizes
(it nearly always comes to that, if only to read the input) will
exceed the size of the automaton. But then, we can just use a bigger
one. So if we want to consider unbounded input size, we need an
infinite sequence of FSA that can do the computation. Actually we may
need a finite-state machine a bit more complex than the traditional
FSA since there may be an output to be computed (rather than a yes-no
answer), but a finite state transducer should probably do.
So, if we are looking at a problem that has an infinite set of
instances, such as computing a GCD, or simply using arithmetics on
integers of arbitrary size, we see that infinity is coming
back at us through the back door, as this infinite set of FSA.
But there is another problem. The above analysis works only when we
consider computations that do terminate with a result. But not all TM
do that. Some may enumerate the members of an infinite set. This is
typically the case for a TM that computes the decimals of $\pi$ and
keep adding new one, indefinitely. Of course, it computes only a
finite answer in a finite time, but what we are interested in is
really the infinite sequence produced by an infinite computation.
Notice that we now have two aspects of infinity: infinity of
computation, and infinity of the result (i.e. of some computed data).
Actually that could even lead to considering infinite input ... but
let us ignore this complication, that deals with unbounded streams of
data. Note also that such computations that give an output other than yes
Then again, we can replace that by an infinite sequence of finite
computations with finite machines. But are we cheating.
From a physical point of view, that is the best we can do. We only
know how to build finite machines, at least according to the current
state of the art in physics, which is not expected to change too much
on that issue in the near future.
But how can we handle those infinities in a consistent and tractable
way from a mathematical point of view.
When you consider an infinite set of FSA that can sort of cooperate to
compute an infinite set of answers, you cannot do it arbitrarily. You
need some safeguards to ensure that what you are doing makes sense.
It is well known that you can trivially build any set with an infinite
union of regular sets, actually with an infinite union of singleton
sets. So, considering arbitrary infinite unions of automata without
any restriction will lead you nowhere. You even consider in the same
set automata that give you inconsistent answers.
What you really want is define a notion of consistency. But that
requires some precautions. Let us assume you are using an infinite
sequence of automata to simulate a TM that answer yes or no, or does
not halt. The problem is that a FSA will always halt with an answer,
such as yes or no. But if you use a FSA that is actually not sized big
enough for the chosen input, what should it answer. Both yes and no
are reserved for the cases when the FSA actually terminated the TM
computation, and using one of these answer with an unfinished
computation would only lead to confusion. What you want is an answer
that says: "sorry, I am too small and I cannot tell. Please try with a
bigger guy in the family". In other word you want an answer such as
overflow, or don't know. Actually it is called by semanticians
"undefined" or also "bottom" and often written "$\bot$".
So you need automata that have 3 sorts of states: accepting,
non-accepting, and undefined. An undefined state may be viewed as a
state standing for a missing part of the automaton that forces
computation to stop. So, when computation halts, depending on the
state it halts on, you get the answer yes, no, or undefined.
Now, you see that what you want is infinite sequences of automata
that are consistent. Both yes and no are consistent with
undefined, but yes is not consistent with no. Then two automata
are consistent when they give consistent answers on the same input.
This can be extended to automata that compute other kind of
answers. For example if they compute colors, such as red, blue, green
..., you can add the undefined color which is consistent with all
others. If the answer is an infinite sequence of digits such as those
of $\pi$, then each digit can be consistently and independently
replaced by undefined so that $3.14\bot\bot\bot\bot...$ is consistent
with $3.1415\bot\bot\bot\bot...$ and with
$\bot.\bot5159\bot\bot\bot\bot...$, but the latter two are not
consistent with $3.1416\bot\bot\bot\bot...$. Actually, in this sense, $3.1416\bot\bot\bot\bot...$ is not an approximation of $\pi$. We say that an answer is
better defined than another when it contains all the information that
can be found in the other one, and possibly more. This is actually a
I will not develop further these theoretical aspects, which is a bit
awkward when based on Turing Machines. The point is that these
concepts lead to the idea that computation domains (whether data or
machines), form mathematical structures such as lattices, in which
infinite object can be adequately defined as the limits of infinitely
increasing (i.e. better and better defined) sequences of finite objects. Defining the infinite
sequences requires some more apparatus, and a notion of
continuity. This is fundamentally what Dana Scott's theory of
semantics is about, and it gives a somewhat different view of the
concepts of computability.
Then, Turing machines, or other formal devices that can do "infinite
computation" can be defined as limits of sequences of finite
approximations of the machines, that are better and better defined.
The same is true for whatever data the machines compute with, whether
input or output.
The simplest document I ever read on this is a hand-written set of
lecture notes by Dana Scott, often referred to as the Amsterdam
lecture notes. But I could not find it on the web. Any pointer to a
copy (even incomplete, as I have part of it) would be welcome.
But you can look at other early publications by Scott such as
Outline of a Mathematical Theory of Computation.
Back to the initial example of the question
These approximation concepts apply to data as well as to programs. The
fact is defined recursively, which means that it is the
least fixed point of a functional that can be used to compute a
sequence converging finite approximation of
fact. This sequence of
more and more defined finite functions converges to an infinite entity
that is what you call the function
But if you use array lookup, you can do exactly the same, with your
code containing larger and larger tables which are all finite
approximations of the infinite table of precomputed values of
Each of these array can actually give an answer for any integer, but
the answer can be $\bot$ (undefined) when the table is not defined
enough (big enough). The table look-up algorithm too must be defined
by a sequence of approximations, as it computes with an infinite
It is true that, if you consider the elementary TM model of
computation, such an infinite array cannot be expressed in that
formalism. It does not mean that it would not make sense. A Turing
machine could have a second tape that is supposed to be initialized
with the tabulated values of some functions such as
fact. It does
not change the computational power of the TM, as long as that function
is a computable one, i.e. as long as the table can be initialized with
an infinite computation of another TM that can compute all
argument-value pairs for the relevant function.
But in practice, you cannot complete an infinite computation. Hence the right way to do it is to compute the table lazily, i.e. to fill entries only when needed. That is precisely what is done with memoization, which is the answer I gave you, with different justifications, for your previous question.