Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$

Could someone give me clarification on how to approach and step through the design of this Turing Machine?

  • $\begingroup$ This heavily depends on how your text defines Turing machines. All definitions are ultimately equivalent, but the specific notation and form of the definitions can be quite different. $\endgroup$ – Thomas Andrews Nov 5 '15 at 0:13
  • $\begingroup$ But my approach would be to swap the $0$s and $1$s until all $0$s come before all $1$s. Then, at the border between $0$s and $1$s, delete $011$, until there is no $011$ left. If there are any digits left at that point - $0$s or $1$s - you reject, otherwise, accept. $\endgroup$ – Thomas Andrews Nov 5 '15 at 0:15
  • $\begingroup$ I am planning on defining a seven-tuple formatted Turing Machine, if that helps. This problem is based off of Sipser. @ThomasAndrews $\endgroup$ – DavidN Nov 5 '15 at 0:16
  • $\begingroup$ Presumably $\#(0,x)$ means the number of digits in $x$ that are $0$? $\endgroup$ – Thomas Andrews Nov 5 '15 at 0:17
  • $\begingroup$ From my interpretation, this states that there are Twice as many 0's as 1's. $\endgroup$ – DavidN Nov 5 '15 at 0:18

Since you asked for clarification on how to approach the design of the Turing machine, I'm not going to solve the problem, but just present a design process that I use. I am also not completely sure what that notation is trying to get across, whether it is strings of the form 001, 000011, etc, or strings of the form #(0000,11). As these are only different in formatting, I will present based upon the latter, and formatting the same algorithm to look like the former should be trivial.

I'm going to assume that the format of the Turing Machine will be a table with states on the left and input symbols on the top, as shown below. If a value is just 'A' or 'R', then 'A' will be shorthand for "accept", and 'R' is shorthand for "reject". Otherwise, a valid table value consists of three characters: moving left or right (L/R), the next state you are going to, and the symbol to write down in the current location. $$\begin{array}{c|c|c|c|c|} & \text{0} & \text{1} & \text{#} & \text{,} & \text{(} & \text{)} \\ \hline \text{q0} & & \\ \hline \text{q1} & & \\ \hline \end{array}$$

Your first step is to identify your desired algorithm, or objective. In this case, perhaps you could overwrite two 0's for every 1 read, and reject if you run out of zeroes prematurely or have an excess.

You should then break down this algorithm into insanely trivial steps. What is the first step? Move to the '1' section. So, we can make our first state do nothing but move until the section after the ',', as this is where the '1's state will begin. This state could look like the following:

$$\begin{array}{c|c|c|c|c|} & \text{0} & \text{1} & \text{#} & \text{,} & \text{(} & \text{)} \\ \hline \text{q0} & \text{R00} & \text{R} & \text{R0#} &\text{R1,} & \text{R0(} & \text{R} \\ \hline \text{q1} & & & & & \\ \hline \end{array}$$

As you can see, we move to state q1 when the a value of ',' is read by state 'q0'. You then need to break the algorithm down into the next insanely small step, and that will be the operation of state 'q1'. In this case, perhaps that would be reading a '1' and then moving to another state that moves all the way to the left. Then, another state that overwrites two zeroes, etc.

So, as far as approaching the design of the Turing Machine, you should first decide on your overall algorithm. You should then build your first state, and see what logically follows as the next state.

I can flesh out the full construction of the Turing Machine if that is deemed necessary by the community.


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.