66

バックグラウンド

Von-Neumannアーキテクチャは、命令とデータがメモリに格納され、マシンが内部状態を変更することによって動作するストアドプログラムコンピュータを記述します。つまり、命令は一部のデータを操作し、データを変更します。したがって、本質的に、システムには状態が維持されます。

チューリングマシンのアーキテクチャは、テープ上のシンボルを操作することによって機能します。つまり、スロットの数が無限のテープが存在し、任意の時点で、チューリングマシンは特定のスロットにあります。そのスロットで読み取られたシンボルに基づいて、マシンはシンボルを変更して別のスロットに移動できます。これはすべて決定論的です。

質問

  1. これら2つのモデルの間に何か関係はありますか？フォンノイマンモデルはチューリングモデルに基づいているか、チューリングモデルに触発されましたか？

  2. チューリングモデルはフォンニューマンモデルのスーパーセットであると言えますか？

  3. 関数型プログラミングはチューリングモデルに適合しますか？もしそうなら、どのように？関数型プログラミングはフォンノイマンモデルにはうまく役立たないと思います。

4

5 に答える 5

56

チューリングマシンは、計算可能な問題の領域を数学的に調査し、これらの計算を記述する方法を取得するために発明された理論的概念です。

フォンノイマンアーキテクチャは、実際のコンピュータを構築するためのアーキテクチャです（チューリングマシンが理論的に説明するものを実装します）。

関数型プログラミングはラムダ計算に基づいています。ラムダ計算は、計算またはより正確には計算可能な関数を記述する別の方法です。まったく異なるアプローチを使用していますが、チューリングマシンにも同様に強力です（チューリング完全であると言われています）。

すべてのラムダ計算プログラム（用語）Tは、次の組み合わせを使用して記述されています。

  • のような変数x
  • 次のような無名関数λx. T
  • 関数アプリケーションT T

ステートレスであるにもかかわらず、これはコンピューターが実行できるすべての計算に十分です。チューリングマシンとラムダ項は相互にエミュレートでき、Von-Neumannコンピューターは両方を実行できます（チューリングマシンが必要とする可能性のある無限ストレージの提供などの技術的な制限は別として）。

しかし、ステートレスでより抽象的な性質のため、関数型プログラムは、バイナリ、メモリ、および更新のスタイルに従う命令型プログラムと比較して、フォンノイマン型コンピュータでは効率が低く、「直感的」ではない可能性があります。

于 2010-05-06T15:09:14.080 に答える
15

一般に、ハーバードアーキテクチャとは対照的に、フォンノイマンアーキテクチャを指します。前者は同じ方法でコードとデータを保存しますが、後者はコードとデータ用に別々のメモリとバスの経路を持っています。最新のデスクトップPCはすべてVonNeumannであり、ほとんどのマイクロコントローラーはハーバードです。どちらも、理論上のチューリングマシンをエミュレートしようとする実際の設計の例です（実際のチューリングマシンは無限のメモリを必要とするため、これは不可能です）。

于 2010-05-06T16:36:55.563 に答える
4

チューリングモデルは、実装に深く踏み込むことなく計算機能を定義します。文字通りチューリングマシンのように見えるコンピューターを作成する人は誰もいません。（愛好家を除くhttp://www.youtube.com/watch?v=E3keLeMwfHY）。

チューリングモデルはアーキテクチャではありません。

Von Neumanは、コンピューターの構築方法に関するガイダンスです。計算能力については何も述べていません。命令セットに応じて、作成されたコンピューターはチューリング完全である場合とそうでない場合があります（つまり、チューリングマシンと同じタスクを解決できます）

関数型プログラミング（ラムダ計算）は、チューリング完全であるが、フォンノイマンアーキテクチャにネイティブに適合させることができない別の計算モデルです。

于 2010-05-06T15:07:26.820 に答える
4

チューリングマシンとフォンノイマン型アーキテクチャの間にどのような歴史的関係があるのか​​わかりません。ただし、フォンノイマンアーキテクチャを開発したとき、フォンノイマンはチューリングマシンを知っていたと確信しています。

ただし、計算能力に関しては、チューリングマシンとフォンノイマンマシンは同等です。どちらか一方をもう一方をエミュレートできます（IIRC、チューリングマシンでのフォンノイマンプログラムのエミュレートはO（n ^ 6）操作です）。ラムダ計算の形式での関数型プログラミングも同等です。実際、少なくともチューリングマシンと同じくらい強力なすべての既知の計算フレームワークは同等です。

  • チューリングマシン
  • ラムダ計算（関数型プログラミング）
  • フォンノイマンマシン
  • 部分再帰関数

これらのモデルのいずれかで計算できる関数のセットに違いはありません。

関数型プログラミングはラムダ計算から派生しているため、TuringマシンまたはvonNemuanマシンのいずれにも直接マッピングされません。どちらも、エミュレーションを介して関数型プログラムを実行できます。チューリングマシンのマッピングはフォンノイマンマシンのマッピングよりも面倒だと思うので、3番目の質問に対する私の答えは「いいえ、実際にはもっと悪い」です。

于 2010-05-06T15:24:46.170 に答える
0

チューリングの「モデル」は、建築モデルではありません。チューリングが決定問題の証明のための手段として機能すると仮定したのは、存在しないマシンにすぎませんでした。

于 2010-05-06T19:27:13.767 に答える