石
チューリングマシンの構成例。チューリングマシン上の関数の適切な計算可能性

チューリングマシンの構成例。チューリングマシン上の関数の適切な計算可能性

チューリングマシン (MT) は、抽象的な実行者 (抽象的なコンピューティングマシン) です。

アルゴリズムの組み合わせは、いくつかの与えられたアルゴリズムから新しいアルゴリズムを構築するための多くの特定の方法に対して確立された名前です。

アルゴリズムの組み合わせに関する定理は、アルゴリズムの一般理論の重要な部分を構成します。一度証明されると、複雑で面倒なアルゴリズムを定義する回路を実際に書き出すことなく、後でその実現可能性を検証することが可能になります。

チューリングマシンのアルゴリズムの組み合わせは、チューリングマシンでの演算によって記述されます。

1.合成操作。

M 1 と M 2 を同じ外部アルファベット A« (a 0 ,a 1 ,...,a p ) を持つチューリングマシンとする。それらの状態の集合をそれぞれ Q1 "(q 0,q 1,...,q n) および Q2 "(q 0",q 1",...,q m") と表すことにします。

意味。

マシン M 1 と M 2 の組み合わせは、M=M 1 ×M 2 で示されるマシンであり、そのプログラムはアルファベット A、状態の集合 Q« (q 0,q 1,...,q n,q) を持ちます。 n+1,...,q n+m) であり、次のようにマシン M 1 および M 2 のプログラムから取得されます。マシン M 1 のプログラムのどこにでも、記号 q 1 (マシン M 1 の最終状態)、シンボル q 0" (マシン M 2 の初期状態) に置き換えられます。マシン M 1 と M 2 のプログラム内の他のすべてのシンボルは変更されません (最終的には、残りは、マシン M のすべての状態の番号を付け直すことです: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" ))。

この構成はマシン M 1 として「動作」し始めますが、マシン M 1 を停止する必要がある場合には、q 1 を q 0 に置き換えることにより、マシン M 2 のプログラムに切り替わります。合成操作は結合的ですが、可換的ではありません。

その動作は、マシン T1 と T2 の順次動作と同等です。

図は、n=1、m=1の重ね合わせ演算子を実装したチューリングマシンの構成を示しています。

写真1。

意味。

チューリングマシン M の反復をマシンと呼びます

2. 分岐操作。

