Do Turing machines assume something infinite at some point?

Question

In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm.

One of the answers that caught my attention was this one:

The factorial example gets into a different model of computation, called non-uniform computation. A Turing Machine is an example of a uniform model of computation: It has a single, finite description, and works for inputs of arbitrarily large size. In other words, there exists a TM that solves the problem for all input sizes.

Now, we could instead consider computation as follows: For each input size, there exists a TM (or some other computational device) that solves the problem. This is a very different question. Notice that a single TM cannot store the factorial of every single integer, since the TM has a finite description. However, we can make a TM (or a program in C) that stores the factorials of all numbers below 1000. Then, we can make a program that stores the factorials of all numbers between 1000 and 10000. And so on.

Doesn't every TM actually assume some way to deal with infinity? I mean, even a TM with a finite description that computers the factorial of any number N through the algorithm

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

contains the assumption that a TM has the "hardware" to compare numbers of arbitrary size through the "<=" comparator, and also ADDers to increment i up to an arbitrary number, moreover, the capability of representing numbers of arbitrary size.

Am I missing something? Why is the approach that I presented in my other question less feasible with respect to infinity than this one?

Answer 1

A Turing machine does not have the ability "to compare numbers of arbitrary size through the <= comparator" because a Turing machine does not have a "<= comparator". A Turing machine has a fixed, finite set $Q$ of states and a fixed, finite tape alphabet $\Sigma$. At each step of the computation, the Turing machine looks at its current state and the symbol under its read/write head and decides what to do next: which state to enter, which symbol to write to the tape and which way to move the tape head.

Because of this, a Turing machine cannot compare arbitrarily large numbers in a single <= instruction. Using the state, it can remember at most $|Q|$ different numbers and, using the alphabet, it can write at most $|\Sigma|$ different numbers in a single tape cell (using each possible symbol to represent one number). As such, to compare arbitrarily large numbers on a Turing machine, you must write each number as a sequence of digits on the tape and write an algorithm that will take multiple steps to compare those two numbers. As you can imagine, this makes writing Turing machine programs a rather fiddly endeavour.

Turing machines don't really "deal with infinity": they deal with unbounded finite things, at least in their standard definition. The input is a finite string and, after any finite number of steps, the machine has only examined or written to a finite number of tape cells. There is no bound on the size of the input or the number of computation steps but, the input is finite and, after any finite number of steps, only a finite amount of output has been produced.

Answer 2

I think the important distinction to make is that the description of the Turing machine is finite, as is the input to the machine, while the tape it uses as memory is infinite. The TM is is a mostly finite machine, which uses a finite tape. Consider the tape to be composed of cells, where each cell can contain a single value. The input to the TM is written on the tape.

The description of a TM is a finite set of tuples <current state, input, output, move, next state>.

At each step, the thing to be done is found by matching the current state and input. Eg, we are in state 0, and we read a 1, so we find the tuple that begins <0, 1, ...> then we write a new value in the current cell, move left or right (I think the classic definition also allows for staying at the same cell as well), and then change to a new state.

So, for your example, you would either need an infinitely large description of the TM (an infinite number of <current state, input, output, move, next state> tuples), or include the lookup information in the input to the TM. I believe the input to a TM is defined to be finite. So, that's probably not something you could do with a classically defined Turing machine.

The Fibonacci example, in contrast, can be computed in binary with a finite number of tuples to describe the TM, and has a finite input.

Answer 3

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

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 partial ordering.

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 function 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 fact.

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 fact. 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 table.

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.

Answer 4

The gist of this answer is that Turing Machines can mimic anything we can program, and we do program computations on, with and of infinite objects.

This is a second answer focussing more on the specific question asked than on the general theoretical framework that justifies the answer, and would be definitively needed to answer the more general title of the question. It is fully compatible with my previous answers to the OP's questions, both What exactly is an algorithm? and Do turing machines assume something infinite at some point?, answers in which I developed more the theoretical context. This may be seen as answering both questions.

Turing machines do have the ability to deal with infinity, as can all Turing complete computational models, though only with denumerable infinity. Our problem is that we can observe only part of this infinity, but we have to consider the whole of it since the part we may observe is unbounded.

