graph - 単語を変更せずにシングル テープ チューリング マシンで回文を見つける

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

a を A に、b を B に変更できます。ur の末尾の文字は大文字になります。(ascia 値を取得し、それが大文字の範囲に収まる場合は、終わりがわかります) これは、入力が完全に小文字であると仮定しています。

Answer 3

テープ上にある可能性のある各シンボル (これは有限集合から引き出されていると想定しています) には、"$X_LOOKING" と呼ぶ状態が必要です。左端から始めて、そこにあるシンボル $X の状態を "$X_LOOKING" に設定します。最後まで右に移動し、$X と一致するかどうかを確認します。

左に戻ると、最初の文字ではなく2 番目の文字で停止する必要があります。このために、テープの別の領域で何文字を見たかを追跡できます。