Loading article…
汎用アナログコンピュータ（GPAC ）は、1941年にクロード・シャノンによって初めて発表されたアナログコンピュータの数学的モデルである。[1]このモデルは、いくつかの基本ユニットが相互接続されて何らかの関数を計算する回路で構成される。GPACは、実際には機械装置またはアナログ電子機器を使用して実装できる。アナログコンピュータはデジタルコンピュータの出現によりほとんど忘れ去られているが、GPACは最近、物理的チャーチ＝チューリングのテーゼの証拠を提供する方法として研究されている。[2]これは、GPACが、物理学の文脈で頻繁に登場する常微分方程式で定義される大規模な動的システムをモデル化することでも知られているためである。[3]特に、2007年には、GPAC（の決定論的変種）が計算可能性の点でチューリングマシンと同等であることが示され、GPACによってモデル化されるシステムのクラスに対する物理的チャーチ＝チューリングのテーゼが証明された。[4] これは最近、多項式時間同等性に強化されました。[5]
定義と歴史
汎用アナログコンピュータは、もともとクロード・シャノンによって導入されました。[1]このモデルは、初期のアナログコンピュータであるヴァネヴァー・ブッシュの微分解析装置に関する研究の結果として生まれました。[6]シャノンは、GPAC を、加算器 (入力を加算する)、乗算器 (入力を乗算する)、積分器、定数ユニット (常に値 1 を出力する)、定数乗算器 (常に入力に固定定数kを乗算する) の 5 種類のユニットで構成されるアナログ回路として定義しました。最近では、簡略化のために、GPAC は、加算器、乗算器、積分器、実定数ユニット (固定の実数kに対して常に値kを出力する) の 4 種類の同等のユニットを使用して定義されています。
シャノンは最初の論文で、GPAC で計算可能な関数は微分代数的な関数であるという結果を提示しました。
参照
参考文献
- ^ abシャノン、 クロードE. (1941)。「微分解析器の数学的理論」。数学物理学ジャーナル。20 (1–4): 337–354。doi :10.1002/sapm1941201337。
- ^ O. Bournez および ML Campagnolo。連続時間計算に関する調査。新しい計算パラダイム。計算可能かどうかの概念の変化。(Cooper, SB、Löwe, B.、Sorbi, A. 編) Springer、383～423 ページ。2008 年。
- ^ DS Graça と JF Costa。アナログコンピュータと実数上の再帰関数。Journal of Complexity、19(5):644–664、2003
- ^ O. Bournez、ML Campagnolo、DS Graça、E. Hainry。多項式微分方程式は、計算可能なコンパクト区間上のすべての実計算可能関数を計算します。Journal of Complexity、23:317–335、2007
- ^ Bournez, Olivier; Graça, Daniel S.; Pouly, Amaury (2016).多項式時間は多項式長さの多項式常微分方程式の解に対応する: 汎用アナログコンピュータと計算可能解析は、2 つの効率的に同等な計算モデルです。ライプニッツ国際情報学会議( LIPIcs)。第 55 巻。Schloss Dagstuhl。pp. 109: 1–109 :15。doi : 10.4230 / LIPIcs.ICALP.2016.109。ISBN 9783959770132.S2CID 1942575 。
- ^ Robert Price (1982). 「Claude E. Shannon、口述歴史」. IEEE Global History Network . IEEE . 2011年7月14日閲覧。
外部リンク
- The Analog Thing: オープンソースのアナログコンピュータ