# Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}

I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |u| = 2|v|

## 1 Answer

One possible solution running in linear time:

1) Move head of the first tape to the right until you reach end of $u$ while copying each symbol of $u$ to the second tape. But first write a blank symbol on the second tape as the first symbol.

2) Read $v$ by two symbols and for each pair of symbol of $v$ erase one symbol of $u$ on the second tape (starting from the last symbol and moving backward).

3.1) If all symbols (of $u$) on the second tape has been erased then check if the first head has reached end of the string (of $v$). If "no" then REJECT else ACCEPT.

3.2) If the TM has reached end of the string of $v$ (on the first tape) then check if the second tape is empty. If "yes" then ACCEPT else REJECT.