So in a book that I'm reading it says that we can convert any given Turing machine to a standard turing machine with only 6 states

furthermore we can convert any given to a turing machine with only 3 states given we have no limitation on which version of turing machine we use(multi tape, non deterministic, etc so its not a standard turing machine anymore) and obviously both the original turing machine and the converted one have the same functionality(accept the same language)

i asked this here before but no one was able to give a proof of this, and i do not understand it either

so what's this statement based on? i tried searching the web but there was literally 0 article about this.

I think this is done the same way we can reduce any PDA to a PDA with only 3 states, but i dont know the prove of that one either, i just know its true

  • 1
    $\begingroup$ I asked this here before. You should include a link to your earlier question. $\endgroup$ – Yuval Filmus Apr 14 '18 at 19:15
  • 1
    $\begingroup$ Here is the earlier question: cs.stackexchange.com/questions/89765/…. $\endgroup$ – Yuval Filmus Apr 14 '18 at 20:34
  • $\begingroup$ See also cs.stackexchange.com/questions/43517/…. $\endgroup$ – Yuval Filmus Apr 14 '18 at 20:35
  • $\begingroup$ What's the difference from the old question? $\endgroup$ – xskxzr Apr 15 '18 at 3:06
  • $\begingroup$ @xskxzr in the old one i said 2 states but that was not right, the correct minimum is 3, and i have not found the prove yet ( but i think reducing the number of states is done the same way that we can reduce any given PDA to a PDA with only 2 states, but i dont know the prove of that one either) all of these are side notes in the book without any prove $\endgroup$ – John P Apr 15 '18 at 3: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.