Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The idea is that the TM uses a "linked list" rather than a tape, so that the head can splice a new symbol position between two existing ones (one could also think of removing some, but I had no use for it :). Of course, that requires having a new item in the description of a transition to specify whether a new square should be spliced in, on the left or on the right of the head (both are needed).
The final point is that it does start with a finite tape. I did not give all the details, but I do not think the rest matters much.
I have not done any proof, but I conjecture its computing power is that of usual TM :) .
As I said I thought of it as a convenient way of explaining some other problem. Then it hit me that, while TM are finitely defined, they are stuck with their infinite tape from the very beginning. It never bothered me very much, until some physicist started explaining that TM are not realistic because of their infinite tape (which I only saw as a convenient mathematical shorthand). I could fight that technically in various ways. But this splicing idea should just do away with such silly objections using no mathematics at all.
So my question is: where has this model, or some similar one, been considered before, by whom and under what name?
Asked By : babou
Answered By : Hendrik Jan
It seems just too close to a two-stack automaton to be studied separately. The two stacks can be seen as two parts of your linked list (before and after the position of the reading head). Pushing a new symbol is the equivalent of your splicing a tape cell.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42105
0 comments:
Post a Comment
Let us know your responses and feedback