patternMinor
Splicing squares on a Turing Machine finite tape
Viewed 0 times
splicingfinitesquarestapemachineturing
Problem
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?
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?
Solution
Yes, it has the same computing power as an ordinary TM.
-
It's a standard exercise in computation theory/complexity theory textbooks that the ability to insert characters into the tape (and delete them from it) can be simulated by a standard Turing machine with a quadratic loss of efficiency. For example, this is Exercise 2.8.8 of Papadimitriou's book (Computational Complexity, Addison Wesley, 1994); he doesn't give a name to this extension of the standard Turing machine or attribute it to anyone which suggests to me that it's folklore – he's pretty good at citing and attributing.
-
Since you can insert characters at will, reaching the end of the initially finite tape makes no difference: you can just use insertion to extend the tape. A halting computation will only need to do this a finite number of times.
The infinite tape of an ordinary TM is just a definitional convenience: it suffices to have a finite tape that gets extended any time the head reaches the end.
-
It's a standard exercise in computation theory/complexity theory textbooks that the ability to insert characters into the tape (and delete them from it) can be simulated by a standard Turing machine with a quadratic loss of efficiency. For example, this is Exercise 2.8.8 of Papadimitriou's book (Computational Complexity, Addison Wesley, 1994); he doesn't give a name to this extension of the standard Turing machine or attribute it to anyone which suggests to me that it's folklore – he's pretty good at citing and attributing.
-
Since you can insert characters at will, reaching the end of the initially finite tape makes no difference: you can just use insertion to extend the tape. A halting computation will only need to do this a finite number of times.
The infinite tape of an ordinary TM is just a definitional convenience: it suffices to have a finite tape that gets extended any time the head reaches the end.
Context
StackExchange Computer Science Q#42105, answer score: 4
Revisions (0)
No revisions yet.