チューリングマシンでの作業方法。チューリングマシンの基本

チューリングマシンは、20世紀で最も興味深く刺激的な知的発見の1つです。これは、あらゆるコンピュータータスクを実装するのに十分一般的な、シンプルで便利なコンピューティング（コンピューターおよびデジタル）の抽象モデルです。その簡単な説明と数学的分析のおかげで、それは理論計算機科学の基礎を形成します。この研究は、一般的なユーザーのコンピューターでは解決できないいくつかの計算問題があるという認識を含め、デジタルコンピューターと微積分のより深い理解につながりました。

Alan Turingは、コンピューターと同じ基本機能を備えた機械装置の最も原始的なモデルを説明しようとしました。チューリングは、1936年に、ロンドン数学会の議事録に掲載された「決定可能性問題への適用を伴う計算可能な数値について」でこのマシンについて最初に説明しました。

チューリングマシンは、読み取り/書き込みヘッド（または「スキャナー」）と紙テープが通っているコンピューティングデバイスです。テープは正方形に分割されており、それぞれに「0」または「1」の1つの記号が付いています。このメカニズムの目的は、入口と出口の両方の手段として、また計算の中間段階の結果を格納するための作業メモリーとして機能することです。デバイスの構成このような各マシンは、次の2つのコンポーネントで構成されています。無制限のテープ。それは両方向に無限であり、セルに分割されます。マシンは制御されたプログラムであり、データを読み書きするためのスキャナーヘッドです。いつでも多くの状態の1つになる可能性があります。

各マシンは、2つの有限データ系列をリンクします。入力シンボルのアルファベットA =（a0、a1、...、am）と状態のアルファベットQ =（q0、q1、...、qp）です。状態q0はパッシブと呼ばれます。デバイスは、デバイスにぶつかると作業を終了すると考えられています。状態q1は初期状態と呼ばれ、マシンは計算を開始します。入力された単語は、テープの各位置に1文字続けて配置されます。その両側には空のセルだけがあります。

メカニズムの仕組み

チューリングマシンは、コンピューティングデバイスとは根本的な違いがあります。そのストレージデバイスには無限のテープがありますが、デジタルデバイスの場合、そのようなデバイスには特定の長さのストリップがあります。タスクの各クラスは、1台の構築されたチューリングマシンによってのみ解決されます。別のタイプのタスクには、新しいアルゴリズムの作成が含まれます。制御装置は、1つの状態にあるため、テープに沿って任意の方向に移動できます。セルに書き込み、最後のアルファベットの文字をセルから読み取ります。移動中に、空の要素が割り当てられ、入力データを含まない位置が埋められます。チューリングマシンのアルゴリズムは、制御デバイスの遷移ルールを定義します。書き込み/読み取りヘッドに次のパラメータを設定します。セルに新しい文字を書き込む、新しい状態に遷移する、テープに沿って左または右に移動する。

動きのプロパティ

チューリングマシンは、他のコンピューティングシステムと同様に、固有の機能を備えており、アルゴリズムのプロパティである離散性に似ています。デジタルマシンは、前のステップが完了した後にのみ、次のステップn+1に進みます。完了した各ステップは、n+1がどうなるかを指定します。明快さ。デバイスは、同じセルに対して1つのアクションのみを実行します。アルファベットから文字を入力し、左または右の1つの動きをします。決定性。メカニズムの各位置は、指定されたスキームの唯一のバリアントに対応し、各段階でアクションとその実行の順序は明確です。効率。各ステップの正確な結果は、チューリングマシンによって決定されます。プログラムはアルゴリズムを実行し、有限のステップ数で状態q0に渡されます。マスキャラクター。各デバイスは、アルファベットに含まれる許可された単語に対して定義されます。チューリングマシンの関数アルゴリズムを解く際に、関数を実装する必要があることがよくあります。計算用のチェーンを作成する可能性に応じて、関数はアルゴリズム的に決定可能または決定不可能と呼ばれます。自然数または有理数のセット、つまりマシンの有限アルファベットNの単語として、セットBのシーケンスが考慮されます-バイナリコードアルファベットB =（0.1）のフレームワーク内の単語。また、計算の結果は、アルゴリズムが「フリーズ」したときに発生する「未定義」の値を考慮に入れています。関数を実装するには、有限のアルファベットに形式言語があり、正しい記述を認識する問題が解決可能であることが重要です。

デバイスソフトウェア

チューリングメカニズムのプログラムはテーブルに配置されており、最初の行と列には外部アルファベットの記号と、オートマトンの可能な内部状態の値（内部アルファベット）が含まれています。表形式のデータは、チューリングマシンが受け入れるコマンドです。問題解決は次のように進行します。現在上にあるセルのヘッドによって読み取られた文字と、オートマトンヘッドの内部状態によって、実行する必要のあるコマンドが決まります。具体的には、このようなコマンドは、表にある外部アルファベットと内部アルファベットの記号の交点にあります。

計算用コンポーネント

