1
$\begingroup$

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|

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.