M 1、M 2、および M 3 を、同じ外部アルファベット A« (a 0,a 1,...,ai,...,a j,...,ap) を持つチューリングマシンとし、したがって、状態: Q1 " (q 0 ,q 1 ,...,q n )、Q2 " (q 0 " ,q 1 " ,...,q m " )、Q3 " (q 0 " , q 1 " ,.. .,q l" )。

意味。

チューリングマシン M 1、M 2、および M3 にわたる分岐操作の結果はチューリングマシン M と呼ばれ、そのプログラムはマシン M 1、M 2、および M3 のプログラムから次のように取得されます。マシン M1 が書き込まれ、次にマシン M2 と M3 のプログラムが割り当てられます。マシン M1 の最終状態 q 1 でシンボル a i が観察された場合、制御はマシン M2 に移されます。シンボル q 1 がシンボル q 0" に置き換えられ、マシン M 2 が動作を開始します。マシン M 1 の最終状態 q 1 でシンボル a j が観察された場合、制御はマシン M 3 に転送されます。つまり、シンボル q 1 が置き換えられます。シンボル q 0" により、マシン M 3 が動作を開始します。マシン M1 および M2 のプログラム内の他のすべてのシンボルは変更されません。マシン M は、最終状態 q 1 で作業を完了します (結論として、マシン M の状態のエンドツーエンドの再番号付けを実行する必要があります)。

チューリングマシン M 1、M 2、および M3 での分岐演算の結果は次のように示されます。

2 文字のチューリングマシン (アルファベット 2 文字のチューリングマシン) の場合、任意のチューリングマシン M1、M2、および M3 での分岐操作は次のように表されます。

それらの。マシン M1 が状態 q 1 で動作しているときにシンボル a 0 が観察された場合、制御はマシン M2 に転送され、そうでない場合はマシン M3 に転送されます。

3. ループ動作。

M をアルファベット A« (a 0 ,a 1 ,...,a p ) と状態の集合 Q« (q 0 ,q 1 ,...,q n ) を持つチューリングマシンとする。

意味。

ループ操作の結果はチューリングマシンと呼ばれ、(i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3、...、n)

このプログラムは、コマンド q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. の結果の記号 q 1 を置き換えることによってマシン M のプログラムから取得されます。 .p、記号 q s が付いています。

2.4 チューリングマシンのバリエーション

チューリングマシンモデルは拡張できます。任意の数のテープとさまざまな制限のある多次元テープを備えたチューリングマシンを考えることができます。ただし、これらのマシンはすべてチューリング完全であり、通常のチューリングマシンによってモデル化されています。

このような等価性の例として、任意の MT を半無限テープ上で動作する MT に縮小することを考えてみましょう。

定理：どのチューリングマシンでも、半無限テープ上で実行される同等のチューリングマシンが存在します。

証拠：

Yu. G. Karpov の証明を考えてみましょう。この定理の証明は建設的です。つまり、任意のチューリングマシンに対して、宣言されたプロパティを持つ同等のチューリングマシンを構築できるアルゴリズムを提供します。まず、MT 作業テープのセルにランダムに番号を付けます。つまり、テープ上の情報の新しい場所を決定します。

写真1。

次に、セルの番号を付け直し、記号「*」が MT 辞書に含まれていないと仮定します。

写真1。

2.5 チューリングの計算可能性と決定可能性

再帰関数、チューリングマシン、または通常のマルコフアルゴリズムを使用して計算可能な関数のクラスが一致することが上記で証明されました。これにより、「計算アルゴリズム」という概念が記述方法に対して不変であると考えることができます。違いは、アルゴリズムオブジェクトの使用においてのみ観察されます。再帰関数の場合、オブジェクトが数値と数値関数であり、計算プロセスが重ね合わせ、再帰、最小化、反復の演算子によって指定される場合、チューリングマシンの場合、そのようなオブジェクトは外部メモリと内部メモリのアルファベットのシンボルであり、計算出口、遷移、ヘッドの移動などの処理をプロトコルで指定します。通常のマルコフアルゴリズムの場合、そのようなオブジェクトは単語またはシンボルのシーケンスであり、計算プロセスは、元のシンボルのシーケンスの構成と構造を目的の結果に変更する置換ルールまたは積によって指定されます。

算術 (数値) 関数は、値の範囲が集合 N の部分集合であり、その定義域が集合 N の要素である関数です。

アルゴリズムの問題の典型的な状況は、引数 x 1、x 2 の整数値に応じて、数値関数 f(x 1, x 2, ..., x n) を計算するアルゴリズムを見つける必要がある場合です。 , ..., x n。

関数の値を計算するために引数の任意の値のセットを許可する (または関数が特定のセットで定義されていないことを示す) アルゴリズムがある場合、関数 f:N n →N computable と呼びます。計算可能関数の定義にはアルゴリズムの直観的な概念が使用されるため、「計算可能関数」という用語の代わりに「直観的計算可能関数」という用語がよく使用されます。したがって、問題に対応する算術関数が直観的に計算可能であれば、質量問題には解決策があります。

関数 f(x 1 , x 2 , …, x n) は、与えられた値 k 1 , k 2 , …, k n 引数に対して関数 f(k 1 , k 2 , …, k n) 既存の機械的手順 (アルゴリズム) を使用します。

アルゴリズムの概念を明確にする代わりに、「計算可能な関数」の概念を明確にすることを検討できます。通常、それらは次のスキームに従って進行します。

1. 正確に定義された関数のクラスが導入されます。

2. このクラスのすべての関数が計算可能であることを確認します。

3. 計算可能な関数のクラスが導入された関数のクラスと一致するという仮説 (テーゼ) を受け入れます。

関数を計算するアルゴリズムがある場合、その関数は計算可能と呼ばれます。「計算可能性」はアルゴリズム理論の基本概念の 1 つであり、計算される関数やアルゴリズムに対して不変です。計算可能な関数とアルゴリズムの違いは、関数の説明と、独立した引数の値を考慮してその値を計算する方法の違いです。

チューリングの論文。チューリングマシンを使用すると、直感的なアルゴリズムを実装できます。

チューリングの理論から、アルゴリズムの問題が発生した場合、チューリングマシンの構築、つまり十分に形式化されたアルゴリズムの概念に基づいて問題を解決する必要があることがわかります。さらに、アルゴリズムの問題では、アルゴリズムの構築についてではなく、特別に構築された関数の計算可能性について話していることがよくあります。

このような場合、アルファベット (0,|) を使用すれば十分であることに注意してください。0 は空文字です。たとえば、0 を含む自然数は、このアルファベットで次のようにエンコードされます。 1 - ||; 2 -

N - ||…| (n + 1 回)。部分数値 n ローカル関数 f(x1, x2, ..., xn) は、次の意味で計算するマシン M が存在する場合、チューリング計算可能と呼ばれます。 1. 引数値のセットの場合は関数 f の定義領域に属し、次にマシン M が構成 0 |x1+1 0 |x2+1 ... 0 |xn q1 | で作業を開始します。ここで、|x = ||... | (x 回) となり、右端のシンボルが認識されて停止し、最終的に 0|yq0 | (y = f(x1, x2, …, xn)) という構成になります。 2. 引数の値のセットがが関数 f の定義領域に属していない場合、マシン M は初期構成で作業を開始し、際限なく動作します。つまり、最終状態に到達しません。チューリングマシンは、アルゴリズムの正確な正式な定義です。この概念を使用すると、アルゴリズムの問題の可解性または不可解性を証明できます。単一クラスの問題を解決できる計算アルゴリズムが見つかった場合、その問題はアルゴリズムで解決可能な問題であると言われます。言い換えると、前提条件計算の計算可能性または有効性は、アルゴリズムの解決可能性です。この意味で、「決定可能性」という概念はアルゴリズム理論における基本概念でもあります。 3 種類のモデルを分析すると、離散性、決定論、質量特性、有効性の基本特性は、どのモデルでも変化しないことがわかります。さまざまな方法で説明: 離散性プロパティ: アルゴリズムは、段階的に実行される個々の基本アクションで構成されます。アルゴリズムプロセスを構成する一連の基本ステップは有限であり、数えることができます。決定的特性: 各ステップの後に、アルゴリズムプロセスの次のステップをどのように、どの順序で実行するかについて正確な指示が与えられます。質量プロパティ: アルゴリズムの使用は、特定のタイプおよび特定のクラスの問題の多くのアルゴリズムオブジェクトに対して許可されます。有効性の特性: 望ましい結果が示された有限数のステップの後に、アルゴリズムプロセスを停止することが必須です。しかし、この命題はチューリングの計算可能性の正確な概念と直感的に計算可能な関数の不正確な概念と結びついているため、証明することはできません。

自己適用の問題

チューリングマシンの定義によれば、これはトリプルです。 T= ここで、あ-アルファベット、 Q –マシンの内部状態、 Q-あるマシンを別のマシンから区別するプログラム。一般的なケース (すべてのマシンの場合) では、プログラムは次のようになります。

P: 気ある あ、jある ® qrある としてある セントある 、a = 1、2、…、k 、どこ S1- R、 S2-L, S3- C . (*)

この場合、いくつかの共通のアルファベットがあると仮定できます。あ0そして Q0、文字が書かれているあるそして q すべてのチューリングマシンに対応。それから記号 気ある, あ、jああ、 qrある, としてある, セントあるアルファベットの記号ですあ0そして Q0.

このアプローチにより、すべてのチューリングマシンに番号を付けることができます。つまり、各マシンには、このマシンに固有の特定の番号 (コード) が割り当てられ、それによって他のマシンと区別できます。ここでは、番号付け方法の 1 つを検討します。

チューリングマシンのゴデル式番号付け。させて p1、p2、p3 , ... - 昇順に並べられた一連の素数 (2、3、5、7、11、13、... など)

プログラム付きチューリングマシン番号 (*)着信番号

n(T) = .

例

機能を実装するマシン S(バツ)= x + 1 、アルファベットのプログラムがあります {0,  } 。という事実を考慮したこのプログラムの数 0 = 0 , 1= | 数字があります:。

n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 。

明らかに、すべての自然数がチューリングマシン数であるわけではありません。一方、次の場合は、 n – 特定のマシンの番号 (通常はアルファベット) であれば、そのプログラムはこの番号から一意に復元できます。

車 T、という単語に当てはまります n(た)(つまり、自分の番号のコードに)、 自己適用と呼ばれる .

自己適用可能なマシンと非自己適用可能なマシンの両方を構築することが可能です。たとえば、指定された例のマシンは自己適用可能です。車 T、プログラムの右側の部分 (表の本文) に停止記号がなく、どの単語にも適用できないため、単語にも適用されません。 n(た).

自己適用問題は次のとおりです。任意のチューリングマシンが与えられた場合に、それが自己適用可能かどうかを決定するアルゴリズムを示します。

チューリング理論によれば、そのようなアルゴリズムはチューリングマシンの形で求められるべきである。このマシンはすべてのチューリングマシンの数値コードに適用できる必要があり、テスト対象のマシンのコードの処理結果に応じて、異なる最終構成が得られます。

たとえばこの車を考えてみましょう Tコードに適用される n(T * ) 。車なら T * 自己適用、その後最終的なマシン構成 Tのように見える ああ」 q0 | B」、そして車の場合 T * 自己適用できない場合、マシンの最終構成 Tのように見える ああ」 q0 0B ". ここ a"、B"、a"、B"- 言葉。

定理自己適用性問題はアルゴリズム的に決定不可能です。つまり、上記の意味でこの問題を解決するチューリングマシンは存在しません。

定理から、一般的なアルゴリズムは存在しないことがわかります。問題解決者自己適用性。特定の特殊な場合には、そのようなアルゴリズムが存在する場合があります。

この定理の結果を使用して、最初の単語への適用可能性の問題の決定不可能性を証明しましょう。

頭語の適用性の問題 は次のとおりです: マシンに従ってアルゴリズムを作成します。 Tそしてその言葉バツインストールする、該当するマシン Tところでバツそうでない場合（そうでない場合は、停止の問題が発生します）。

チューリングマシンの観点から見ると、自己適用性問題の定式化と同様に、この問題は次のように定式化されます。次の形式のすべての単語に適用できるマシンを構築することは可能ですか? n(T)0 バツ 、どこ T任意のマシン、バツ – 任意の単語、およびマシンの場合 Tという言葉に当てはまるバツ ああ」 q0 |B" , そして車の場合 Tその言葉には当てはまらないバツ、最終的な構成につながります ああ」 q0 0B」 . ここ a"、B"そして a"、b"- 任意の言葉。

定理最初の単語への適用性の問題はアルゴリズム的に決定不可能です。つまり、上記の意味でこの問題を解決するチューリングマシンは存在しません。

自己適用性の問題について上で述べたように、最初の準備ステップは番号付けです。したがって、以下では、アルゴリズムとその 3 つの主要なタイプのアルゴリズムモデルについて、この問題を一貫して検討し、解決します。

アルゴリズムの番号付け

アルゴリズムの番号付けが役割を果たします重要な役割彼らの調査と分析では。任意のアルゴリズムは有限単語 (あるアルファベットの記号の有限シーケンスとして表される) として指定でき、有限アルファベット内のすべての有限単語のセットは可算であるため、すべてのアルゴリズムのセットも可算です。これは、自然数のセットとアルゴリズムのセットの間に 1 対 1 のマッピングが存在すること、つまり、各アルゴリズムに数値を割り当てる機能が存在することを意味します。

アルゴリズムの番号付けは、アルゴリズムで計算可能なすべての関数の番号付けでもあり、どの関数も無限の数を持つことができます。

番号付けの存在により、数値と同じ方法でアルゴリズムを操作できるようになります。番号付けは、他のアルゴリズムと連携して動作するアルゴリズムを研究する場合に特に役立ちます。

初期オブジェクト X のセットと目的のオブジェクト Y のセットに関する特定の質量問題があるとします。質量問題の解が存在するためには、セット X と Y の要素が構成的なオブジェクトである必要があります。したがって、これらのセットの要素には自然数で番号を付けることができます。 x∈ X を初期オブジェクトとし、その数を n(x) で表します。元のオブジェクト x に対する質量問題で、数値 n(y) の目的のオブジェクト y∈ Y を取得する必要がある場合、f(n(x))=n となる算術関数 f: Nn →N を定義します。 (y)。

質量問題の算術関数を構築する例として、質量問題を考えてみましょう。

1. 自然数の配列 ] が与えられた場合、自然数 2x1, 3x2,... p(n)xn を割り当てることができます。ここで、p(n) – n番目の素数番号。長さ 5 の配列の例を見てみましょう。

] 2x13x25x37x411x5。

