始める無料で始める

チューリングマシンの欠けているステップ

2進数に1を加算するチューリングマシンを設計します。マシンは右から左へ数を処理し、次の規則に従います。

  • いちばん右のビットから開始します。
  • 現在のビットが0なら:1に反転して停止します。
  • 現在のビットが1なら:0に反転します(1 + 1 はキャリーが発生するため)。その後、左へ移動して次のビットを処理します。
  • いちばん左の桁より左へ移動した場合(つまり空白に到達した場合):キャリーを表す1を書き込み、停止します。

次の状態遷移図はこれらの手順を表そうとしていますが、重要な遷移が1つ欠けています。欠けているステップを特定してください。

Turing diagram with missing step

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

コンピュータサイエンスの基礎概念

コースを見る

実践的なインタラクティブ演習

理論を実践に変える、インタラクティブな演習のひとつをお試しください

演習を開始する