1つの特定の問題を解決するためのチューリングマシンを構築するには、次のパラメータを定義する必要があります。外部アルファベット。これは、記号Aで示される有限の記号のセットであり、その構成要素は文字と呼ばれます。それらの1つ（a0）は空である必要があります。たとえば、2進数で動作するチューリングデバイスのアルファベットは次のようになります：A =（0、1、a0）。文字の連続したチェーン-テープに記録された記号は単語と呼ばれます。オートマトンは、人間の介入なしに機能するデバイスです。チューリングマシンでは、問題を解決するためのいくつかの異なる状態があり、特定の条件下では、ある位置から別の位置に移動します。このようなキャリッジ状態のセットは、内部アルファベットです。 Q =（q1、q2 ...）のような文字指定があります。これらの位置の1つ（q1）は、最初の位置、つまりプログラムを開始する位置である必要があります。もう1つの必要な要素は、状態q0です。これは、最終状態、つまり、プログラムを終了してデバイスを停止位置に移動する状態です。

ジャンプテーブル。

このコンポーネントは、マシンの現在の状態と読み取られる文字の値に応じて、デバイスキャリッジの動作を行うためのアルゴリズムです。-

オートマトンのアルゴリズム

動作中のチューリングデバイスのキャリッジは、各ステップで次の一連のアクションを実行するプログラムによって制御されます。空の文字を含む位置に外部アルファベット文字を書き込み、空の要素を含むその中にある要素を置き換えます。ステップセルを1つ左または右に移動します。内部状態を変更します。したがって、文字または位置の各ペアのプログラムを作成するときは、次の3つのパラメータを正確に記述する必要があります。ai-選択したアルファベットAの要素、キャリッジシフトの方向（左に「←」、左に「→」）右、「ドット」-移動なし）およびqk-デバイスの新しい状態たとえば、コマンド1「←」q2の値は「文字を1に置き換えます。キャリッジヘッドを左に1ステップセル移動し、状態にジャンプします。 q2"。

日常、数学など、さまざまな複雑さの問題を解決することがよくあります。簡単に解決できるものもあれば、多くのことを考える必要があるものもあります。また、解決策が見つからないものもあります。

一般的なケースでは、問題を解決する方法（存在する場合）は、有限数の基本アクションを使用して記述できます。

たとえば、2次方程式を解きます。

方程式を標準形に変換します\（a x ^ 2 + b x + c = 0 \）
\（a = 0 \）の場合、これは解\（x = \ frac（-c）（b）\）を持つ線形方程式です。問題が解決しました。それ以外の場合は、手順3に進みます。
判別式を計算する\（D = b ^ 2-4 a c \）
方程式の解を計算する \（x_（1,2）= \ frac（-b \ pm \ sqrt（D））（2 a）\）。問題が解決しました。

アルゴリズムの次の直感的な概念を導入できます。

アルゴリズムは、任意の初期データのセットに対して、実行者が有限数のアクションで問題を解決した結果を達成するための手順を説明する一連の命令です。

もちろん、これは厳密な定義ではありませんが、アルゴリズムの概念の本質を説明しています。

アルゴリズムは特定のものに基づいてコンパイルされます パフォーマー、したがって、パフォーマーが理解できる言語である必要があります。

アルゴリズムの実行者は、人の場合もあれば、コンピューターの場合もあれば、織機などの他のオートマトンの場合もあります。

アルゴリズムの次のプロパティが区別されます。

アルゴリズムの離散性は、明確に定義された個別のステップ（アクション）の特定のシーケンスである必要があります。これらの各アクションは、時間的に有限でなければなりません。アルゴリズムの各ステップでの決定性。次のステップは、システムの現在の状態によって一意に決定されます。結果として、同じ初期データで、アルゴリズムは、実行回数に関係なく、常に同じ結果を返します。理解しやすさアルゴリズムは、実行者が理解できる言語で作成する必要があります。コンピューターについて話している場合、アルゴリズムは、コンピューターに認識されており、そのアクションの結果が厳密に定義されているコマンドのみを使用する必要があります。有限性アルゴリズムは有限のステップ数で完了する必要があります。アルゴリズムの質量特性は、さまざまな入力データのセットに適用できる必要があります。言い換えれば、アルゴリズムは解くのに適している必要があります クラスタスク。二次方程式の例に戻ると、アルゴリズムは解くのに適しています全て 1つ以上だけでなく、2次方程式。アルゴリズムは特定の結果で終了する必要があります。たとえば、問題を解決するか、解決策がないことを見つけます。アルゴリズムが結果につながらない場合、なぜそれが必要なのかは明確ではありません。

問題を解決するすべての方法がアルゴリズムであるとは限りません。アルゴリズムが選択の余地がないことを意味するとしましょう。たとえば、ほとんどの料理レシピは、「味に塩を加える」などのフレーズを使用しているため、アルゴリズムではありません。結果として、決定論の要件に違反します。

解決策があるすべての問題に対してではなく、解決策アルゴリズムもあります。たとえば、画像認識の問題はまだほとんど解決されておらず、厳密なアルゴリズムの助けを借りていないことは確かです。ただし、ニューラルネットワークを使用すると非常に良い結果が得られます。

通常、アルゴリズムにはセットがあります 許容可能入力データ。方程式を解くアルゴリズムを夕食の料理に適用しようとしたり、その逆を試みたりするのは奇妙なことです。

さらに、エグゼキュータの可能なアクションのセットも制限されています。これは、アクションが許可された場合、その中には「許容されない」ものでなければならないためです。

アルゴリズムの厳密な定義

上記のアルゴリズム定義は厳密ではありません。これはいくつかの困難を生み出します。特に、そのような定義では、与えられたクラスの問題がアルゴリズムによって解決可能かどうかを厳密に証明することは不可能です。

