Design Turing Machine

Question

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?

Answer 1

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.