言語L={ww|のチューリングマシンを構築するw∈{0,1}}

ここでは、言語L ={WW | Wが{0、1}}に属するチューリングマシンを作成する方法を説明します。したがって、これは、0と1の2文字のみを使用する一種の言語を表します。 wは文字列です。したがって、w =10110の場合、チューリングマシンは文字列z=1011010110を受け入れます。

これを解決するために、このアプローチを使用します。まず、文字列の中点を見つけます。0をxに、1をyに変換します。継続的に実行した後、すべての0と1がそれぞれxとxに変換された時点に到達します。今、私たちは文字列の中点にいます。これで、最初の目標は完了しました。

ここで、中点の左側にあるすべてのxとyを0と1に変換します。これで、文字列の前半は0と1の形式になります。文字列の後半はxとyの形式になります。

ここで、再び文字列の先頭から開始します。 0がある場合は、それをxに変換し、後半に達するまで右に移動します。ここでxが見つかった場合は、それを空白（B）に変換します。次に、xまたはxが見つかるまでトラバースします。その右側の0または1をそれぞれxまたはyに変換し、それに応じて、文字列の後半のxまたはyを空白（B）に変換します。

文字列の左側のすべての記号がxとyに変換され、文字列の右側のすべての記号が空白に変換されるまで、これを繰り返します。一部が完全に変換されても、残りの半分の一部の記号が変更されない場合、文字列は受け入れられません。前半でそれぞれ対応する0または1について、後半でxまたはyが見つからなかった場合。そうすると、文字列も受け入れられなくなります。

状態遷移図