クラスがあることがわかりました アルゴリズム的に解決できない問題-解決するためのアルゴリズムを作成することが不可能な問題。しかし、アルゴリズムの決定不可能性を厳密に証明するには、最初にアルゴリズムの厳密な定義が必要です。

20世紀の20-30年代には、さまざまな数学者、特にアランチューリング、エミールレオンポスト、アンドレイアンドレービッチマルコフ、アンドレイニコラエビッチコルモゴロフ、アロンゾチャーチなどのアルゴリズムの厳密な定義の問題に取り組みました。彼らの研究は、最終的に、アルゴリズムの理論、計算可能性の理論、微積分へのさまざまなアプローチ、そして、ちなみに、プログラミング一般の出現と発展につながりました。彼らの研究の結果の1つは、アルゴリズムのいくつかの厳密な定義の出現であり、さまざまな方法で導入されましたが、互いに同等です。

Turingの定義について詳しく説明し、Post、Church、およびMarkovの同等の定義をざっと見ていきます。

チューリングマシン

アルゴリズムの正式な定義を紹介するために、チューリングはチューリングコンピューターまたは単にチューリングマシンと呼ばれる抽象コンピューターを発明して説明しました。

アラン・チューリング（1912-1954）

英国の数学者、論理学者、暗号学者、おそらく世界初の「ハッカー」は、コンピューターサイエンスと人工知能の理論の起源に立っていました。彼は第二次世界大戦における連合軍の勝利に多大な貢献をしました。

チューリングマシンへの入力として使用されます言葉、いくつかでコンパイル アルファベット、つまり、セット文字.

チューリングマシンの出力も言葉です。

アルゴリズムが適用される単語は、入力。仕事から生まれた言葉週末.

アルゴリズムが適用される単語のセットは呼び出されます アルゴリズムの範囲.

厳密に言えば、オブジェクトがアルファベットで構成された単語の形で表現できることを証明することは不可能です。このためには、オブジェクトの厳密な定義が必要になります。ただし、オブジェクトで機能するランダムに選択されたアルゴリズムは、アルゴリズムの本質を変更せずに単語で機能するように変換できることを確認できます。

チューリングマシンの説明

チューリングマシンの構成には、セルに分割された両方向に制限のないテープと、制御デバイス（別名 読み取り/書き込みヘッド、または単に機械）多くの状態の1つになる可能性があります。制御装置の可能な状態の数は有限であり、正確に与えられます。

制御装置は、テープに沿って左右に移動し、有限のアルファベットの文字をセルに読み書きできます。 \（a_0 \）または\（\ Lambda \）で示される特別な空の文字が割り当てられます。これは、入力データが書き込まれるセル（有限数）を除く、テープのすべてのセルを埋めます。

制御デバイスは、このチューリングマシンによって実装されるアルゴリズムを表す遷移ルールに従って動作します。各遷移ルールは、現在の状態と現在のセルで観察されたシンボルに応じて、このセルに新しいシンボルを書き込み、新しい状態に移動して1つのセルを左または右に移動するようにマシンに指示します。チューリングマシンのいくつかの状態は、ターミナルとしてマークすることができ、それらのいずれかに移行することは、作業の終了、アルゴリズムの停止を意味します。

チューリングマシンは抽象的な概念ですが、そのようなマシンを想像するのは簡単です（有限のテープを使用しますが）。次のようなデモンストレーションマシンもあります。

チューリングマシンのアルゴリズムを表の形式で提示すると便利です。表の列はテープ上の現在の（観測された）文字に対応し、行はオートマトンの現在の状態に対応し、セルは記録しますオートマトンが実行する必要のあるコマンド。

次に、コマンドは次の構造を持つ場合があります。

\ [a_k \ left \ lbrace \ begin（matrix）L \\ N \\ R \ end（matrix）\ right \ rbrace q_m \]

最初にアルファベットの文字が表示されます。これは現在のセル\（a_k \）に書き込む必要があります。次に、オートマトンの左（L）、右（R）、またはどこにも移動しない（所定の位置にとどまる、N）示されています。最後に、オートマトン\（q_m \）が入る新しい状態が示されます。

テーブルセルは、現在の文字\（a_i \）とオートマトン\（q_j \）の現在の状態によって明確に決定されます。

作業の開始時に、チューリングマシンが 初期状態、\（q_1 \）で示され、 停止状態\（q_0 \）アルゴリズムが終了し、マシンが停止します。

例

10進数である入力ワードに1を追加するチューリングマシンのアルゴリズムを書いてみましょう。

次に、記述的に、アルゴリズムは次のように定式化できます。

右に移動して、入力単語の先頭を見つけます
右に移動して、入力単語の終わりを見つけます
入力ワードの現在のビットに1を追加します。 0から8までの数字がある場合は、終了します。それ以外の場合は、0を書き込み、左に移動して、手順3に戻ります。

このアルゴリズムはテーブルの形で記述します。アルファベットは、0から9までの数字と「空白文字」\（\ Lambda \）で構成されます。また、アルゴリズムの説明のステップに対応して、停止状態をカウントするオートマトンの4つの状態が必要です。

初期状態\（1 \）は入力単語の先頭の検索、\（2 \）は入力単語の末尾の検索、\（3 \）は1の加算であることに同意します。

\（_（q_j）\ backslash ^（a_i）\）	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛL3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

このアルゴリズムがどのように機能するかを例で見てみましょう。最初の行はテープに対応し、2番目の行はマシンの位置とその現在の状態を示します。

	1	9	9
