<p>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.</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2017-07-09T17:00:06.050Z
I think it's hard to answer this question without more details. [Counter machines](https://en.wikipedia.org/wiki/Counter_machine) 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.
Sasho Nikolov
CC BY-SA 3.0
2017-07-11T14:31:01.827Z
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.
Yuval Filmus
CC BY-SA 3.0
2017-07-11T14:33:19.423Z
Thank you @YuvalFilmus, but what about `automata-theory`? What if this model is much more illustrative regarding language recognition (of the considered structures)?
Andrey Lebedev
CC BY-SA 3.0
2017-07-11T14:34:05.220Z
Automata theory is concerned with models *weaker* than Turing machines. Your models seem to be as strong as Turing machines.
Yuval Filmus
CC BY-SA 3.0
2017-07-11T14:39:55.397Z
@YuvalFilmus, do you mean that we can not consider the Turing machine in Automata theory as *automata* per se, which accepts some language?
Andrey Lebedev
CC BY-SA 3.0
2017-07-11T15:01:46.350Z
You can, but this is different that the connotation the term "automata theory" has for me. The area also considers languages of infinite words and finite or infinite trees, but the more elementary parts seem to be about models which are weaker than Turing machines.
Yuval Filmus
CC BY-SA 3.0
2017-07-11T15:03:23.250Z
A different reason to consider a model is if it is more realistic. For example, RAM machines are more realistic than Turing machines, even though the difference is only polynomial. In that case you'll have to argue why your model is better (has running time which is a better model of reality).
Yuval Filmus
CC BY-SA 3.0
2017-07-11T15:04:00.493Z
@YuvalFilmus yes, I agree. But when we are talking about unrestricted grammars and recursively enumerated languages as an abstract machine we *have* to use TM.
Andrey Lebedev
CC BY-SA 3.0
2018-01-02T09:13:07.057Z
I don't know what makes something publish worthy or not.  All I can say is that I would read it!  :)
Michael Wehar
<automata-theory><turing-machines>
Convenient forms of Turing machines
Andrey Lebedev
# Convenient forms of Turing machines

(Asked by: username_0 on 2017-07-08)

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*?

**Tags:** automata-theory, turing-machines

> **Comments:**
> **username_1**: I think it's hard to answer this question without more details. [Counter machines](https://en.wikipedia.org/wiki/Counter_machine) 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.  
> **username_2**: 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.  
> **username_0**: Thank you @YuvalFilmus, but what about `automata-theory`? What if this model is much more illustrative regarding language recognition (of the considered structures)?  
> **username_2**: Automata theory is concerned with models *weaker* than Turing machines. Your models seem to be as strong as Turing machines.  
> **username_0**: @YuvalFilmus, do you mean that we can not consider the Turing machine in Automata theory as *automata* per se, which accepts some language?  
> **username_2**: You can, but this is different that the connotation the term "automata theory" has for me. The area also considers languages of infinite words and finite or infinite trees, but the more elementary parts seem to be about models which are weaker than Turing machines.  
> **username_2**: A different reason to consider a model is if it is more realistic. For example, RAM machines are more realistic than Turing machines, even though the difference is only polynomial. In that case you'll have to argue why your model is better (has running time which is a better model of reality).  
> **username_0**: @YuvalFilmus yes, I agree. But when we are talking about unrestricted grammars and recursively enumerated languages as an abstract machine we *have* to use TM.  
> **username_3**: I don't know what makes something publish worthy or not.  All I can say is that I would read it!  :)  

---

## 0 answers

