3 ms·
There are many ways to define Turing Machines: * only binary alphabet, or allow any finite alphabet on the tape(s) * tape is infinite in a single direction or
by progval 7y ago
There are many ways to define Turing Machines:
* only binary alphabet, or allow any finite alphabet on the tape(s)
* tape is infinite in a single direction or in both (and various possibilities as to how to handle reaching the edge)
* there is one tape or there are more
* the head has to move every time, or can it remain on the same cell
* etc.
And they are all equivalent in terms of computability (ie. they can compute the same functions), and mostly equivalent in terms of algorithmic complexity (ie. they take the same time to run, up to a polynomial).
So almost no one bothers actually saying which model they use, unless they are doing a rigorous proof.
However, when papers like this one say "Hey, let's take my favorite model of Turing Machines and restrict it so that [X]", then the results highly depends on what their favorite model is. Except they don't always bother saying which one it is.
For example, if you restrict yourself to Turing Machines with a single state, two tapes, and any alphabet allowed on at least one of the tapes, then it's enough to emulate any one-tape Turing machine, simply by writing the state on a single cell of the second tape and repeatedly read it. Which in turn are known to be able to emulate any conventional model of Turing Machines.
- daveFNbuck 7y agoLooking at the first page of the linked PDF, it's not explicit about whether the alphabet must be finite, although it's implied by the summary saying that addition can only be done modulo some finite value. It is explicit about having an arbitrary alphabet, a single tape that's infinite in both directions and that the head has to move every time. I don't think I've ever seen anyone restrict a Turing machine in a novel way and not follow that up with a rigorous proof.