1

状態1では、オートマトンは空のセルの上にあります。テーブル「ΛP1」からの対応するコマンド、つまり、セルを空のままにして、右に移動し、状態1にとどまります。

	1	9	9
	1

これで、オートマトンは値「1」を監視します。対応するコマンドは「1H2」です。つまり、セルに「1」を残し、移動せず、状態「2」に移動します。

	1	9	9
	2

状態「2」では、マシンは値「1」を監視します。対応するコマンドは「1P2」です。つまり、「1」を残して右に移動し、状態「2」のままにします。

状況は繰り返されます：

ここで、状態3でシンボル「9」を観察すると、オートマトンはコマンド「0L3」を実行します。

	1	9	0
		3

状況は繰り返されます：

状態「0」–停止状態。アルゴリズムが完了しました。

正式な説明

数学的には、チューリングマシンは次のように説明できます。

チューリングマシン（MT）

それは形のシステムです \（\（A、a_0、Q、q_1、q_0、T、\ tau \）\）、どこ

\（A \）は、MTアルファベットの有限の記号セットです。
\（a_0 \ in A \）–アルファベットの空の文字
\（Q \）–MT状態の有限集合
\（q_1 \ in Q \）–MTの初期状態
\（q_0 \ in Q \）– MTの最終状態（停止状態）
\（T = \（L、P、H \）\）はMTのシフトのセットです
\（\ tau \）– MTプログラム、つまり、マッピングを定義する関数 \（\ tau：A \ times Q \バックスラッシュ\（q_0 \）\ rightarrow A \ times T \ times Q \）

アルゴリズムの理論の鍵は チューリングの論文.

大まかに言うと、チューリングの論文は次のように述べられています。

チューリングの理論アルゴリズム的に解決可能な問題には、この問題を解決するチューリングマシンがあります。それ以外の場合、どのアルゴリズムにも同等のチューリングマシンがあります。

チューリングの論文では、かなり単純な数学的装置を使用してアルゴリズムについて話すことができます。さらに、チューリングマシン自体は ユニバーサル作動装置、そしてそのような架空のマシンを作成する可能性は、ユニバーサルコンピューティングテクノロジーの作成について話す機会になりました。

代替アルゴリズムの定義

チューリングマシンとは別に、チューリング定義と同等の独立した定義がいくつかあります。

特に、Postマシン、Churchのラムダ計算、通常のマルコフアルゴリズムによる定義。

これらの方法を考えてみましょう。

ポストマシン

チューリングの1年後、アメリカの数学者エミール・レオン・ポストは、チューリングをいくらか単純化した別の抽象的なユニバーサルコンピューターを独自に提案しました。

ポストマシンは2桁のアルファベットで動作し、オートマトンの内部状態は次のように置き換えられます。 プログラムライン.

それ以外の点では、PostマシンはTuringマシンに似ています。オートマトンがあり、セルが付いた無限のテープがあります。

Postマシンは、次のコマンドを実行できます。

1を書いて、プログラムのi番目の行に移動します
0を書き込み、プログラムのi番目の行に移動します
左にシフトし、プログラムのi番目の行に移動します
右にシフトし、プログラムのi番目の行に移動します
条件分岐：観測されたセルが0の場合は、プログラムのi行目に移動します。それ以外の場合は、プログラムのj行目に移動します。
止まる。

Postマシンには、いくつかの禁止されたコマンドもあります。

すでに1がある場合は、セル1に書き込みます。
すでに0がある場合にセル0に書き込みます。

このようなイベントはクラッシュにつながります。

次の表記法を使用して、ポストマシン用のプログラムを作成できます。

∨i-1を書き込み、プログラムのi番目の行に移動します
×i– 0を書き込み、プログラムのi番目の行に移動します
←i-左にシフトし、プログラムのi番目の行に移動します
→i-右にシフトし、プログラムのi番目の行に移動します
？私; j –条件付き遷移：観測されたセルが0の場合は、プログラムのi番目の行に移動します。それ以外の場合は、プログラムのj番目の行に移動します。
！ - 止まる。

プログラム例：

1.→22.？ 1; 33.×44.←55.！

このプログラムは、オートマトンの開始位置の右側にある最初のラベル（1）を消去し、その左側のセルにあるオートマトンを停止します。

概して、郵便機は先駆者です命令 C、Fortranなどのプログラミング言語

ポストマシンはチューリングマシンと同等です。つまり、どのチューリングマシンプログラムでも、同等のポストマシンプログラムを作成できます。その逆も可能です。

この同等性の重要な結果の1つは、 任意のアルファベットをバイナリコードに減らすことができます.

チューリングの論文と同様に、ポストの論文もあります。

ポストの論文すべてのアルゴリズムはポストマシンとして表すことができます。

通常のマルコフアルゴリズム

通常のマルコフアルゴリズムは、さまざまなアルファベットの単語に適用されるように設計されています。

通常のアルゴリズムの定義は、次の2つの部分で構成されます。

アルファベットアルゴリズム
図式アルゴリズム

アルゴリズム自体はに適用されます言葉、つまり、文字のシーケンス アルファベット.

