文献

J-GLOBAL ID：201202258555224162   整理番号：12A1105194

Turing機械の持続する遺産

The Enduring Legacy of the Turing Machine

著者 (1件)： FORTNOW Lance (Northwestern Univ., Illinois)
資料名： Computer Journal  (Computer Journal)
巻： 55  号： 7  ページ： 830-831  発行年： 2012年07月 
JST資料番号： D0002B  ISSN： 0010-4620  CODEN： CMPJA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： 「計算可能なものはすべてTuring機械により計算可能である」というChurch-Turingの命題では,ディジタル計算,確率計算機,並列計算機,量子計算機,インターネットなどの計算モデルを含んでいない。そして,現在,計算は原子や整数のような自然の基本部分の一つであるという見方を述べた。Peter Denningは,Church-Turingの命題の応用可能性に関して以下の3つの問題を掲げた。1)Turingの計算は有限回数のステップの後に停止するが,今日の,オペレーティングシステム,Webサービスなどはこの中に含まれないのか?2)Turingの計算の定義には,物理量表現のために連続信号を用いるアナログコンピュータの概念は含まれているのか?3)Turingの計算概念には,自然界の情報処理や自然計算に関する最新の議論を含んでいるのか?を掲げた。本稿では,これらの問題に対する考え方について議論を行った。その中で,計算プロセスはアルゴリズムや値と呼ばれる概念の表現列であるというDenningの考え方を紹介した。このことは,Denningの新しい定義が再定式化されたTuring機械に他ならないと述べ,計算可能なものはすべてTuring機械により計算可能であることを論じた。

シソーラス用語： *Turing機械 ,  *計算可能性 ,  計算モデル ,  オペレーティングシステム ,  Web【情報システム】 ,  Webサービス ,  アナログ計算機 ,  アルゴリズム

分類 (2件)： オートマトン理論  (JB04000O) ,  計算理論  (JB02000A)

タイトルに関連する用語 (1件)： Turing機械