受け入れられる言語と決定された言語

TMは、入力文字列wの最終状態に入ると、言語を受け入れます。言語がチューリングマシンによって受け入れられる場合、その言語は再帰的に列挙可能です(タイプ0文法によって生成されます)。

TMは、言語を受け入れるかどうかを決定し、その言語以外の入力に対して拒否状態になります。チューリングマシンによって決定された場合、言語は再帰的です。

TMが止まらない場合があります。そのようなTMは言語を受け入れますが、それを決定しません。

チューリングマシンの設計

チューリングマシンを設計するための基本的なガイドラインは、いくつかの例の助けを借りて以下に説明されています。

例1

奇数のαで構成されるすべての文字列を認識するようにTMを設計します。

Solution

チューリングマシン M 次の動きで構築できます-

  • しましょう q1 初期状態になります。

  • 場合 M にあります q1; αをスキャンすると、状態になりますq2 と書き込み B (ブランク)。

  • 場合 M にあります q2; αをスキャンすると、状態になりますq1 と書き込み B (ブランク)。

  • 上記の動きから、 M 状態に入る q1 偶数個のαをスキャンして状態に入ると q2奇数のαをスキャンする場合。したがって、q2 唯一の受け入れ状態です。

したがって、

M = {{q 1、q 2 }、{1}、{1、B}、δ、q 1、B、{q 2 }}

ここで、δは次の式で与えられます。

テープアルファベット記号 現状 'q 1 ' 現状 'q 2 '
α BRq 2 BRq 1

例2

2進数を表す文字列を読み取り、文字列の先頭の0をすべて消去するチューリングマシンを設計します。ただし、文字列が0のみで構成されている場合は、1つの0を保持します。

Solution

入力文字列が、文字列の両端にある空白の記号Bで終了していると仮定します。

チューリングマシン、 M、次の動きで構築できます-

  • しましょう q0 初期状態になります。

  • 場合 M にあります q0、0を読み取ると、右に移動し、状態になります q1 そして0を消去します。1を読み取ると、状態になります。 q2 右に移動します。

  • 場合 M にあります q1、0を読み取ると、右に移動して0を消去します。つまり、0をBに置き換えます。左端の1に達すると入りますq2右に移動します。Bに達すると、つまり文字列が0のみで構成される場合、左に移動して状態になりますq3

  • 場合 M にあります q2、0または1を読み取ると、右に移動します。Bに到達すると、左に移動して状態になりますq4。これにより、文字列が0と1のみで構成されていることが検証されます。

  • 場合 M にあります q3、Bを0に置き換え、左に移動して最終状態に到達します qf

  • 場合 M にあります q4、0または1を読み取ると、左に移動します。文字列の先頭に到達すると、つまりBを読み取ると、最終状態に到達しますqf

したがって、

M = {{q 0、q 1、q 2、q 3、q 4、q f }、{0,1、B}、{1、B}、δ、q 0、B、{q f }}

ここで、δは次の式で与えられます。

テープアルファベット記号 現在の状態 'q 0 ' 現状 'q 1 ' 現状 'q 2 ' 現状 'q 3 ' 現状 'q 4 '
0 BRq 1 BRq 1 ORq 2 - OLq 4
1 1Rq 2 1Rq 2 1Rq 2 - 1Lq 4
B BRq 1 BLq 3 BLq 4 OLq f BRq f