How can I design a turing machine that recognises this language? 01^n01^n0

Question

I keep on struggling with how to actually capture the number of 0's .

Do I use a different marker to capture 0 and 1? Or do I need to create new states that count the number of 0's? This doesn't seem particuarly elegant to me, but I don't see anyway to count exactly 3 0's. Also when I back track to recount the number of 1's, how do I know when I reach the start?

Answer 1

Do I use a different marker to capture 0 and 1?

No need for different markers. You can erase 1s by replacing them by 0s in a controlled way.

Or do I need to create new states that count the number of 0's?

Yes.

This doesn't seem particularly elegant to me

That is a matter of opinion, but using different states is the way to go.

Also when I back track to recount the number of 1's

You don't actually count the number of 1's. Instead you pair each 1 in the left half with another 1 in the right half.

...how do I know when I reach the start?

In the very first state you'll have asserted that the first character was a 0, so now when backtracking you know you'll have reached the start when you encounter a (third) zero. Again, you'd use different states on your way back to keep track of which zero you have already encountered.

You could solve this in two phases:

1. Check whether the input has exactly three 0's, assuming the input is followed by a blank (not part of the input)

2. Go back and forth over the tape and each time replace the outermost 1 by a 0 until there are no more 1s that can be paired that way. In that case you can conclude whether the original had the desired pattern.

First phase:

current state	symbol read	symbol to write	head moves to	new state
start	0	copy	right	toSecond0
start	1,blank	copy	right	reject
toSecond0	0	copy	right	toThird0
toSecond0	1	copy	right	toSecond0
toSecond0	blank	copy	right	reject
toThird0	0	copy	right	assertBlank
toThird0	1	copy	right	toThird0
toThird0	blank	copy	right	reject
assertBlank	blank	copy	left	atThird0
assertBlank	0,1	copy	left	reject

Second phase starts at state atThird0 with the head on the final zero.

current state	symbol read	symbol to write	head moves to	new state
atThird0	0	copy	left	wipeToLeft
wipeToLeft	0	copy	left	assert0
wipeToLeft	1	0	left	toCenterLeft
assert0	0	copy	left	accept
assert0	1	copy	left	reject
toCenterLeft	0	copy	left	toStart
toCenterLeft	1	copy	left	toCenterLeft
toStart	0	copy	right	wipeToRight
toStart	1	copy	left	toStart
wipeToRight	0	copy	right	reject
wipeToRight	1	0	right	toCenterRight
toCenterRight	0	copy	right	toEnd
toCenterRight	1	copy	right	toCenterRight
toEnd	0	copy	right	wipeToLeft
toEnd	1	copy	right	toEnd

Here is an implementation of a Turing machine in JavaScript, and it is run with the above transition table. You can play with the input to see what you get:

createTuring({
  transitions: [
    { state: "start"         , read: "0"             , move: "R", nextState: "toSecond0" },
    { state: "start"         , read: "1_"            , move: "R", nextState: "reject" },
    { state: "toSecond0"     , read: "0"             , move: "R", nextState: "toThird0" },
    { state: "toSecond0"     , read: "1"             , move: "R", nextState: "toSecond0" },
    { state: "toSecond0"     , read: "_"             , move: "R", nextState: "reject" },
    { state: "toThird0"      , read: "0"             , move: "R", nextState: "assertBlank" }, 
    { state: "toThird0"      , read: "1"             , move: "R", nextState: "toThird0" },
    { state: "toThird0"      , read: "_"             , move: "R", nextState: "reject" },
    { state: "assertBlank"   , read: "_"             , move: "L", nextState: "atThird0" },
    { state: "assertBlank"   , read: "01"            , move: "L", nextState: "reject" },
    { state: "atThird0"      , read: "0"             , move: "L", nextState: "wipeToLeft" },
    { state: "wipeToLeft"    , read: "0"             , move: "L", nextState: "assert0" },
    { state: "wipeToLeft"    , read: "1", write: "0" , move: "L", nextState: "toCenterLeft" },
    { state: "assert0"       , read: "0"             , move: "L", nextState: "accept" },
    { state: "assert0"       , read: "1"             , move: "L", nextState: "reject" }, 
    { state: "toCenterLeft"  , read: "0"             , move: "L", nextState: "toStart" },
    { state: "toCenterLeft"  , read: "1"             , move: "L", nextState: "toCenterLeft" },
    { state: "toStart"       , read: "0"             , move: "R", nextState: "wipeToRight" },
    { state: "toStart"       , read: "1"             , move: "L", nextState: "toStart" },
    { state: "wipeToRight"   , read: "0"             , move: "R", nextState: "reject" },
    { state: "wipeToRight"   , read: "1", write: "0" , move: "R", nextState: "toCenterRight" },
    { state: "toCenterRight" , read: "0"             , move: "R", nextState: "toEnd" },
    { state: "toCenterRight" , read: "1"             , move: "R", nextState: "toCenterRight" },
    { state: "toEnd"         , read: "0"             , move: "L", nextState: "wipeToLeft" },
    { state: "toEnd"         , read: "1"             , move: "R", nextState: "toEnd" }
  ],
  initState: "start",
  tape: "01111011110",
});

<script src="https://trincot.github.io/turing.js"></script>