この番号付けは、算術関数 f を定義します (たとえば、f(73500) = f(22315372110) = 20315272113 = 4891425)。

2. あらゆる有理数には何らかの自然数があります。問題に必要なオブジェクトのセットの番号付けは簡単です。

(「はい」、「いいえ」) a (1, 0)。特定の質量問題に対して、前の例の手法を使用して 1 つの引数の算術関数を構築することも、3 つの引数 (元のトリプルの要素の 3 つの数) の関数を検討することもできます。

3. プログラムテキストの番号付けは次のように実行できます。どのプログラムでも、256 進数体系で数値を記録していると認識できます (プログラムの記録に ASCII テーブル文字が使用された場合)。

質量問題から算術関数への移行により、質量問題に対する解の存在の問題を存在の問題に還元することができます。効果的な方法算術関数の値をその引数から計算します。

数値セットの番号付け

アルゴリズムの理論では、複数の変数の関数の研究を 1 つの変数の関数の研究に減らすことを可能にする手法が普及しました。これは、数値の集合の番号付けに基づいており、数値の集合とその数値の間には全単射の対応があり、数値の集合からその数値を決定する関数、および数値の集合自体の数値からその数値を決定する関数は一般に再帰的です。たとえば、2 つの独立変数 (x, y) を含む関数の場合、このマッピング h(x, y) は次のようになります。

