チューリングマシンの欠けているステップ
2進数に1を加算するチューリングマシンを設計します。マシンは右から左へ数を処理し、次の規則に従います。
- いちばん右のビットから開始します。
- 現在のビットが0なら:1に反転して停止します。
- 現在のビットが1なら:0に反転します(1 + 1 はキャリーが発生するため)。その後、左へ移動して次のビットを処理します。
- いちばん左の桁より左へ移動した場合(つまり空白に到達した場合):キャリーを表す1を書き込み、停止します。
次の状態遷移図はこれらの手順を表そうとしていますが、重要な遷移が1つ欠けています。欠けているステップを特定してください。

この演習はコースの一部です
