4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ It should be simple to prove equivalence, any state that moves right past the boundary just needs to add a position, same for left. Therefore it is effectively bi-infinite $\endgroup$
    – ruler501
    May 3, 2015 at 21:57
  • $\begingroup$ This question is related: cs.stackexchange.com/questions/42013/… $\endgroup$
    – André Souza Lemos
    May 3, 2015 at 22:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    May 3, 2015 at 23:14
  • $\begingroup$ @HendrikJan I was aware of the closeness. And I guess that is enough to study complexity issues, which is what people are usually interested in. Still, I was hoping it would have a name of it own. $\endgroup$
    – babou
    May 3, 2015 at 23:23
  • 1
    $\begingroup$ Don't listen to this popular myth about TMs that this physicist told you! TMs are every bit as finite as finite state machines. They do not contain a tape. They do operate on a tape, but it is external to the TM. It doesn't need to be infinite, either. $\endgroup$
    – reinierpost
    May 6, 2015 at 12:59

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is indeed nearly the same as two-stack automaton. I was looking for something more intuitive to use for pedagogical purposes, and my impression is that the splicing-TM is a bit more intuitive (at least for beginners) than the two-stack automaton. Hence I was hoping it might have a name. But you give a good reason why it probably does not. I saw the finite/infinite tape issue as a bonus to do away with some useless disputes, whether meaningful or not (not meaningful imho). $\endgroup$
    – babou
    May 8, 2015 at 9:46
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks David. I was wondering whether it has a name. @HendrikJan is apparently not hopeful given the closeness to a 2-stack automaton. $\endgroup$
    – babou
    May 3, 2015 at 23:27
1
$\begingroup$

Turing machines are not supposed to be "realistic" in a physical (concrete) sense. That said, to say that the tape is infinite is obviously not precise. The tape is better thought of as being unlimited, or "growing" in size as needed, which makes it essentially identical to what you propose, at least in what it can compute.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ What you write is more a comment than an answer to my question. I am not disputing your view, but my question is whether the TM model I suggest has been considered, where and under what name. $\endgroup$
    – babou
    May 3, 2015 at 21:17
  • $\begingroup$ I thought of posting it as a comment, but I considered that this is the only possible answer to your question (without delving deeper into philosophical considerations). The alternative would be to vote it down. $\endgroup$
    – André Souza Lemos
    May 3, 2015 at 21:22
  • 1
    $\begingroup$ Well, my remark on the physicist is more a side remark of debatable interest. Its point was not whether TM are realistic, but the fact that someone was using that as an argument. As I said, my suggested model was not motivated by that. And my question is clearly whether this model was considered before (I did add some emphasis, as you seem to feel it was not clear enough). What reason do you have to think it has no answer, or even that it requires philosophical consideration. I am only asking for factual references. $\endgroup$
    – babou
    May 3, 2015 at 22:07
  • $\begingroup$ If you are interested in what the insertion of cells can change in the complexity of solutions, I'm fine. You may find research on that. Considering only computability issues (which is what your question seems to be about), what you propose is just a Turing machine. You can't find factual reference for a bird that quacks like a duck, walks like a duck, has duck's feathers, and yet is claimed to not be a duck. $\endgroup$
    – André Souza Lemos
    May 3, 2015 at 22:20
  • $\begingroup$ Actually, I am after a pedagogical tool to explain something that is not about TMs. But since you mention it, I did wonder how much it can change the complexity of some problems ... though it is not my main interest. I am aware that it is essentially a TM ... that is why I said I had attempted no proof, adding a smiley in the end. Communication is always hard. $\endgroup$
    – babou
    May 3, 2015 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.