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

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

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

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

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

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

例1

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

Solution

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

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

• 場合 M にあります q₁; αをスキャンすると、状態になりますq₂ と書き込み B （ブランク）。

• 場合 M にあります q₂; αをスキャンすると、状態になりますq₁ と書き込み B （ブランク）。

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

したがって、

M = {{q ₁、q ₂ }、{1}、{1、B}、δ、q ₁、B、{q ₂ }}

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

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

例2

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

Solution

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

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

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

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

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

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

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

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

したがって、

M = {{q ₀、q ₁、q ₂、q ₃、q ₄、q _f }、{0,1、B}、{1、B}、δ、q ₀、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