Re: Turing machines and tape length

[Tim Gwinn <***>]

Howard,

 

If the idea of an infinite tape on a Turing machine seems problematic or irrelevant outside the formal proof itself, it suffices to consider Turing machines with arbitrarily long, finite-length, tapes. (The Turing machine is otherwise already defined as being finite, in terms of finite number of distinct internal states, finite symbol expressions per tape square, etc.) From "What is a Turing Machine?" ( http://www.earlham.edu/~peters/courses/logsys/turing.htm):

"It does not matter whether we think of the tape as finite or infinite in length. But if it is finite, we will assume there will always be enough for a given operation. (If this sounds too indefinite for this exact realm, then let us say that whenever the scanner comes within n cells of either end of the tape, a human technician adds another m cells to that end; n and m may be as small as 1 to fix the principle, but we may make them each a trillion if it will bring greater peace of mind.) Since all computable functions take only a finite number of steps to compute, by definition, no operation in which we are interested will require an infinite tape. In short, the remarkable power of the Turing machine does not require an infinite tape."

 

This is described formally in Martin Davis' book, Computability and Unsolvability (Dover ), in "The General Theory of Computability", " Chapter 1: Computable Functions".  (Omitting the formal definitions here) he states:

"At this point, we must remove a basic inconsistency between our rigorous definitions and our intuitive picture. We have visualized our machine as possessing an infinite tape; yet, formally, the _expression_ on the tape of a Turing machine at an instantaneous description a is always finite, and we have required that there always be a symbol scanned at any instaneous description. This difficulty is removed by means of a special symbol S0 or B. We change our intuitive picture to that of a machine with a tape that is always finite but that can be extended. The machine is to have the property that, whenever it is about to rush off the end of the tape, a new square, on which appears a B, is "spliced" onto that end of the tape."[p. 6, ital. orig.]

 

Thus, strictly speaking, formal Turing proofs do not require infinite length tapes or infinite sets.

 

Obviously, the relevance of the formal Turing machine arises because it defines the limits of "effective calculability", and the class of computable functions (those functions for which an algorithm can be used to compute their values) associated with that notion. [Davis, p.3] Computational complexity seeks to characterize certain qualities or resource-requirements (e.g., of elapsed time) of an algorithm to achieve a result (i.e., to compute some value). Computational complexity is thus primarily concerned with creating a certain taxonomy of all the algorithms which compute some value; that is, of all the algorithms within the universe of algorithms circumscribed entirely by the class of computable functions as determined by the formal Turing machine.

 

(I don't know if there is any interest in computational complexity in a taxonomy of resource requirements for non-computable functions (non-halting algorithms). If so, fine -- that is another universe of functions and algorithms.)

 

Finally, if the formal Turing machine definition still seems problematic, it has also been shown that this same class of functions, (the same limits of effective calculability, and therefore, the same circumscription on the associated universe of algorithms) can be defined equivalently by using Church's l-definability, Herbrand-Godel-Kleene general recursiveness, Post's 1-definability and Post's binormality. [Davis, p.10] Therefore, one need not even invoke the formal Turing machine proof in order to arrive at the same results on the limits of computability, by simply utlizing one of these other criteria instead.

 

Regards,

Tim

 

 

 

 

 -snip- 
What I wonder about is if (or how) formal proofs about Turing-equivalent computability that require infinite sets are related to computational limits based on so-called Computational
Complexity Theory where the concern is with number of steps or length of time to a solution with finite sets that nevertheless can explode exponentially.

Howard