branch - 条件分岐はチューリング完全性の要件ですか?

Question

私はウェブを検索してきましたが、やや矛盾した答えを見つけています。一部の情報源は、条件付き分岐と無条件分岐の両方がある場合にのみ、言語/マシン/あなたが持っているものはチューリング完全であると主張します(これは一種の冗長だと思います)。必要とされている。

ドイツのZ3とENIACについて読むと、ウィキペディアは次のように述べています。

ドイツの Z3 (1941 年 5 月に稼働中) は、コンラート ツーゼによって設計されました。これは最初の汎用デジタル コンピューターでしたが、すべての機能にリレーを使用していたため、電子的ではなく電気機械的でした。バイナリ演算を使用して論理的に計算しました。パンチテープでプログラムできましたが、条件分岐がありませんでした。チューリング完全性のために設計されたわけではありませんが、1998 年に発見されたように、偶然にもそうでした (ただし、このチューリング完全性を利用するには、複雑で巧妙なハックが必要でした)。

正確には、どのような複雑で巧妙なハックですか?

R. Rojas による 1998 年の論文 Abstract にも次のように記載されています (この論文はまだ読んでいないことに注意してください。IEEE からの抜粋です)。

1938 年から 1941 年の間に Konrad Zuse によって構築されたコンピューティング マシン Z3 は、パンチ テープにコード化された浮動小数点算術演算 (加算、減算、乗算、除算、および平方根) の固定シーケンスのみを実行できました。コンピューティングの歴史の観点から興味深い質問は、これらの操作が普遍的な計算に十分かどうかということです。この論文は、実際に、これらの算術命令を含む単一のプログラム ループで、特定の有限サイズのテープを使用する任意のチューリング マシンをシミュレートできることを示しています。これは、条件付き分岐と間接アドレス指定を純粋に算術的にシミュレートすることによって行われます。したがって、Zuse の Z3 は、少なくとも原則として、制限されたアドレス空間を持つ今日のコンピューターと同じくらい普遍的です。

要するに、SOers の皆さん、チューリング完全性のために正確に必要とされるタイプの分岐は何ですか? goto無限のメモリを想定すると、またはjmp分岐構造のみ (ifまたは構造なし)を持つ言語は、jnzチューリング完全と見なすことができますか?

Answer 1

元のロハスの論文はここにあります。基本的な考え方は、Z3 は無条件の単一ループ (説明テープの両端を接着することによる) のみをサポートするというものです。すべてのコード セクションを次々とループに入れ、実行するセクションを決定する変数 z を使用することで、条件付き実行を構築します。セクション j の先頭で、次のように設定します。

 if (z==j) then t=0 else t=1

a = b op c次に、このセクションの各割り当てを読み上げます

 a = a*t + (b op c)*(1-t)

(つまり、アクティブなセクションを除いて、各割り当てはノーオペレーションです)。現在、これにはまだ条件付きの割り当てが含まれています: z==j を比較する方法は? 彼は、z の 2 進数表現 (z1..zm) を j の否定された 2 進数表現 (c1..cm) と共に使用し、次に計算することを提案しています。

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

この積は、c と z がすべてのビットで異なる場合にのみ 1 になります。これは、z==j の場合にのみ発生します。z への代入 (これは基本的に間接ジャンプです) は、z1..zm にも代入する必要があります。

Rojas はまた、Conditional Branching is not Necessary for Universal Computation in von Neumann Computersも書いています。そこで彼は、メモリからチューリング命令を読み取り、それに応じてジャンプするようにプログラムを変更できるように、自己変更コードと相対アドレス指定を備えたマシンを提案しています。別の方法として、彼は、LOAD(A)、STORE(A)、INC、および DEC のみを使用するバージョンで、上記のアプローチ (Z3 用) を提案しています。

Answer 2

gotoまたはのアドレスを計算できる場合はjmp、任意の条件をシミュレートできます。これを時々使用して、ZXBasicで「ONxGOTO a、b、c」をシミュレートしました。

「true」の数値が1で「false」が0の場合、次のような構造になります。

if A then goto B else goto C

と同じです：

goto C+(B-C)*A

したがって、はい、「計算されたgoto」または自己変更機能を使用すると、gotoまたはjmpを条件付きとして機能させることができます。

Answer 3

算術式しかない場合は、算術演算のいくつかのプロパティを使用できます。たとえば、Aある条件 (以前に計算されたもの) に応じて、 is は 0 または 1 のいずれかでありA*B+(1-A)*C、式 を計算しますif A then B else C。

Answer 4

入力 (の結果) に基づいて分岐できるものが必要です。

条件分岐をシミュレートする 1 つの方法は、自己変更コードを使用することです。実行中の命令のストリームに結果を格納する計算を行います。無条件ジャンプのオペコードを命令ストリームに入れ、入力に対して数学を実行して、入力の条件セットに応じて、そのジャンプの正しいターゲットを作成できます。たとえば、y から x を減算し、正の場合は右にシフトして 0 を埋め、負の場合は 1 を埋め、次にベース アドレスを追加し、その結果を jmp オペコードの直後に格納します。その jmp に到達すると、x==y の場合は 1 つのアドレスに移動し、x!=y の場合は別のアドレスに移動します。

Answer 5

チューリング完全マシンを構築するために条件分岐は必要ありませんが、もちろん、チューリング完全マシンはコア機能として条件分岐を提供します。

Rule 110 Cellular Automatonのような単純なシステムを使用してチューリング マシンを実装できることが証明されました。このようなシステムをビットバケットから引き出すために条件分岐は必要ありません。実際には、岩の束を使用することもできます。

重要なのは、チューリング マシンが条件分岐を提供するということです。そのため、チューリングの完全性を証明することによって、とにかく条件分岐を実装することになります。半導体のロックやPN接合など、ある時点で条件付き分岐なしで行う必要があります。

Answer 6

Z3 は、抽象的な観点からチューリング完全であるにすぎません。任意の長さのプログラム テープを使用して、すべての条件分岐の両側を計算させることができます。つまり、分岐ごとに両方の答えを計算し、どちらを無視するかを教えてくれます。明らかに、これにより、条件分岐ごとに指数関数的に大きなプログラムが作成されるため、このマシンをチューリング完全な方法で使用することはできません。

Answer 7

マシンが分岐できる場合、はい、チューリングが完了したと見なされます。

その理由は、条件分岐を自動的に行うと、すべてのコンピューターのチューリングが完全になるからです。ただし、分岐や IF にさえジャンプできないが、それでもチューリング完了と見なされるマシンもあります。

処理とは、出力を選択するために入力を識別するプロセスです。

分岐は、このプロセスを理解するための 1 つの方法です。ジャンプの条件は、入力を分類できるものであり、分岐してその入力の正しい出力を格納する場所です。

最後に、物事を明確にするために：

条件付き分岐がある場合、コンピューターは計算上、チューリング マシンと同等である必要があります。ただし、コンピューターがチューリングの完全性を達成する方法は他にもたくさんあります (ラムダ、IF、CL)。