Let $p(n)$ be the productivity of the most productive $n$-state machine, where the productivity $f$ of a TM is defined to be the length of the $*$-string if the TM halts in standard position and 0 otherwise.

I'm trying to prove: $$ \forall n [p(n+11) \geq 2n ] $$

Presumably I have to construct an $n$-state turing machine that produces a string of $n$ $*$-symbols. But I'm not totally sure how to do this, or how to proceed.

  • $\begingroup$ It seems like you need to add 11 states to double the number of *'s. So:can you write an 11-state Turing-machine that doubles the number of *'s on the tape? And from your earlier question, I understand it has to be a quadruple machine, right? $\endgroup$ – Bram28 Mar 4 '17 at 3:39
  • 1
    $\begingroup$ P.s. Just noticed you have never accepted any of the answers to your questions ... This does not exactly inspire members of the community to answer your questions ... Maybe you didn't realize that there is such a thing: you can click the check mark next to an answer to accept it ... Assuming it answers your question to your satisfaction of course. $\endgroup$ – Bram28 Mar 4 '17 at 3:41

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.