1
$\begingroup$

So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either

So my question is :

For every turing machine, what is the minimum number of states that we can have after converting it to this minimal state turing machine?

and what is the properties of this turing machine that we have converted our original turing machine to?is this a standard turing machine or we do this by increasing the number of tapes or...? ( how is this possible?)

What i mean by convert is build a Turing machine which accepts the same language but only with 2 or 3 states

$\endgroup$
  • $\begingroup$ What do you mean by "convert"? Do you mean the TMs before and after this converting accept the same language, or behave the same (accept, reject or loop) on each input? Anyway, I think you are seeking for universal Turing machine. $\endgroup$ – xskxzr Mar 25 '18 at 6:58
  • $\begingroup$ Meaning build a Turing machine which accepts the same language but only with 2 or 3 states, no i'm not talking about UTM, in the book that i'm reading it says for every turing machine we can create another turing machine which is doing the same thing as the previous one but only with 3 states $\endgroup$ – John P Mar 25 '18 at 10:01
3
$\begingroup$

Ariel's answer shows that you cannot fix the number of states if the tape alphabet is constant. There are two ways out:

  • Allow the Turing machine access to a "hint" written on an auxiliary tape. You can then use a universal Turing machine with a fixed number of states, which gets as auxiliary input the description of another Turing machine that it executes.

  • Allow the tape alphabet to be arbitrary. You can then simulate the auxiliary tape, that is, you can design a Turing machine with a fixed number of states that first writes on a tape the description of another Turing machine, and then switches over to a universal Turing machine that executes it.

In the second case, the tape alphabet is still finite, but its size depends on the machine. This allows us to use a bina fide Turing machine with a fixed number of states but with an unbounded description length, thus bypassing the limitation presented in Ariel's answer.

Whether you can do it with N states could depend on the exact semantics of your Turing machine, but in both cases you should be able to make do with some constant N.

$\endgroup$
  • $\begingroup$ So is this statement true ? : " We can convert any given turing machine to a standard turing machine with only 6 states, we can also reduce this number to 3" assuming the last part means there is no limit on which version of turing machine we use and how many tapes we have and etc, and if it is true, is 3 the minimum number? $\endgroup$ – John P Mar 25 '18 at 12:06
  • $\begingroup$ I have no opinion on the minimum value of N. It may depend on your exact definition of Turing machines. $\endgroup$ – Yuval Filmus Mar 25 '18 at 12:35
3
$\begingroup$

You can't always find an equivalent Turing machine (in the sense that it has the same language) having less than $N$ states.

Note that the semantics of a Turing machine is determined by its states and transition function. After fixing the alphabet, to fully describe a machine you only need to specify how it reacts to every symbol from every state. This description has length of $O(|Q|\log |Q|)$. Thus, if you bound the number of states by some constant $N$, then there's only a finite number of different machines ($\sim N^N)$, which means that not every decidable language has an equivalent machine in this set.

$\endgroup$
  • $\begingroup$ Strictly speaking, you're obviously not wrong, but there exist very small universal machines, I feel that's what the original post was about. $\endgroup$ – quicksort Mar 25 '18 at 8:57
  • $\begingroup$ Well, according to the comments by OP, it seems that he is not talking about UTMs (who indeed can be made small). $\endgroup$ – Ariel Mar 25 '18 at 10:44
  • $\begingroup$ @ariel Ok i found the side note in the book, its this : "We can convert any given turing machine to a standard turing machine with only 6 states, we can also reduce this number to 3" i guess the last part means using multiple tape or something, so is this a false statement? the book is a translation of peter linz automata book and this was a side note, not sure if this is in the linz book as well or not. $\endgroup$ – John P Mar 25 '18 at 11:12

Your Answer

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

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