Is there a way of combining two turing machines without introducing an extra state (I don't want to increase or decrease the total number of states)? Don't worry about an accept or a reject state since they are not that important; I just want a TM to do some computation starting from a blank tape, and I want the result of that computation (some tape contents) to be used by the next TM right after the first machine halts (i.e output redirection)

The only solution I can think of (without introducing a new state) is that I combine the halt state of first machine and the initial state of the second machine into one state, but I am decreasing the total number of states by 1.

  • $\begingroup$ what transitions are you allowing? a do nothing state transition is allowed for some definition of turing machine $\endgroup$ – ratchet freak Nov 29 '17 at 9:30
  • $\begingroup$ Just a normal turing machine.Read/write tape symbol and move the head left or right. $\endgroup$ – Ted Nov 29 '17 at 9:36

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.