The other problem is that we can deal ourselves only with finitely specified entities. Actually, the whole structure of science as we know it falls down if we consider entities that are not finitely specified, since it becomes impossible to check consistency of definitions, to even know what the definitions are, since we can access only part of them in a finite time.

There is possibly another fundamental issue that is somewhat similar to the fact that closure under infinite union defines any set you want, unless you can finitely restrict appropriately what is permitted in such a union. But I am not sure I fully understand this issue.

As I said, Turing machines do have the ability to deal with infinity. I am contradicting other well upvoted answers of some high rep users, who should know what they talk about on such an elementary topic.

The problem is that Turing chose a very elementary model of computation to achieve his theoretical purpose. The simpler, the better. It is to more advanced/sophisticated models of computation pretty much what machine language is to programming: something very obscure where you cannot recognize any of the concepts that do make sense in high-level programming. The fact is that, like machine language, TM can mimic much more than they can directly express.

Furthermore no one actually believes in these limitations of the Turing Machine, and many varieties of TM have been devised, with more or less exotic features. If some infinite sets are called recursively enumerable, it is because TM can actually enumerate (representations of) their members, which does require an infinite computation (see Turing Machines as Enumerators in Hopcroft-Ullman 1979, page 167). Of course, we can always encode that as finite computations that would answer questions such as: what is the $23{rd}$ member of the set according to your enumeration of them? But it would still be often implemented as an infinite computation that is artificially stopped when the right answer is attained.

Actually, all users who state that everything is finite but unbounded in a TM are quite careful to add that they consider Turing Machines in their standard definition. The problem is that the standard definition is just a device to simplify the theory, but is pretty much irrelevant when trying to understand computational structures.

Actually, the only thing that matters in computation is that everything must be finitely specified in a computable way, not that it be finite.

We are assuming that a turing machine must be a finite object. But that is not true. You can define a model of Turing machine using a second tape that is read only, and contains a function tabulated for all integer values, without any bound. That is infinite. But it does not buy you any extra computing power as long as the content of that tape is computatbly specified (the computability implies that it is finitely specified). The extra tape could well be replaced by a TM machine embedded in the other one, and would provide the answers, instead of looking for them on the extra tape. From a higher level, the difference is not visible.

From a practical realization point of view, we could have a fact turing machine computing factorials and tabulating them on the extra tape, while another TM would used the tabulated factorial from the extra tape, just waiting on the first TM whenever the tabulation has some still missing entry. But the second machine does assume that the content of the tape is ultimately infinite. The tabulating machine does not even have to work all the time, but must resume computation whenever data is requested from the table and is not found there.

Coming back to the question, the main difference between unbounded integers and the infinite table is only that integers are finite, unbounded but completely computed in finite time. The infinite table is computed indefinitely, finite but still growing all the time to infinity. That is not a problem, but is a difference. Infinite objects are accessible only through finite approximations, ... but they are infinite. Computable irrational numbers are, in this sense, infinite objects, at least for their representation as binary numbers.

All algorithms are defined in the context of some mathematical theory. And a table look-up together with an infinite table is an algorithm. But it is an algorithm in a mathematical theory having a finitely defined infinite set of axioms that specify extensively (rather than intensively) the values of a function it axiomatizes for each integer argument. (see my answer to your previous question). Then it is always legitimate to do so, as you can always add provably true statements to the axioms of a theory.

Usul statements, as reproduced in your current question, is in my opinion incorrect (though everything is also a matter of definition). His conclusion in his answer, that you did not reproduce, is that the use of an infinite table cannot be considered an algorithm because it can only be implemented by a non-uniform model of computation, by a collection of different machines, and hence such uses "do not have a finite description that can be implemented to solve the "whole" problem for any input size". This is wrong. His partitioning into disjoint machines that have separate domains of definition is just a wrong way to do things. The right way is to have an infinite sequence of consistent machines with larger and larger domains of definition, which can appropriately converge to the infinite machine that answers the question. That is one essential purpose of the mathematical theory of semantics of computation defined by Dana Scott. With proper mathematical apparatus, it does define precisely infinite machines, values with infinite representations (such as e or $\pi$), or infinite data structures, that are all computable. (see my first answer to this question).

