Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures.

This form of TM contains some specific features related to the considered structures and specific rules of its instruction applying.

Obviously any TM of my form can be transformed to the conventional classical Turing Machine (and vice-versa), as my structures can be represented as flat strings. But my form is more convenient to deal with this structures and I have implemented visualisation software which emulates this process.

My question is: is any sense of publishing a paper describing this type of machine or it is just multiplying entities beyond necessity?

  • $\begingroup$ I think it's hard to answer this question without more details. Counter machines have been useful in proving undecidability results. On the other hand, often we avoid the low-level details of Turing machine implementations in research papers, especially in complexity theory and algorithms papers, and assume the reader can fill them in. In these cases, a slightly streamlined low-level computational model is not terribly useful. $\endgroup$ – Sasho Nikolov Jul 9 '17 at 17:00
  • $\begingroup$ Such a model will be interesting if there is something non-trivial you can say about it, say you have a lower bound on the computational complexity of some problem. Otherwise it is probably not so interesting from the point of view of Theory of Computation. $\endgroup$ – Yuval Filmus Jul 11 '17 at 14:31
  • $\begingroup$ Thank you @YuvalFilmus, but what about automata-theory? What if this model is much more illustrative regarding language recognition (of the considered structures)? $\endgroup$ – Andrey Lebedev Jul 11 '17 at 14:33
  • $\begingroup$ Automata theory is concerned with models weaker than Turing machines. Your models seem to be as strong as Turing machines. $\endgroup$ – Yuval Filmus Jul 11 '17 at 14:34
  • $\begingroup$ @YuvalFilmus, do you mean that we can not consider the Turing machine in Automata theory as automata per se, which accepts some language? $\endgroup$ – Andrey Lebedev Jul 11 '17 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.