通常のアルゴリズムのスキームは、いわゆる有限順序集合です。 置換式、それぞれが単純また 最後の。単純な置換式は、\（L \ to D \）の形式の式です。ここで、\（L \）と\（D \）は、アルゴリズムのアルファベットから構成される2つの任意の単語です（それぞれ、左と右の部分と呼ばれます）。置換式の）。同様に、最終的な置換式は、\（L \ to \ cdot D \）の形式の式です。ここで、\（L \）と\（D \）は、アルゴリズムのアルファベットから構成される2つの任意の単語です。

補助文字\（\ to \）および\（\ to \ cdot \）は、アルゴリズムのアルファベットに属していないことを前提としています。

通常のアルゴリズムを任意の単語\（V \）に適用するプロセスは、次の一連のアクションです。

\（V "\）をアルゴリズムの前のステップで取得された単語（または現在のステップが最初の場合は元の単語）とします。
置換式の中に誰もいない場合、その左側は\（V "\）に含まれ、アルゴリズムの作業は完了したと見なされ、単語\（V" \）は次の結果と見なされます。この作品。
それ以外の場合は、左側が\（V "\）に含まれている置換式の中で、最初の式が選択されます。
\（RLS \）の形式での単語\（V "\）のすべての可能な表現（ここで、\（R \）は接頭辞、\（L \）は接尾辞）のうち、\（R \）が最短で、その後に置換\（V "= RDS \）が実行されます。
置換式が有限の場合、アルゴリズムは結果\（V "\）で終了します。それ以外の場合は、ステップ1（次のステップ）に進みます。

通常のアルゴリズムはチューリングマシンと同等であり、逆にチューリングマシンは通常のアルゴリズムと同等です。

通常のアルゴリズムに対するチューリングの理論の類似物は、通常、 正規化の原則.

例

このアルゴリズムは、2進数を「単一の」数値に変換します（非負の整数NのレコードはN個のスティックの文字列です）。たとえば、2進数101は5つのスティックに変換されます：|||||。

アルファベット：（0、1、|）ルール：

1 → 0|
|0 → 0||
0→（空の文字列）

ソース行：101実行：

0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

再帰関数

チューリングマシンと同等のシステムは、数学関数に基づいて構築することができます。これを行うには、次の関数クラスを導入する必要があります。

原始再帰関数
一般的な再帰関数
部分再帰関数

最後のクラスは、チューリング計算可能関数（つまり、チューリングマシンのアルゴリズムで評価できる関数）のクラスと同じになります。

再帰関数に関するアルゴリズムの定義は、基本的にラムダ計算の基礎であり、アプローチはそれに基づいています。 関数型プログラミング.

原始再帰関数

原始再帰関数のクラスには次のものが含まれます 基本機能そして、演算子によってベース関数から取得されたすべての関数置換と 原始再帰.

基本的な機能は次のとおりです。

null関数\（O（）= 0 \）は、常に\（0 \）を返す引数のない関数です。
後継関数\（S（x）= x + 1 \）は、任意の自然数\（x \）を次の数\（x + 1 \）に関連付ける関数です。
機能 \（I_n ^ m（x_1、\ ldots、x_n）= x_m \）、ここで\（0

残りのクラス関数を作成するには、次の演算子を使用します。

代用。 \（m \）変数の関数\（f \）と\（n \）変数の\（g_1、\ ldots、g_m \）関数の場合、それぞれ\（g_k \）を代入した結果into \（f \）は関数です \（h（x_1、\ ldots、x_n）= f（g_1（x_1、\ ldots、x_n）、\ ldots、g_m（x_1、\ ldots、x_n））\）\（n \）変数から。
原始再帰。 \（f（x_1、\ ldots、x_n）\）を\（n \）変数の関数とし、\（g（x_1、\ ldots、x_（n + 2））\）を\（ n + 2 \）変数。次に、原始再帰演算子を関数\（f \）と\（g \）に適用した結果は、次の形式の\（n + 1 \）変数の関数\（h \）になります。 \ [h（x_1、\ ldots、x_n、0）= f（x_1、\ ldots、x_n）\] \ [h（x_1、\ ldots、x_n、y + 1）= g（x_1、\ ldots、x_n、y、h（x_1、\ ldots、x_n、y））\]

部分再帰関数

部分再帰関数のクラスには、原始再帰関数に加えて、引数最小化演算子を使用して原始再帰関数から取得されるすべての関数が含まれます。

引数最小化演算子

\（f \）を\（n \）変数\（x_i \ in \ mathbb（N）\）の関数とします。次に、引数最小化演算子を関数\（f \）に適用した結果は、\（n-1 \）引数の関数\（h \）であり、次のように定義されます。

\ [h（x_1、\ ldots、x_（n-1））= \ min y、\]どこ \ つまり、\（h \）は、\（f \）の値がゼロである関数\（f \）の最後の引数の最小値を返します。

原始再帰関数は常に計算可能ですが、一部の引数値では部分再帰関数が定義されていない場合があります。

より厳密には、部分的に再帰的な関数は、引数の可能な値の一部でのみ定義されるため、「部分的に定義された再帰関数」と呼ばれる必要があります。

一般的な再帰関数

一般的な再帰関数は、任意の引数値に対して定義されているすべての部分再帰関数のサブクラスです。特定の部分再帰関数が一般再帰であるかどうかを判断する問題は次のとおりです。 アルゴリズム的に決定不可能。これは、計算可能性理論と停止性問題のトピックに私たちをもたらします。

計算可能性理論と停止性問題

私たちの想像力は全体として、解決できない問題、つまりアルゴリズムを構成することが不可能な問題の存在を認めています。