写真1。

ペア (x, y) が部分的に順序付けされたセット N(2) を形成するとします。 h(x, y) = n とすると、逆マッピングが行われます: x = h -1 1 (n) および y= h -1 2 (n)、つまり h(h -1 1 (n), h -1 2 (n)) = n。これにより、任意のペア (x, y) の数値 n を計算したり、逆に数値 n を使用して x と y の値を計算したりすることができます。

これらのルールを使用すると、トリプルの番号付け h 2 (x, y, z) = h(h(x, y), z) = n を計算でき、逆に、トリプルの数によって、次の値を計算できます。 x、y、z。たとえば、h 2 (x, y, z) = n の場合、z= h -1 2 (n)、y= h -1 2 (h -1 1 (n))、x= h -1 1 ( h -1 1 (n))、h 2 (x、y、z) = h(h(h -1 1 (h -1 1 (n))、h -1 2 (h -1 1 (n)) )、h -1 2 (n))。トリプル (x, y, z) は、部分的に順序付けされたセット N(3) を形成します。同様に、任意の数の数値については次のようになります。

h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn)。 h n-1 (x1, x2,…, xn)=m の場合、xn = h -1 2 (m)、x n-1 =h -1 2 (h -1 1 (m))、... ................................................、x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...))、x1 = h -1 2 (h (...h (m)...))。

集合 N (1) 、 N (2) 、...、 N (i) 、...、 N(n の番号付けを持ち、ここで N (i) は数値の集合 (i) です。任意のセット番号 M = N (1) N (2) ... N (i) .. N(n) を組み合わせた番号付けを確立することができます。ここで、M N です。任意の n N に対して、 h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1)。

h(x ,1x ,2..., x)n = m の場合、 h n−1 (x ,1x ,2..., x)n = h -1 1 (m)、n= h -1 2 (m)+1。上記の式を使用すると、x1、x2、…、xn の値を復元できます。

理論情報

MT を記述するための上記の方法は、実際には単純なアルゴリズムにのみ使用でき、そうでない場合は記述が煩雑になります。複雑なアルゴリズム用のチューリングマシンは、既存の基本 MT を使用して構築でき、この構築はと呼ばれます。 構成MT.

MT 合成の 4 つの主な方法について説明します。

連続合成（重ね合わせ）。

並列構成。

分岐

1. チューリングマシンの逐次構成

連続合成または 重ね合わせチューリングマシンや

そして
アルファベットであ、それは車と呼ばれています M、関数を計算します
.

一連の構成は次のように表されます。

そして指定されている
または
.

