My previous post about this topic (deleted question No. 142986) was quite long and somehow, most of it got erased. I will try to summarize it. I would like to consider a type of Turing machine which I will call "space bounded" and refer to as an SBTM. Instead of a one-way or a two-way infinite tape, an SBTM has a finite tape wrapped around a cylinder or wheel that is always free to rotate in either direction. What would be "shifts to the right" or "shifts to the left" in a regular Turing machine are small "counterclockwise" or "clockwise" rotations of the SBTM's cylinder or wheel. The actual number of "cells" on the tape, that contain the symbols used by the machine-although finite-can be aslarge as one pleases (depending on the size of the cylinder or wheel). An SBTM can be provided with the same (finite) set of symbols, the same (finite) set of states and the same (finite) table of instructions as any regular Turing machine. Therefore an SBTM can halt or it can continue to execute instructions forever, because- just like a regular Turing machine-it is assumed to have available an infinite amount of time in which to operate. My FIRST QUESTION is: Is the Halting Problem solvable for SBTM's?--------It seems pretty clear to me (although I could possibly be mistaken) that if the SBTM does not halt, its restricted memory capacity will cause any infinite sequence of symbols that it generates to become ultimately preiodic. If I am right then my SECOND QUESTION is: Are the periods of these (infinite) sequences and the number of instructions that must be executed until just before the start of the first period, recursive functions of the parameters used to specify the (operations of the) SBTM?---------Among these parameters, of course, should be the initial (finite) sequence of symbols on the SBTM's tape.



A couple of questions about Turing machines that are bounded in space but have an infinite amount of time in which to operate
An SBTM has only finitely many possible combinations of internal state and tape configuration. Moreover, the next internal state and tape configuration is completely determined by the current internal state and tape configuration (regardless of prior history). Therefore, if the machine ever repeats an internal state and tape configuration then it will keep looping forever and never halt. Conversely, a machine that never halts must eventually repeat an internal state and tape configuration.


To summarize, there are two option given an initial tape configuration and initial state:


* The machine might reach a stage $s$ where it halts.
* The machine might reach a stage $s$ where it repeats an earlier configuration, in which case it will never halt.


Both of these are $\Sigma^0\_1$ statements and therefore the halting problem is decidable.


In fact we know more. Knowing the total number $K$ of possible internal state and tape configuration, the machine must halt in at most $K$ steps or else it will repeat a configuration and never halt.


