поиск палиндрома на машине для ленточной ленты без изменения слова

Question

Довольно легко найти заменяющие палиндром буквы на обоих концах (Φ).

 ΦabaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbΦΦ
 ΦΦbΦΦ
 ΦΦbΦΦ
 ΦΦΦΦΦ
 ΦΦΦΦΦ
 ΦΦΦΦΦ YES

Это возможно при изменении a на A и изменении A на a в конце задачи. Но есть ли у кого-нибудь идея, как этого добиться, не используя дополнительные знаки?

Answer 1

Может помочь перемещение конечных символов:

 ΦΦabaΦΦ
 ΦaΦbaΦΦ
 ΦaΦbΦaΦ YES

или

 ΦΦabbaΦΦ
 ΦaΦbbaΦΦ
 ΦaΦbbΦaΦ
 ΦabΦbΦaΦ
 ΦabΦΦbaΦ YES

Answer 2

Для каждого возможного символа на ленте (который, как я полагаю, взят из конечного набора) вам нужно состояние, которое я назову «$ X_LOOKING». Начните с левого конца и установите состояние «$ X_LOOKING» для символа $ X, который вы там найдете. Двигайтесь вправо, пока не дойдете до конца, и посмотрите, соответствует ли оно $ X.

Когда вы двигаетесь назад влево, вам придется остановиться на 2nd букве вместо первой. Для этого, возможно, вы можете отслеживать, сколько букв вы просматривали в другой области ленты.

Answer 3

Вы можете изменить a на A, а b на B, и ваш конечный символ будет заглавной.(возьмите значение ascia, и если оно попадает в верхний регистр, вы знаете конец). Это означает, что ваш ввод полностью строчный.