計算可能性理論は、そのような問題の研究を扱います。

アルゴリズム的に解決できない問題の例は次のとおりです。 問題を止めると 微分可能性認識問題。それらをさらに詳しく考えてみましょう。

停止問題アルゴリズムAと入力\（x \）の説明を考えると、アルゴリズム\（A \）が入力\（x \）で停止するかどうかを調べる必要があります。

停止問題はアルゴリズム的に決定不可能です。それを証明しましょう。

\（\デルタ\）

停止性問題を解決する普遍的なアルゴリズムがあるとしましょう。次に、アルゴリズムを説明するテキストを処理するアルゴリズムのクラスについて考えてみましょう。

停止問題を解くための普遍的なアルゴリズムが存在するため、言及されたクラスのアルゴリズムがそれ自体のテキストで停止するかどうかを決定するアルゴリズムがあります。そのようなアルゴリズム\（B \）を示します。

アルゴリズム\（C \）を作成してみましょう。その入力は、アルゴリズム\（A \）のテキストであり、独自のテキストを処理します。

\（A \）でアルゴリズム\（B \）を実行します。
\（B \）アルゴリズムが\（A \）がそのテキストで停止すると判断した場合は、手順1に進みます。それ以外の場合は、手順3に進みます。
\（C \）アルゴリズムの終了。

\（C \）アルゴリズムを\（C \）アルゴリズムに適用しようとすると、明らかな矛盾が発生します。\（C \）がそれ自体のテキストで停止する場合、停止することはできません。その逆も同様です。したがって、\（B \）アルゴリズムはありません。 \（\ not \ Delta \）

停止性問題のより一般的な定式化は、微分可能性を決定する問題です。

微分可能性認識の問題

特定のアルファベット、このアルファベットの単語（式）、およびこのアルファベットの単語に対する形式的な変換のシステムを定義します（つまり、論理微積分が構築されます）

与えられた論理微積分内に\（R \）から\（S \）につながる演繹的連鎖\（R \）と\（S \）の2つの単語が存在しますか？

1936年、アロンゾチャーチは教会の定理を証明しました。

教会の定理推論可能性を認識する問題は、アルゴリズム的に解決できません。

教会はそれを証明するためにラムダ計算の形式を使用しました。 1937年、彼とは関係なく、チューリングはチューリングマシンの形式を使用して同じ定理を証明しました。

アルゴリズムのすべての定義は互いに同等であるため、アルゴリズムの特定の定義に関連せず、その概念で動作する概念のシステムがあります。 計算可能関数.

計算可能関数は、アルゴリズムによって評価できる関数です。

入力データと出力データの関係をアルゴリズムで記述できないという問題があります。そのような機能は 計算できない.

計算不可能な関数の例

次のように、\（\ forall n \ in \ mathbb（N）\）に対して定義された関数\（h（n）\）を取ります。

\ [h（n）= \ begin（cases）1、＆\ text（if）\ pi \ text（には正確に）n \ text（9th）\\ 0のシーケンスが含まれ、＆\ text（それ以外の場合）\ end（ケース）\]

この関数の値\（1 \）を取得できますが、値\（0 \）を取得するには、数値\（\ pi \）の無限小数展開をチェックする必要があります。これは有限では明らかに不可能です。時間。したがって、この関数は計算不可能です。

1920年代以降の表現 計算機動作したすべてのマシンを指します 人間のコンピューター特に、チャーチチューリングテーゼの効率的な方法に従って開発されたもの。この論文は次のように定式化されます。「任意のアルゴリズムは、対応するチューリングマシンまたは部分再帰的定義の形式で与えることができ、計算可能関数のクラスは、部分再帰関数のクラスおよびチューリングマシンで計算可能な関数のクラスと一致します。 "。別の言い方をすれば、チャーチチューリングの論文は、電子計算機などの機械式コンピューティングデバイスの性質に関する仮説として定義されています。十分な時間とストレージスペースがあれば、可能な計算はすべてコンピューターで実行できます。

無限大の計算に作用するメカニズムは、アナログタイプとして知られるようになりました。このようなメカニズムの値は、シャフトの回転角や電位差などの連続した数値で表されていました。

アナログマシンとは異なり、デジタルマシンには、数値の状態を表し、各桁を個別に格納する機能がありました。ランダムアクセスメモリデバイスが発明される前は、デジタルマシンはさまざまなプロセッサまたはリレーを使用していました。

名前 計算機 1940年代からコンセプトに取って代わられ始めました コンピュータ。それらのコンピューターは、店員が行っていた計算を行うことができました。値は（アナログマシンのように）物理的特性に依存しなくなったため、デジタルハードウェアに基づく論理コンピューターは記述できることをすべて実行できるようになりました。 純粋に機械的なシステム .

チューリングマシンは、計算能力に限界がある場合に計算できるものを数学的に正式に定義するように設計されています。チューリングマシンがタスクを実行できる場合、そのタスクはチューリング計算可能であると言われます。チューリングは主に、何を計算できるかを決定できるマシンの設計に焦点を当てていました。チューリングは、数値の近似値を計算できるチューリングマシンがある限り、その値は可算であると結論付けました。さらに、チューリングマシンは、AND、OR、XOR、NOT、および「If-Then-Else」などの論理演算子を解釈して、

チューリングマシンは、次のオブジェクトのコレクションです

