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

Question

$ \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.?

Answer 1

For your question in last paragraph, it seems that the answer should be yes for several reasonable models of computation. That is, we should be able to distinguish between "bounded" and "unbounded" cases, generally speaking. However, I don't know the generic answer to this.

For example, if we have a machine based model, then we talk about the "length of tape being used". If we have a program based model (which uses a finite number of variables, which can take value of any natural number), then we can define "the maximum value that any variable can take (at any time), among all the ones used in the program". So, for a given run of a program (with a given input), if the variable values have some fixed upper-bound, then we can say that "the given run of the program is bounded".

Now one thing which we can observe is that if the run of a program corresponding to every input value is bounded, then the set representing the input values where the function loops forever is computable. The looping for any given run of the program is easy to check. One has to check the given run for a repetition in snapshots. If some snapshot repeats itself, then the program loops (otherwise the program will halt anyway).

As an example of what is meant by snapshot, suppose the function $x \mapsto x^3$ represented a computable upperbound on the maximum value of the variables (as a function of input). In particular, if the input value was $10$ then we know that the maximum value that any variable can take is less than or equal to $1000$. Specifically, assume that given program was of length $20$ (mark the line numbers from $1$ to $20$) and the program used $5$ variables. Now we can note that all the "snapshots" (the $(\mathrm{line \,\, number},\mathrm{variable\,\,vector})$ pair) that can be used in the given run are already known in advanced. In this specific case, all the possible snapshots can be written as $(s,v_0,v_1,v_2,v_3,v_4)$, where $1 \le s \le 20$ and $0 \le v_{0,1,2,3} \le 1000$.

Now consider the set $A$, such that a given element $<p,i>$ belongs to $A$ iff (i) the run corresponding to the program with index $p$ on input $i$ is bounded (ii) the program loops forever on the given run. Now it can be shown with similar logic, that the set $A$ is recursively enumerable. All we have to do is to simulate the program with index $p$ for input $i$. We check whether program enters into a "snapshot loop" for the given run or not. If it does, then the run is bounded for the given input (and the program also loops for the given run).

The next question to ask is whether $A$ is recursive or not. The answer is no because the halt set $H$ is computationally reducible to $A$. For this, suppose that we are given $x=<p,i>$ as input and we have to determine whether $x \in H$ is true or not. We want to transform the program $P$ (with index $p$) into another program $Q$ (with index $q$) such that we have $p=f(q)$ (where $f$ is a computable function). The program $Q$ simply simulates the behaviour of program $P$, for the same input. If $P$ loops for the given input $i$, then $Q$ also loops for the same input. If $Q$ discovers that $P$ halts for the given input $i$, then towards the end instead of halting it enters into a "snapshot loop" (via an artificial construction). Now to check whether $<p,i> \, \in H$, we first check whether $<q,i>\,=\,<f(p),i> \, \in A$ is true or false. If $<q,i>\, \notin A$ (since that implies that the run of $P$ on input $i$ is not bounded) then $<p,i> \, \notin H$. If $<q,i> \, \in A$ then we simply check whether the program $P$ halts on input $i$ or whether it enters into a snapshot loop. If the former is true then answer $<p,i> \, \in H$ and if the latter is true then answer $<p,i> \, \notin H$.

---

Finally for the question you asked, suppose we have a partial recursive function $g:\mathbb{N} \rightarrow \{0,1\}$. Now suppose that there is some program $P$ (with index $p$) which computes $g$. We define a new function $g_p:\mathbb{N} \rightarrow \{0,1,2,3\}$ such that $g_p(x)=g(x)$ whenever $P$ halts. When $P$ loops, then $g_p(x)=2$ if the run of $P$ for given input is bounded. When $P$ loops, then $g_p(x)=3$ if the run of $P$ for given input is not bounded.

When the image-set of $g_p$ doesn't contain the element $3$, then $g_p$ will always be a computable function.

Edit: Improved the wording/structure.

Answer 2

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