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.
-
2$\begingroup$ Isn't this just a finite state machine? $\endgroup$– Qiaochu YuanCommented Sep 25, 2013 at 18:38
-
2$\begingroup$ Yes, it was pointed out to the OP last time that what he had defined was a finite state machine. $\endgroup$– James CranchCommented Sep 25, 2013 at 18:39
-
$\begingroup$ The problem seems ill-defined to me. How does the machine get an input word to work on? Must it fit on your bounded tape? Depending on the answer to this, one can get an idea as to whether you are talking finite state machines or not. $\endgroup$– Benjamin SteinbergCommented Sep 25, 2013 at 18:53
-
1$\begingroup$ @BenjaminSteinberg: I don't think the OP meant for this to be a useful device for computation. (On the other hand, my computer is actually an SBTM and I find it quite handy!) $\endgroup$– François G. DoraisCommented Sep 25, 2013 at 19:33
-
1$\begingroup$ I don't understand why this was closed. Wondering about the desktop halting problem is perfectly reasonable. $\endgroup$– François G. DoraisCommented Sep 27, 2013 at 20:39
2 Answers
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.
-
$\begingroup$ I more or less wrote the same answer but you finished yours first. I have deleted. $\endgroup$ Commented Sep 25, 2013 at 19:39
-
$\begingroup$ In my answer I pointed out that the space complexity is not so bad. Basically the space you need to check halting is the size $N$ of his tape but of course the time is $m^N$ where $m$ is the number of state+alphabet symbols. $\endgroup$ Commented Sep 25, 2013 at 19:40
-
1$\begingroup$ @BenjaminSteinberg: The reason I finished quicker is that I didn't include that (potentially useful) extra information. I think that in the old days we didn't delete concurrent answers exactly for that reason. $\endgroup$ Commented Sep 25, 2013 at 19:43
-
$\begingroup$ oh well maybe I should add that to my answer on meta as to why it is harder to get rep than it used to be :) $\endgroup$ Commented Sep 25, 2013 at 19:44
-
$\begingroup$ Thanks for a very complete answer and the many illuminating comments. I can see why my post might deserve to be closed out. SBTM's interest me because they show clearly that if you want to generate non-periodic infinite sequences of symbols such as all the decimal digits of the square root of 2, it is not sufficient to have an infinite amount of time in which to operate. You also need an infinite memory capacity-which seems to mean an infinite amount of space. $\endgroup$ Commented Sep 27, 2013 at 19:48
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.
-
1$\begingroup$ I undeleted my answer based on Francois's comment. Maybe it contains info interesting to the OP. $\endgroup$ Commented Sep 25, 2013 at 19:45