2. チューリングマシンの並列構成

並列構成 車
そして
、辞書関数の計算
そして
アルファベットであそしてで、したがって、マシンは次のように呼ばれます。 M、辞書関数を評価します。ここに標識があります並列 MT 合成で単語を区切るために使用されます。

並列構成MT
そして
は次のように描かれています。

そして指定されています:
.

実際、2 つの MT の並列構成は、異なるアルファベットの 2 つの単語で構成される単語を入力として受け取り、同じく 2 つの単語で構成される単語を出力します。は、同時に独立して動作する 2 台の機械を表します。並列構成を実現するには、2 階建てのベルトを備えた機械が使用されます。

ダブルデッキベルトマシンは次のように動作します。

1) 単語テープの2階で書き換えられ、1階で消去され、

2) 計算された
1階に、

3) 計算された
二階にあります

4)
おそらくシフトを伴って 1 階に書き直されました。

2 層テープを使用した MT コマンドは次のように記述されます。

どこ
– 1階と2階にそれぞれ書かれた手紙。単語の長さを表してみましょう
、それぞれ、
.

2 階建てのテープを使用してチューリングマシンの動作を実証してみましょう。一般に、単語の長さは、
そして
は互いに一致しませんが、イメージを簡単にするために、それらが等しいと仮定します。次に、2 階建てテープを使用した MT でのポイント 1) ～ 4) の実装は、次のように実行されます。

並列合成を実装するには n チューリングマシンが使われている n– 床テープ。

3. チューリングマシンの構成における分岐または条件遷移

チューリングマシンが与えられた場合
そして
、辞書関数の計算
そして
、そして車
、いくつかの述語を評価します P( ) 復元あり（単語を消さずに）  ), その後、チューリングマシンを構築して分岐を実装できます。
、関数を計算します。

構成図におけるチューリングマシンの分岐は次のように表されます。

そして指定されている
、ここ
- 機械の動作の結果
、述語の場合は値「1」を受け取ります P( )= ”真実” 述語の場合は「0」 P( )= “間違い” ,
– 入力単語のコピーを実装するチューリングマシン
.

4 . チューリングマシンの構成におけるサイクル

サイクル構成では、MT は分岐と同じ原理に従って実装されます。

" さよなら P( )= ”真実” 、満たす
»,

どこ  – 最初の実行前にテープ上の単語
そして次の実行後 .

サイクルを表すために、いくつかの表記法を導入します。

– 述語の計算を実装するチューリングマシン P( ) ;

–MT、入力単語のコピーを実装します。
;

–MT、ループ内で実行され、実装されます。
;

–MT、ループを抜けて実装するときに実行されます。
.

次に、チューリングマシンの周期的な構成、つまりサイクルは次のように表すことができます。

チューリングマシン構成を使用したプログラミング:

1) ブロックが基本 MT に対応するような詳細レベルの複雑なアルゴリズムのブロック図の構築。

2) 単純なブロックを実装する基本 MT の構築。

３）基本ＭＴを組み合わせてＭＴ構成にする。

例。を実装する MT コンポジションを構築する
.

– 入力単語のコピーを実装するチューリングマシン。

–MT、定数ゼロを設定する機能を実装します。

–MT、復元を伴う述語の計算
;

– 選択機能を実装したMT -その議論から引数。

–MT、引数削減機能を実装単項コードでは 1 ずつ (左端の文字を消去)。

– MT。単項コードで 2 つの数値の加算を実行します。

いずれの場合も、アルゴリズムの実行開始時に入力データの正しさをチェックする必要があることに注意してください (たとえば、除算中の引数が 0 に等しいかどうか)。

図1.6

図 1.6 では次の表記が使用されています。

T 1、T 2 - チューリングマシン。

ST 1、ST 2 - それぞれマシン T 1 および T 2 のコマンドシステム。

x - マシン T 1 の初期情報。

T 1 (x) - マシン T 1 の操作の結果。

T 2 (T 1 (x)) - マシン T 2 の操作の結果。

例として、2 台のマシンの構成を考えてみましょう。1 台目はコピー操作を実行し、2 台目は単項コードで数値を加算する操作を実行します。マシンの組み合わせの図と、得られた結果を含むテープの例を図 1.7 に示します。

図1.7

図 1.7 に示す構成では、既知の複写機や加算機を使って数値を 2 倍にする演算を実行できます。したがって、一連の特定の演算 (算術演算など) を解決するためのチューリングマシンのアルゴリズムを構成した後、より複雑な問題を解決するためのチューリングマシンの構成を構成できます。この場合、一般的なアルゴリズムの開発は、チューリングマシンで実行するアルゴリズムがすでに知られている操作からコンパイルすることになります。このアプローチは、プログラミングにおけるプロシージャや関数の使用に似ています。

ただし、マシン合成を使用するには、基本的な演算を実行するためのアルゴリズムが既知であり、そこから一般的なアルゴリズムが構成されることが前提となります。したがって、任意の問題を解決する場合、このアプローチでは、新しいアルゴリズムを作成し、それに応じて異なる制御ユニットを備えたチューリングマシンを開発する必要性が排除されません。汎用チューリングマシンを使用することで、制御ユニットの構造を変更することなく任意のアルゴリズムを実装することが可能です。

1.2.2.ユニバーサルチューリングマシン

