内容詳細 ソフトウェアを動作させる計算の原理を数学的なモデルで理解することを目標とした.本書で得られる知識は,計算の可能性と限界を知る上で役に立つとともに,ソフトウェアの構築法の基本を学ぶのに役に立つであろう.2色刷. 第1章 序-計算の考え方 1.1 計算のための機械 1.2 計算可能性の概念 第2章 準備 2.1 集合 2.2 関係 2.3 関数 2.4 命題 2.5 証明方法 第3章 有限オートマトンとチューリング機械 3.1 計算機械のモデル化 3.2 有限状態機械と有限オートマトン 3.3 プッシュダウン・オートマトン 3.4 チューリング機械 第4章 プログラミング言語L 4.1 言語Lのプログラム 4.2 マクロ 4.3 言語Lの抽象計算機ML 第5章 帰納関数 5.1 帰納関数の考え方 5.2 初期関数 5.3 合成 5.4 原始帰納 5.5 帰納関数による述語と論理結合子
WIRED VISIONの記事のよれば、Wolfram氏が提案したもっとも簡単なチューリングマシンが万能チューリングマシンであることを20歳のイギリスの学生が証明して見せたのこと。Wolfram氏は、この証明に2万5000ドルの賞金をかけており、見事47日後に証明して見せた。 ちなみに、Wolfram氏は、複雑系理論の権威でもあり、Wolfram Mathematicaの設立者でもある。社名の通り、Mathematicaを開発している会社だ。 提案されたチューリングマシンは、2つの状態と3つの色を持つ装置であり、証明の内容(PDF)も公開されているので、興味のある方は追ってみてはいかがでしょうか?
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く