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

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

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

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

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

チューリングマシンの設計の基本的なガイドラインは、いくつかの例を使用して以下に説明されています。

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

溶液

チューリングマシン M は、次の動きによって構築することができます-

* q〜1〜*を初期状態とします。
M が* q〜1〜にある場合; αをスキャンすると、 q〜2〜状態になり、 *B （空白）を書き込みます。
M が* q〜2〜にある場合; αをスキャンすると、 q〜1〜状態になり、 *B （空白）を書き込みます。
上記の動きから、偶数個のαをスキャンすると M が* q〜1〜状態に入り、奇数個のαをスキャンすると q〜2〜状態になることがわかります。したがって、 q〜2〜*が唯一の受け入れ状態です。

したがって、

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

ここで、δは-

Tape alphabet symbol	Present State ‘q₁’	Present State ‘q₂’
α	BRq₂	BRq₁

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

溶液

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

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

* q〜0〜*を初期状態とします。
M が* q〜0〜にある場合、0を読み取ると、右に移動し、状態 q〜1〜に入り、0を消去します。 1を読み取ると、状態 q〜2〜*に入り、右に移動します。
M が* q〜1〜にある場合、0を読み取ると、右に移動して0を消去します。つまり、0をBに置き換えます。左端の1に到達すると、 q〜2〜に入り、右に移動します。 Bに達すると、つまり文字列が0のみで構成される場合、左に移動して状態 q〜3〜*になります。
M が* q〜2〜にある場合、0または1を読み取ると、右に移動します。 Bに到達すると、左に移動し、 q〜4〜*状態に入ります。これにより、文字列が0と1のみで構成されていることが検証されます。
M が* q〜3〜にある場合、Bを0に置き換え、左に移動して最終状態 q〜f〜*に到達します。
M が* q〜4〜にある場合、0または1を読み取ると、左に移動します。文字列の先頭に到達すると、つまりBを読み取ると、最終状態 q〜f〜*に到達します。

したがって、

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

ここで、δは-

Tape alphabet symbol	Present State ‘q₀’	Present State ‘q₁’	Present State ‘q₂’	Present State ‘q₃’	Present State ‘q₄’
0	BRq₁	BRq₁	ORq₂	-	OLq₄
1	1Rq₂	1Rq₂	1Rq₂	-	1Lq₄
B	BRq₁	BLq₃	BLq₄	OLq_f	BRq_f