何らかのチューリングマシンが与えられている場合 (つまり、入力、出力信号、および状態のアルファベット、ヘッドの初期位置とマシンの初期状態がわかっているほか、マシンの動作のテーブルと初期情報が記録されたテープがわかっている場合) ) の場合、このマシンが意図しているすべての情報変換を段階的に手動で実行できます。実際、この場合、チューリングマシンのシミュレーションが実行されます。

チューリングマシンのモデル化時に実行される操作を分析すると、モデリングは最終的に各ステップで次のアクションを繰り返すことになることがわかります。

Äヘッドが置かれているテープセルから文字を読み取ります。

Äマシン操作テーブルでコマンドを検索します。検索は、マシンの現在の状態と読み取られたシンボルの値に基づいて実行されます。

Äテープに書き込むコマンドからシンボルを選択し、記録します。

Äコマンドからヘッド移動シンボルを選択して移動します。

Ä コマンドから新しいマシン状態を選択し、現在の状態を新しい状態に変更します。その後、次のステップに進み、これらのステップを繰り返します。

S.U.

図1.8

これらの基本的なアクションの性質は、元のマシンの動作をシミュレートする他のチューリングマシンを使用してすべてを実行できるようなものです。モデリングの本質は図 1.8 で説明されています。

マシン T がコマンドシステム ST を持ち、情報 X を含むテープを処理する場合、その動作は、独自のコマンドシステム SU を持つ別のマシン U によってシミュレートできます。マシン U の入力をシミュレートするには、情報 X を含むテープを提出するだけでなく、 , コマンドシステム（作業テーブル）STも含まれます。このコマンド体系は、元の情報と同じテープに記録することができます。

図1.9

重要な機能モデリングマシンの特徴は、そのコマンドシステム SU (およびそれに応じて制御ユニットの構造) が、シミュレートされたマシン T の動作アルゴリズムに依存しないことです。他のチューリングマシンの動作をシミュレートできるチューリングマシンは、ユニバーサルと呼ばれます。ユニバーサルチューリングマシン (UMT) の構造の変形例を図 1.9 に示します。

UMT テープは、データゾーン、モードゾーン、コマンドゾーンの 3 つのゾーンに分割されています。

データゾーンには、シミュレートされたチューリングマシンによって処理される必要がある初期情報が含まれています。同じゾーンに、UMT 操作の結果が記録されます。

モードゾーンは、現在の状態 Q t と、特定のサイクルでデータゾーンセルから読み取られる現在の入力シンボル X t を記録します。

コマンドゾーンには、シミュレートされたマシンのコマンドシステムが含まれています。コマンドはグループに編成されています。最初のグループには記号 Q 0 で始まるコマンドが含まれ、2 番目のグループには記号 Q 1 などで始まります。各グループ内で、コマンドはシンボル X t の値によって順序付けされます。したがって、テープ上のコマンドは、シミュレートされたマシンの動作テーブルに配置されているのと同じように配置されます。

テープからの情報の読み取りとテープへの書き込みは、G d - データヘッド、G r - モードヘッド、G k - コマンドヘッドの 3 つのヘッドを使用して実行されます。各ヘッドはベルトの独自のゾーンに沿って移動できます。

UMT が動作を開始する前に、関連情報をテープの各ゾーンに記録する必要があります。ヘッドは各ゾーンの左側のシンボルの上に取り付ける必要があります。

UMT の動作はサイクルで発生し、各サイクルでシミュレートされたマシンの 1 つのコマンドの実行がシミュレートされます。 UMT の動作グラフを図 1.10 に示します。

図1.10

図 1.10 では次の表記が使用されています。

Q G to P (G to L、G r P、G r L、G d P、G d L) - ヘッドの 1 つを移動します。

右か左;

Q (G k)、(G d)、(G r) - ヘッドの 1 つによって読み取られた情報。

Q (G k) à (G r) - コマンドヘッドによるデータの読み取りとこのデータの書き込み

モードヘッドを使用してテープモードゾーンに転送されます。

Q a は値 1 を取る補助変数です。

頭部 Гк と Гр によって読み取られる文字が一致するかどうか。

Q in は値 1 を取る補助変数です。

現在の状態 (Q t) と最終状態 (Q z) のシンボルが一致するかどうか

Q p - コマンドが先頭の場合に値 1 を取る信号

左への移動は指揮区域の境界を越えた。

UMT の動作の各サイクルでは、次の手順が実行されます。

コマンドゾーンを検索します。

ゾーン内でチームを検索します。

コマンド実行のシミュレーション。

コマンドゾーンの検索は、モードゾーンからの現在の状態 Q t とコマンドゾーンの最初のコマンドの開始時に記録された状態 Q i を比較することで始まります。これらの状態が等しくない場合、コマンドヘッドは次のコマンドの先頭に移動し、ヘッドの 5 ステップが右に実行されます (状態 U 0 ～ U 4)。シンボル Q t と Q i が一致する場合、コマンドの先頭は目的のゾーンの最初のコマンドの先頭にあります。次に、モードゾーンの Q t および X t シンボルに対応するコマンドの検索が開始されます。これを行うには、モードヘッドがモードゾーンのシンボル X t の上に配置され、コマンドヘッドが現在のコマンドのシンボル X i の上に配置されます。

