Functions corresponding to Turing machines that might not halt but consume bounded tape

computabilityturing-machines

$ \renewcommand{\N}{\mathbb{N}} $
$ \renewcommand{\def}{\stackrel{def}{=}} $
$ \renewcommand{\symstart}{\text{start}} $
$ \renewcommand{\symhalt}{\text{halt}} $
$ \renewcommand{\boundedLoop}{\text{boundedLoop}} $
$ \renewcommand{\unboundedLoop}{\text{unboundedLoop}} $
Turing machines are usually divided into two groups based on whether they halt or not … and the functions corresponding to Turing machines that never halt for any input are said to be computable. Is there any nice meaning for Turing machines that may potentially loop forever, but definitely consume a bounded amount of tape doing so?

I'm defining a Turing machine as a section of $\N$, $I_n \def \{0, 1, \cdots, n-1\}$, and two directed graphs $\Phi_0, \Phi_1$ over $I_n \cup \{\symstart, \symhalt_0, \symhalt_1\} $ .

For every $v$ in $I_n \cup \{\symstart\}$, the out-degree of $v$ in $\Phi_0$ must be 1. The out-degree of $v$ in $\Phi_1$ must also be 1.

The out-degree of $\symhalt_0$ and $\symhalt_1$ in $\Phi_0$ and $\Phi_1$ is $0$.

The Turing machine runs along a single tape with cells indexed by $\N$ that can each hold a $0$ or a $1$. The Turing machine can accept an input $i$ that is encoded onto the tape in little-endian binary, with an infinite number of trailing zeroes.

Each Turing machine $\Phi$ corresponds to a function $f : \N \to \{0, 1, \infty\}$ based on whether a run of the machine $(\Phi, i)$ calls $\symhalt_0$, calls $\symhalt_1$, or calls neither, respectively.

A computable function $f$ is precisely one which doesn't produce $\infty$ for any input.

Any given run of a Turing machine $(\Phi, i)$ has another interesting property … whether it consumes a finite or infinite amount of tape. I say consumes because I think the definition is equivalent regardless of whether you use observes or modifies as your notion of interacting with a cell on the tape.

In the formalism above, the only way we have of inspecting what a turing machine is doing "from the outside" is whether it halts yielding $0$, halts yielding $1$, or doesn't halt.

But if we expose the machinery of the Turing machine, however, we can ask whether certain runs consume a bounded amount of tape or not and talk about a new type of function:

$$ g : \mathbb{N} \to \{0,1,\boundedLoop,\unboundedLoop\} $$

Is there any kind of meaning associated with the subset of $g$ 's that never return $\unboundedLoop$ for any input?

Furthermore, if we pick another way of representing a computable function, say, based on the untyped lambda calculus, would we be able to inspect the computation/executation of a given program-input pair and meaningfully divide it into "bounded" and "unbounded" cases? Or is the division into "bounded" and "unbounded" cases merely an artifact of the Turing machine construction.?

Best Answer

Firstly, bounded memory use is not an artifact of Turing machine mechanics. You can ask the same question for any Turing-complete programming language, where it corresponds to whether or not the program uses unbounded memory (defined as appropriate) on a run. For example, if the language supports integer and string variables, then bounded memory means that the integer variables have bounded value and the string variables have values with bounded length.

Secondly, a bounded-memory program must on every input either halt or eventually cycle. I doubt there is a nicer characterization. Note that it is not known whether even the following simple non-halting program f uses bounded memory on every positive integer input or not:

def f(n):
  while n>0:
    if n%2==0: n=n*3+1;
    n=n/2;

Also, it is easy to prove that there is no program that can decide whether a given input is a bounded memory program or not. In fact, via a simple generalization of f, one can show that this decision problem is not only undecidable but actually $Π_2$-complete, implying that it cannot be solved even by a program that has access to the halting oracle (see here).

Related Question