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.
closed as off-topic by Andy Putman, Qiaochu Yuan, Kevin Ventullo, David White, Mark Sapir Sep 26 '13 at 11:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andy Putman, Qiaochu Yuan, Kevin Ventullo, David White, Mark Sapir
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.
I am not sure if I understand completely your question but let me give some sort of a crack at it. An instantaneous description of a Turing machine is a string like $xqy$ where $x,y$ are words in the tape alphabet and the head is in state $q$ and pointing at the first letter of $y$. Now I am not completely sure I understood your cylinder thing, so perhaps we should view these as circular words (cyclic conjugacy classes of words) since the tape can rotate around.
In any event, there is some uniform bound $N$ on the number of instantaneous configurations. If the tape alphabet together with set of states has size $m$, this means there are at most $m^N$ configurations. If you ever see a loop it will not halt and a loop must occur within $m^N$ steps, so basically you can enumerate in space of size $N$ and time at most $m^N$ all the possible configurations reachable from an initial configuration. Since you have only one bounded tape, I am assuming that you have only finitely many initial configurations and hence the whole thing is decidable in space $N$ and time $m^N$.
The standard way space complexity works is you have an input tape which holds the input and a work tape. The amount of cells you are allowed to use on the work tape is bounded in terms of the length n of the input by some function $f(n)$. Then one can talk about logspace, linear space, polynomial space, etc.