# Halting problem under spatial restrictions

Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine*" and "random-access machine*" respectively), $n \in \mathbb{N}$. $A$ and $B$ are the same type of machine. For any $N \in \mathbb{N}$, statements where $n \leq N$, don't matter.

$n + |d|$ is the number of spatial units on $B$'s tape if $B$ is a Turing machine* or random-access machine*. If it is a C program, $n$ is the number of Bytes in $B$'s read-write memory (registers are neglected, see last sentence of previous pragraph). The memory $d$ takes up is read-only and not accounted for. All spatial units regarded are capable of holding the same amount of information.

$d$ is the argument data. You may assume $n$ to be included in $d$.

If $A$ is a Turing machine* or random-access machine*, it may access $2 \cdot (n + |d|) + c$ spatial units where $c$ is constant.

If $A$ is a C program, it may access $n + c$ Byte of read-write memory. The memory $d$ takes up is read-only and not accounted for. It may have a function which for any $p, k \in \mathbb{N}, B \in \{\text{C program}\}, d$ returns the $k$th Byte of $B(n, d)$'s memory after $p$ steps.

For any of the situations $B \in \{\text{Turing machine*}, \text{random-access machine*}, \text{C program}\}$: Is there an $A$ which decides whether $B(n, d)$ will halt?

I care about the reasons as to why this is the case. Unfortunately, I forgot a lot of what I learned about computability. I'm sorry if this is super trivial or unknown.

• Can you clarify whether $n$ is a parameter of the programs or of the machines? I mean, can the programmer of $A$ and $B$ assume to know the size of the memory of the machine? – danieleds Jun 6 '17 at 7:02
• @danieleds $n$ is a parameter of the machines. The programmer of the machines doesn't know $n$ when programming. But you can assume to be able to read $n$ at runtime. $n$ then is part of $d$. – UTF-8 Jun 6 '17 at 10:52

$A(n,B,d)$ can decide whether $B(n,d)$ will halt.
Note the fact that $B$'s writable memory is limited to $n$ units. This means that the number of possible states of $B$ is just $2^n$ (each possible memory configuration that $B$ may assume). Note also that $B$ halts iff it never goes back to a previously visited state, otherwise it would loop. This means that, if $B$ halts, it cannot do more than $2^n-1$ state transitions (as each state is visited only once).
Thus we can exploit the $2 \cdot n + c$ writable memory units of $A$ to build a machine which simulates B and counts the number of states it visits. We can do that by keeping the memory of $B$ in the first $n$ units, and a state counter $\gamma$ in some other $n+1$ units. We increment $\gamma$ at each state transition of $B$.
If $B$ halts, sooner or later the simulation of $B$ will reach a "HALT" instruction, and then we know $B$ halts. If $B$ does not halt, $\gamma$ will increase forever: as soon as $\gamma = 2^n$, we know that $B$ does not halt.