Вот решение грубой силы для односторонней одноленточной машины Тьюринга: для каждого i отметьте символ i в W1 и посмотрите, будет ли W1 [i… | W2 | + i] = W2 [1… | W2 |].
Чтобы проверить, отскок назад и вперед между W1 и W2, отмечая соответствующие символы, пока они совпадают, и сбрасывая их, если вы обнаружите расхождение.
Обработка вслучай несоответствия может выглядеть следующим образом:
abc#abd Xbc#abd Xbc#abd Xbc#abd Xbc#abd Xbc#Abd
^ ^ ^ ^ ^ ^
mark scan scan scan scan mark'
Xbc#Abd Xbc#Abd Xbc#Abd Xbc#Abd XBc#Abd XBc#Abd
^ ^ ^ ^ ^ ^
scan' scan' scan' bounce mark' scan
XBc#Abd XBc#Abd XBc#ABd XBc#ABd XBc#ABd XBc#ABd
^ ^ ^ ^ ^ ^
scan scan mark' scan' scan' scan'
XBc#ABd XBC#ABd XBC#ABd XBC#ABd XBC#ABd XBC#ABd
^ ^ ^ ^ ^ ^
bounce mark' scan scan scan reset
XBC#Abd XBC#abd XBC#abd XBc#abd Xbc#abd Xbc#abd
^ ^ ^ ^ ^ ^
reset reset reset reset reset mark
XYc#abd ...
^
scan
Это будет допустимо, если у вас закончились немаркированные символы в W2 одновременно с тем, как у вас закончились немаркированные символы в W1 или ранее. В противном случае вы продолжите сброс до тех пор, пока не убедитесь, что в W1 нет первого отмеченного символа, который работает, и не отметили их все.