The main question asked me to build a certain turing machine such that given a word w over {0,1}* the turing machine accepts all such words and ends in accept state with the tape string = the word apended with the number of zeros in it. I built the state diagram of this turing machine..

But now there is a question next to it which say something like -

  1. What is the function the machine you build computes ??

I dont understand what this means ?? What i can think of is that the function the question talks about is the transition function... and that just copies 0's from w to the end of it... it doesnt computes as such anything..

Any lights on the above ??


  • 2
    $\begingroup$ I didn't understand your description of the behavior of the machine. Is it that it starts with a word $w\in\{0,1\}^*$ and ends with $w$ followed with as many zeros as zeros are in $w$? If that is the case, you could say that the machine is computing the function $w\mapsto w0^{z(w)}$, where $z(w)$ is the number of zeros of $w$. $\endgroup$ – plop Aug 24 at 16:25
  • $\begingroup$ yes i think you got it correct. example if w = 0110010 then turing machine ends in accept state with this written on the tap = 01100100000 .. so at the end it just appends 0's with count same as that in w $\endgroup$ – rohit sharma Aug 24 at 18:04

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.