The way such infinite entities are computed with in practice is by means of lazy evaluation, computing just whatever part is needed at any time, and resuming the computation for some of the rest whenever more becomes needed. That is exactly what is proposed above with the fact machine lazily computing factorial to be stored in a table, whenever more data is needed from the table.

In a way, that seems to vindicate the assertion (in DanielV's answer) that the codespace must be finite, since lazy evaluation will be actually based on some finite code. But computability is a pervasive game of encoding, so that, among other things, distinguishing code from data is always pretty much in the eyes of the beholder. Indeed, many modern programming languages do not make much difference between intensional and extensional specification of values, and Denotational Semantics does not really distinguish "2+2" from "4". Semantics is really what we are talking about when asking a question such as "What is X?".

This view of the finiteness of code, also seen as static, is another reason why an infinite table (considered as part of the code) is not seen on an equal footing with unbounded integers used as data. But that is another illusion that does not survive known programming practice in metaprogramming, reflexive languages, and the use of the evalfunction. In those languages, code can be extended without bounds by the running program itself, as long as the computer is running. Indeed one could consider Turing Machines that modify their own transition rules, increasing their number without bound. That is pretty close to the way Universal Turing machines are working.

When designing theoretical frameworks, there is always a tension between simplicity and perspicuity or expressivity. Simplicity make analysis of the framework often simpler, especially when it come to proving specific properties or reducing it to other frameworks. But it is often inconvenient for expressing high level concepts that must then be encoded. We do not program with Turing Machines, but with high level languages that are a lot more expressive and perspicuous, and may at the same time erase some barriers such as the distinction between code and data, on the basis of semantic equivalence. Turing machines seem simple, but can go far beyond their elementary definition.

Answer 5

The short answer: no. Turing machines do not assume anything infinite at any point.

This is one reason why they are valid as a model for computation. It doesn't make sense to describe computation as something performed by an infinite device.

However, their operation may be infinite: it may not terminate. This is another reason why they are valid as a model for computation. Devices that can only perform operations which are guaranteed to always terminate cannot express all possible computations.

What is more: operation requires unbounded memory: while the actual amount of memory in use is always finite, it may grow arbitrarily large. So you can't supply all the memory any operation will ever need in advance. Devices that can only perform operations which are guaranteed to never use more than a certain fixed amount of memory cannot express all possible computations.

Answer 6

"thinking out of the box" and generalizing on this question that does get to some heart of the abstraction of Turing machines, and coming up with a different angle not already answered: yes, Turing machines have some intrinsic aspects of "assuming infinities" just as the concept is intrinsic to mathematics. TMs are an abstraction of physical machines. the physical concepts of Time and Space are purposely used in TM theory but as abstractions, however also with aspects of their real counterparts.

in short the TM can possibly run forever in theory, aka the halting problem. the tape is infinite but only a finite amount of it can ever be written to at a given time. a TM that runs forever basically assumes that time and space are unlimited, ie "infinite". in fact there is a corresponding Time and Space hierarchy / "continuum" that is infinite.

but no physical realization of this abstract concept is possible assuming the physical universe is bounded (space, time, matter, the last of which is somewhat analogous to "symbols" or "ink" in the Turing machine). somewhat similarly/ analogously, in physics sometimes the universe is regarded as unbounded/ infinite, but only as an abstraction. to flip this, that is also why the "modelling" of a modern computer as a Turing machine is itself an abstraction, because the computer can only have finite memory etc.

another useful comparison is the number line in mathematics. the number line is infinite, but it denotes finite numbers. every number on the number line represents a finite quantity, but there an infinite number of these finite quantities. the Turing machine tape has a strong similarity to the number line concept from mathematics. Turing could have easily defined it as only infinite in one direction, but he defined it as infinite in both directions, much like the mathematics number line, with negative positions "left" on the tape and positive positions "right".