1）外部アルファベットA =（a 0、a 1、…、a n）;
2）内部アルファベットQ =（q 1、q 2、…、q m）-状態のセット。
3）制御文字のセット（P、L、S）
4）セルに分割された、両方向のエンドレステープ。各セルには、任意の離散時間にアルファベットAの1文字のみを含めることができます。
5）多くの状態の1つになることができる制御装置

空のセルの記号は、外部アルファベットの文字である0です。

状態の中で、最初のq 1は機械が動作を開始する状態であり、最後の（または停止状態）q0は機械が停止するときに区別されます。

制御装置は、テープ上を左右に移動したり、アルファベットAの文字をテープのセルに読み書きしたりできます。制御装置は、次の形式のコマンドに従って動作します。

q i a j> a p X q k

記録とは、次のことを意味します。制御デバイスが状態q iにあり、表示されているセルに文字a jが書き込まれている場合、（1）jの代わりにpがセルに書き込まれ、（2）マシンはレビューに進みます。 X = Pの場合は表示されたばかりのセルから次の右側のセル、X = Lの場合は次の左側のセルを表示、X = Cの場合は同じテープセルを引き続き表示するには、（3）制御デバイスが入力されます。状態qk。

マシンの動作は、条件によって、特定の瞬間の状態qと、その瞬間に表示されるセルの内容aによって完全に決定されるため、可能な構成q iajごとに1つのルールがあります。機械が停止する最終状態だけのルールはありません。したがって、外側のアルファベットA =（a0、a1、…、an）と内側のアルファベットQ =（q1、q2、…、qm）を持つチューリングマシンプログラムには、m（n + 1）個以下の命令が含まれます。

アルファベットAまたはアルファベットQまたはアルファベットAQの単語は、対応するアルファベットの文字の任意のシーケンスです。 k番目の構成では、k番目のステップの開始までに開発された情報（またはテープに書かれたアルファベットAの単語）を含むマシンのテープのイメージを意味します。 k番目のステップ）、このステップでどのセルが表示されているかを示します。また、車はどのような状態にありますか？有限の構成のみが意味をなします。有限数を除いて、テープのすべてのセルが空であるセル。マシンの状態が最終である場合、構成は最終であると言われます。

チューリングマシンの非最終構成を初期構成として選択した場合、マシンの仕事は、最終構成に到達するまで、マシンプログラムに従って初期構成を順次（段階的に）変換することです。その後、チューリングマシンの作業が完了したと見なされ、作業の結果が最終構成に到達します。

アルファベットA（а0）=（a 1、...、a n）の空でない単語bは、テープの連続するセルに書き込まれた場合、マシンによって標準の位置で認識されます。他のセルは空であり、マシンは単語bが書き込まれているセルから左端または右端のセルをスキャンします。標準位置の単語を認識する機械が初期状態q1（それぞれ停止状態q 0）にある場合、標準位置は初期（最終）と呼ばれます。

単語bの処理によってチューリングマシンが最終状態になる場合は、bに適用されると言われます。それ以外の場合は、bには適用されません（マシンは無期限に実行されます）。

例を考えてみましょう。

外部アルファベットA\u003d（0、1）（ここで0は空のセルのシンボル）、内部状態Q \ u003d（q 0、q 1、q 2）のアルファベット、および次のチューリングマシンがあるとします。機能図（プログラム）：

q 1 0> 1 L q 2;

q11>0Сq2;

q20>0Пq0;

q 2 1> 1 C q 1;

このプログラムは、テーブルを使用して作成できます

最初のステップで、コマンドは次のように動作します。q 1 0>1Лq2（制御デバイスはq1状態にあり、文字0は監視対象セルに書き込まれ、文字0は0の代わりにセルに書き込まれます。を左にシフトすると、制御デバイスはq2状態に切り替わります）、その結果、マシン上に次の構成が作成されます。

最後に、コマンドq 2 0> 0 P q 0を実行した後、構成が作成されます

マシンが停止状態q0にあるため、この構成は最終的なものです。

したがって、元の単語１１０は、機械によって単語１０１に処理される。

結果として得られる構成のシーケンスは、より短い方法で書き込むことができます（監視対象セルの内容は、マシンが現在配置されている状態の右側に書き込まれます）。

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

チューリングマシンは、アルファベットA Qの単語を変換するための規則（アルゴリズム）にすぎません。構成。したがって、チューリングマシンを定義するには、その外部および内部のアルファベットであるプログラムを指定し、どの記号が空のセルと最終状態を示すかを示す必要があります。

それは何で、誰がそれを作成したのか

デバイスは何でできていますか？

このような各マシンは、次の2つのコンポーネントで構成されています。

無制限のテープ。それは両方向に無限であり、セルに分割されます。
マシンは制御されたプログラムであり、データを読み書きするためのスキャナーヘッドです。いつでも多くの状態の1つになる可能性があります。

メカニズムの仕組み

制御装置は、1つの状態にあるため、テープに沿って任意の方向に移動できます。セルに書き込み、最後のアルファベットの文字をセルから読み取ります。移動中に、空の要素が割り当てられ、入力データを含まない位置が埋められます。チューリングマシンのアルゴリズムは、制御デバイスの遷移ルールを定義します。書き込み/読み取りヘッドに次のパラメータを設定します。セルに新しい文字を書き込む、新しい状態に遷移する、テープに沿って左または右に移動する。

動きのプロパティ

