チューリングマシンの基本的な考え方とは

チューリング マシンの基本的なアイデアは、人間がペンと紙を使って数学的演算を実行するプロセスをマシンを使用してシミュレートすることです。このプロセスは、2 つの単純なアクションとして見ることができます: 1. 紙に特定の記号を書くか消す; 2. 紙上の 1 つの位置から別の位置に注意を移動します。

#この記事の動作環境: Windows 7 システム、Dell G3 コンピューター。

チューリング マシンは抽象的な機械を指します。無限に長い紙テープがあり、紙テープは小さな正方形に分割されており、各正方形は異なる色になっています。紙テープの上を動き回るマシンヘッドがあります。マシンヘッドには一連の内部状態と、いくつかの固定手順があります。マシンヘッドは各瞬間に、現在の紙テープから正方形の情報を読み取り、それ自体の内部状態に基づいてプログラムテーブルを検索し、プログラムに従って情報を紙テープの正方形に出力し、自身の内部状態を変換する必要があります。 、そして、行動を起こします。

#チューリングの基本的なアイデアは、人々が紙とペンを使用して数学的演算を実行するプロセスを機械を使用してシミュレートすることです。彼は、そのようなプロセスを次の 2 つの単純なアクションと見なしました:

1. 紙に特定の記号を書くか消す;

2. 紙の上のある位置から別の位置に注意を移します。

各段階で、人は次の行動を決定する必要があります。それは、(1) その人が現在注目している紙上の特定の位置にある記号、および (2) その人の現在の状態に応じて決まります。思考の。

この種の人間の計算プロセスをシミュレートするために、チューリングは次の部品で構成される架空の機械を構築しました:

1. 無限に長い紙テープ TAPE。紙テープは次々と小さなグリッドに分割され、各グリッドには限られたアルファベットの記号が含まれており、アルファベットには空白を表す特別な記号があります。紙テープのマス目は左から右に0、1、2…と番号が振られており、紙テープの右端は無限に伸ばすことができます。

2. 読み取り/書き込みヘッド HEAD。読み書きヘッドは紙テープ上で左右に移動でき、現在ポイントされているグリッド上のシンボルを読み取り、現在のグリッド上のシンボルを変更できます。

3. 一連の制御ルール TABLE。マシンの現在の状態と現在の読み書きヘッドが指すグリッド上のシンボルに基づいて読み書きヘッドの次の動作を決定し、ステータス レジスタの値を変更してマシンを新しい状態にします。 。

4. ステータスレジスタ。チューリング マシンの現在の状態を保存するために使用されます。チューリング マシンの取り得るすべての状態の数は有限であり、停止状態と呼ばれる特別な状態があります。シャットダウンの問題を参照してください。

このマシンのすべての部分は有限ですが、紙テープの長さは潜在的に無限であるため、このマシンは単なる理想的なデバイスであることに注意してください。チューリングは、そのような機械は人間が実行できるあらゆる計算プロセスをシミュレートできると信じていました。

プログラミング学習について詳しく知りたい方は、

php training のコラムに注目してください！

以上がチューリングマシンの基本的な考え方とはの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。