Использование машины Тьюринга. Если бы входная лента машины состояла из строки 0 и 1, как бы вы подошли к решению проблемы, учитывая, что выходные данные машины должны быть 1 или 0 соответственно, в зависимости от того, палиндром это или нет.
Мне очень трудно осознать эту идею.
Любые советы будут очень признательны.
Я пытался разобраться в этой идее. идея в голове и на бумаге, например:
1, 0, 1, 0, 1
Я бы начал с 1 в состоянии «старт», а затем проверил символ. В этом примере символ равен 1, поэтому я бы установил новый «отмеченный» символ и переместился вправо в новом состоянии под названием «compare_right_1», в этом состоянии машина дойдет до конца и прочитает пустой символ. и, следовательно, доберитесь до конца ленты, поэтому двигайтесь влево и проверьте, есть ли в символе 1, если символ равен 1, то перейдите к следующему пробелу слева, если нет, то выйдите, поскольку это не палиндром.
Я не уверен, что это правильный подход.
Подробнее здесь: https://stackoverflow.com/questions/784 ... palindrome