ゾーン内のコマンドの検索は、コマンドゾーンの検索と似ています。この場合、文字 X t と X i が比較されるまで、コマンドヘッドは右に 5 ステップ (状態 U 5 ～ U 9) に移動します。

コマンドの実行（状態 U 10 ～ U 17）は、コマンドヘッドを 1 ステップ右に移動することから始まり、その後、見つかったコマンドから読み取られたシンボル Y t が、コマンドの代わりにデータヘッドを使用してデータゾーンに書き込まれます。以前に読み取られたシンボル X t 。コマンドヘッドの次のステップを右に進めた後、見つかったコマンドからデータヘッド移動シンボル（Ｙ・ｄ）を読み取り、このシンボル（Ｒ、Ｌ）に従ってデータヘッドを移動する。その下には、次に処理されるシンボル (X t +1) があり、モードヘッドを使用して、次のサイクルを準備するためにモードゾーンに書き込まれます。次に、次の状態 Q t +1 (状態

U14、U15）。状態Ｕ１６では、解決を終了するための条件がチェックされる。次の状態のシンボルがモデル化されたマシン (Q z) の最終状態のシンボルと一致しない場合、問題の解決は完了せず、状態 U 17 でコマンドヘッドは元の位置に移動します (最初のゾーンの最初のコマンドの先頭まで）。この場合、UMT は次のサイクルを実行する準備ができています。次のコマンドの実行をシミュレートします。

シンボル Q t と Q z が一致すると、問題の解決は終了し、UMT は最終状態 U z になります。

UMT の動作プロセスを分析すると、UMT の動作アルゴリズムは、シミュレートされたチューリングマシンがどのような特定の問題を解決するかに依存しないという重要な結論を導き出すことができます。したがって、UMT コントロールユニットの構造は、異なるマシンをモデル化する場合でも変わりません。解決されるタスクには依存しません。このため、UMT は真の万能マシンであり、その構造を変更することなくあらゆるアルゴリズムを実行できます。

次の UMT コマンドを選択して実行するプロセスはテープセルの順次列挙に関連するため、UMT の問題を解決するには時間がかかりすぎます。したがって、チューリングマシンは汎用のものを含めて構築されることはありませんでしたが、その中に現代のコンピューターの類似物を見るのは難しくありません。したがって、UMT コマンドゾーンのコマンドシステムはマシンプログラムに似ており、シンボル Q t と X t のペアがマシンコマンドのアドレスの役割を果たします。

ただし、チューリングマシンはアルゴリズムを記述するための非常に便利な手段であり、アルゴリズム理論で広く使用されています。

コントロールの質問

ü1.チューリングマシンの構成は何ですか?

ü2.チューリングマシンの構成は何ですか?

ü3. 1 つのチューリングマシンで別のマシンの動作をシミュレートできますか?

チューリング？

ü4.この場合、どのようなアクションが実行されますか?

ü5.万能チューリングマシンの構造を説明してください。

ü6.UMTテープの各領域にはどのような情報が記録されていますか？

ü7.チューリングマシンの指令体系は何ですか?

ü8.UMT ワークサイクルにはどのようなステップが含まれますか?

ü9.「コマンドゾーンの検索」ステップの内容を説明してください。

ü10.「コマンド実行」ステップの内容を説明してください。

ü11.情報処理プロセスはどのような機能を使用していますか

図はグラフのように見えます。

マシンテーブル値

表1

チューリングマシンでの一部の操作

チューリングマシンの動作は、入力データとコマンドシステムによって完全に決定されます。ただし、特定のマシンが問題をどのように解決するかを理解するには、原則として、そのマシンに与えられた種類の意味のある説明が必要です。。これらの説明は、多くの場合、ブロック図とチューリングマシンの操作を使用することで、より形式的かつ正確に行うことができます。関数の構成を思い出してください。
そして
呼び出された関数
を使用すると得られます。計算結果に。するために
これで決まった、それは必要十分ですに決定されました
、A に決定されました .

定理1。もし
そして
チューリングは計算可能か、そしてその合成
チューリング計算も可能です。

させて - 計算する機械、A - 計算する機械、およびそれらの状態のセット
そして
.

車の遷移図を作成してみよう図からそして次のように: 最初の頂点を特定します
機械図終端頂点あり
機械図 (コマンドシステムの場合、これはコマンドシステムが指揮系統に割り当てられるそしてこのために
チームでと置換する
）。 () を使用して図を取得します。
) と述べています。初期状態発表します
そして最後
。表記を簡単にするために、次のように仮定します。そして 1 つの変数の数値関数。

させて
決定した。それから
そして

。車同じ一連の構成を実行しますが、代わりに
で開催されます
。この構成は、マシンの標準的な初期構成です。、それが理由です
。でも、どのチームもそうなので、に含まれた、それ

したがって
。もし
が定義されていない場合、または止まらないので車は止まらないでしょう。それで車は計算します
.

こうして作られた機械はそれをマシンの構成と呼びますそしてそして指定する
（または ())、ブロック図でも示されています。

チューリングマシンの構成

させて ,,- 同じ外部アルファベットを持つ 3 つのチューリングマシン
、内部状態のアルファベット付き
,
,
とプログラム ,
,
それぞれ。

構成
車そして呼ばれた車T 、そのプログラムは集合の和集合です
そして

、どこ
から受信した一連のコマンドを示します。すべてを置き換えるの上 .

チューリングマシンからの分岐

分岐機,,による
、象徴的に

呼ばれた車T 、そのプログラムは次のように取得されます。チームは除外されます
そして
のために
、結果のセットが呼び出されます ; それから。

万能チューリングマシン

チューリングマシンのコマンドシステムは、特定のデバイスの動作の記述としても、プログラムとしても解釈できます。明確に結果につながる一連の指示。例を分析するとき、無意識のうちに 2 番目の解釈が受け入れられます。私たちは、あらゆるチューリングマシンの動作を再現できるメカニズムとして機能します。誰もがこれを同じように行うだろうという確信 (間違いを犯さなければ、ちなみにチューリングマシンが動作するときにもそれが想定されます) は、本質的にチューリングマシンの動作を再現するアルゴリズムの存在に対する自信です。与えられたプログラムに従ってマシンを動かします。コマンドシステム。実際、そのようなアルゴリズムを口頭で説明するのは難しくありません。その主なアクションは周期的に繰り返され、次の内容で構成されます: 「現在の構成の場合」
コマンド体系の左側でコマンドを検索します
。このコマンドの右側が次の形式の場合、
、現在の構成に置き換えます
の上
(構成が判明しました
); 右側に次のような形がある場合
、交換してください
の上
。アルゴリズムの口頭での説明は不正確である可能性があるため、形式的に説明する必要があります。チューリングマシンは現在、アルゴリズムの概念を形式化したものとして議論されているため、説明された再生アルゴリズムを実装するチューリングマシンを構築するという問題が生じるのは当然です。 1 つの変数の関数を計算するチューリングマシンの場合、この問題の定式化は次のようになります。チューリングマシンを構築する、2 つの変数の関数を計算し、どのマシンでもコマンドシステム付き
、もし
定義されている（つまり、マシンが初期データで停止する）そして
止まらない場合
止まらない。このプロパティを持つマシンをすべて呼び出します万能チューリングマシン。この定式化を任意の数の変数に一般化することは難しくありません。

汎用マシンを構築するときに発生する最初の問題、という事実によるものです。他のチューリングマシンと同様に、固定されたアルファベットが必要です
固定された一連の状態
。したがって、コマンドシステムは、
および任意のマシンの初期データ単に機械のベルトに転写することはできません (いつも車があります、アルファベット
そして
どちらが力に優れているか
そして
または単に一致しない）。

解決策は、次の文字を使用することです。
そして
アルファベットの記号でエンコードされる
。させて
,
。私たちは常に次のように仮定します
そして
(これら 2 つの記号は、数字を扱うマシンのアルファベットには常に含まれています)。コードを表しましょうそしてを通して
そして
そしてそれらを次のように定義します
; 他の誰かのために
; 最終状態用

、もし

。コード
この車の場合常に長さ (形式) があります
、およびコード
- フォーマット。記号 ,
入りましょう
、つまり
,
,
。文字コード、この単語を構成する文字のコードによって形成され、次のように表します。
。したがって、万能機械の問題の定式化の最終的な改良は、つまり、どんな車でもそして言葉アルファベット
.

万能チューリングマシンの存在は、命令システムが
どの車でも元のデバイスの動作の説明として解釈することができます。、または汎用マシンのプログラムとして。制御システムを設計する現代のエンジニアにとって、この状況は自然なことです。彼は、あらゆる制御アルゴリズムが、適切な回路を構築することによってハードウェアで実装できること、またはユニバーサル制御コンピュータプログラムを作成することによってソフトウェアで実装できることをよく知っています。

ただし、普遍的なアルゴリズムデバイスのアイデアは、その実装のための現代の技術的手段（電子工学、物理学）の開発とはまったく無関係であることを認識することが重要です。固体など）、技術的なものではなく、数学的な事実であり、技術的手段から独立した抽象的な数学用語で記述され、さらに、非常に少数の非常に初歩的な初期概念に基づいています。特徴的なのは、アルゴリズム理論の基礎的な著作（特にチューリングの著作）が、現代のコンピュータが誕生する前の 30 年代に登場したことです。

この二重の解釈により、2 つのエンジニアリング実装オプションの主な長所と短所が抽象レベルで保持されます。特定の車はるかに高速に動作します。また、機械の制御装置非常に面倒です (つまり、状態とコマンドの数が多い)。ただし、その値は一定であり、一度構築されると、任意の大規模なアルゴリズムを実装するのに適しています。必要なのは大量のテープだけであり、当然、制御装置よりも安価で構造が簡単であると考えられます。さらに、アルゴリズムを変更する場合、新しいデバイスを構築する必要はなく、新しいプログラムを作成するだけで済みます。

ある	b	*	私

			-
			-
			-
		-


		*	私
			-
			-
		-

チューリングマシンの構成例。 チューリングマシン上の関数の適切な計算可能性

理論情報

1. チューリングマシンの逐次構成

2. チューリングマシンの並列構成

3. チューリングマシンの構成における分岐または条件遷移

マシンテーブル値

チューリングマシンでの一部の操作

チューリングマシンの構成

チューリングマシンからの分岐

万能チューリングマシン

チューリングマシンの構成例。チューリングマシン上の関数の適切な計算可能性