The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps before nontermination is determined.
Now let us give each cell an exponent: It stores how often the symbol in the cell is to be repeated, i.e. we use a run-length encoding. The machine then works on this tape under preservation of the exponent.
The number of distinct values is still limited to $k$, but the effective tape length is no longer bounded. I'm fairly certain this class of Turing machines suffers from the Halting problem just like regular, unbounded machines do, but I'm looking for a concise proof.
$k$ can be assumed to be $\geq 7$.
Starting in configuration $x^3$ A $y^2$ $z^5$ with $\delta(A,y) = w,right,A$ and $\delta(A,z) = v,left,B$, execution will be:
- $x^3$ A $y^2$ $z^5$
- $x^3$ $w^1$ A $y^1$ $z^5$
- $x^3$ $w^2$ A $z^5$
- $x^3$ $w^1$ B $w^1$ $v^1$ $z^4$
In this example, the maximum number of cells used so far is 4 (or 5 if the head is seen as a splitting point), seen in the final step. The total effective tape length is $3+2+5=10$, but this number is not limited for our purposes.
Just for curiosity, to make the example machine nonhalting, replace $\delta(A,z) = v,right,A$ and add $\delta(A,\sqcup) = u,right,A$, and the machine will increase the exponent of $u$ indefinitely.