チューリングマシンは、他のコンピューティングシステムと同様に、固有の機能を備えており、アルゴリズムのプロパティに似ています。

離散性。デジタルマシンは、前のステップが完了した後にのみ、次のステップn+1に進みます。完了した各ステップは、n+1がどうなるかを指定します。
明快さ。デバイスは、同じセルに対して1つのアクションのみを実行します。アルファベットから文字を入力し、左または右の1つの動きをします。
決定性。メカニズムの各位置は、指定されたスキームの唯一のバリアントに対応し、各段階でアクションとその実行の順序は明確です。
効率。各ステップの正確な結果は、チューリングマシンによって決定されます。プログラムはアルゴリズムを実行し、有限のステップ数で状態q0に渡されます。
マスキャラクター。各デバイスは、アルファベットに含まれる許可された単語に対して定義されます。

チューリングマシンの機能

アルゴリズムを解く際には、関数の実装が必要になることがよくあります。計算用のチェーンを作成する可能性に応じて、関数はアルゴリズム的に決定可能または決定不可能と呼ばれます。自然数または有理数のセット、つまりマシンの有限アルファベットNの単語として、セットBのシーケンスが考慮されます-バイナリコードアルファベットB =（0.1）のフレームワーク内の単語。また、計算の結果は、アルゴリズムが「フリーズ」したときに発生する「未定義」の値を考慮に入れています。関数を実装するには、有限のアルファベットに形式言語があり、正しい記述を認識する問題が解決可能であることが重要です。

デバイスソフトウェア

計算用コンポーネント

1つの特定の問題を解決するためのチューリングマシンを構築するには、次のパラメータを定義する必要があります。

外部アルファベット。これは、記号Aで示される有限の記号のセットであり、その構成要素は文字と呼ばれます。それらの1つ（a0）は空である必要があります。たとえば、2進数で動作するチューリングデバイスのアルファベットは次のようになります：A =（0、1、a0）。

文字の連続したチェーン-テープに記録された記号は単語と呼ばれます。

オートマトンは、人間の介入なしに機能するデバイスです。チューリングマシンでは、問題を解決するためのいくつかの異なる状態があり、特定の条件下では、ある位置から別の位置に移動します。このようなキャリッジ状態のセットは、内部アルファベットです。 Q =（q1、q2 ...）のような文字指定があります。これらの位置の1つ（q1）は、最初の位置、つまりプログラムを開始する位置である必要があります。もう1つの必要な要素は、状態q0です。これは、最終状態、つまり、プログラムを終了してデバイスを停止位置に移動する状態です。

ジャンプテーブル。このコンポーネントは、マシンの現在の状態と読み取られる文字の値に応じて、デバイスキャリッジの動作を行うためのアルゴリズムです。

オートマトンのアルゴリズム

動作中のチューリングデバイスの運搬は、各ステップで次の一連のアクションを実行するプログラムによって制御されます。

空のアルファベットを含む位置に外部アルファベットの文字を書き込み、その中にある要素を空の要素を含めて置き換えます。
ステップセルを1つ左または右に移動します。
内部状態を変更します。

したがって、文字または位置の各ペアのプログラムを作成するときは、次の3つのパラメータを正確に記述する必要があります。ai-選択したアルファベットAの要素、キャリッジシフトの方向（左に「←」、左に「→」）右、「ドット」-移動なし）およびq k-デバイスの新しい状態たとえば、コマンド1「←」q 2は、「文字を1に置き換え、キャリッジヘッドを1ステップセル左に移動して、状態q2にジャンプする」という意味です。 "。

チューリングマシン：例

例1タスクは、テープにある特定の番号の最後の桁に1を追加するアルゴリズムを構築することです。入力データ-ワード-テープの連続したセルに書き込まれた10進数全体の数字。最初の瞬間、デバイスは右端の文字（数字の数字）の反対側にあります。

解決。最後の桁が9の場合は、0に置き換えてから、前の文字に1を追加する必要があります。この場合の特定のチューリングデバイスのプログラムは、次のように記述できます。

ここで、q 1は桁変更の状態、q0は停止です。 q 1で、オートマトンが行0..8の要素を修正すると、それぞれ1..9のいずれかに置き換えられ、状態q 0に切り替わります。つまり、デバイスは停止します。キャリッジが番号9を固定すると、それは0に置き換えられ、次に左に移動して、状態q1で停止します。この移動は、デバイスが9未満の数字を修正するまで続きます。すべての文字が9に等しい場合、それらはゼロに置き換えられ、最も高い要素の代わりに0が書き込まれ、キャリッジは左に移動し、1を空のセル。次のステップは、状態q0への遷移です-停止します。

例2開き括弧と閉じ括弧を示す一連の記号が与えられます。相互ブラケットのペア、つまり、一列に配置された要素「（）」を削除するチューリングデバイスを構築する必要があります。たとえば、入力データ：“）（（）（（）”、答えは次のようになります：“）..。（（”。解決策：q 1にあるメカニズムは、文字列の左端の要素を分析します。

状態q1：記号「（」が検出された場合は、右にシフトして位置q 2に移動します。「a0」が定義されている場合は、停止します。

状態q2：括弧「（」はペアリングの存在について分析されます。一致する場合は、「）」を取得する必要があります。要素がペアの場合は、キャリッジリターンを左に実行して、q3に進みます。

状態q3：最初に文字「（」、次に「）」を削除して、q1に進みます。

密閉する