チューリングの計算理論概要と参考図書とニューラルチューリングマシン

チューリングの計算理論の概要

チューリングの計算理論は、アラン・チューリングによって提唱された、コンピュータの基本的な概念を理論化する理論となる。この理論は、コンピュータがどのように動作するか、そして計算が何であるかを理解するための基礎を提供するもので、次のような要素から構成されている。

• チューリングマシン: チューリングマシンは、計算理論における基本的な計算機械となる。この機械は、紙テープ上に記号を書き込んだり、読み取ったりすることができ、状態遷移関数に従って紙テープ上の記号を読み取り、書き換え、移動させることで、計算を実行する。有限状態機械というのオートマトン理論に関しては”オートマトンと状態遷移/ペトリネットと自動計画“を参照のこと。
• チューリング完全性: チューリング完全性とは、ある種の計算機が、すべてのチューリングマシンと同じ計算能力を持つことを示す概念となる。つまり、チューリング完全性を持つ計算機は、あらゆる種類の計算を実行することができる。
• 可算性と非可算性: チューリングの計算理論において、可算性とは、ある問題がアルゴリズムによって解けることを指す。一方、非可算性とは、ある問題がアルゴリズムによって解けないことを指す。例えば、停止問題は非可算性の問題であり、アルゴリズムによって解くことができない。与えられた解候補が正しいかどうかを多項式時間で検証できる問題「NP完全問題」に関しては”命題論理の充足可能性判定問題(SAT:Boolean SAtisfiability)の概要と実装“を参照のこと、
• チューリングテスト: チューリングテストは、人工知能が人間のように思考することができるかどうかを評価するテストとなる。このテストでは、人間とコンピューターが同じ問いに対する回答をするかどうかを比較する。もしコンピューターが人間と同じような回答をすることができれば、それは人間と同じように思考していると見なされる。詳細は”会話とAI(チューリングテストから考える)“を参照のこと。

チューリングの計算理論の参考図書

チューリングの計算理論の入門的な参考図書としては「チューリングの計算理論入門」がある。

「イギリスの数学者チューリングは、ヒルベルトの「決定問題」解決のために、万能計算機の数学的モデル「チューリング・マシン」のアイディアに至った。この「チューリング・マシン」こそが、コンピュータの万能性を保証する数学的基礎になった。
　チューリングは、「チューリング・マシン」を使って、計算という行為を徹底的に検証した。そして、手順を示すことと、計算ができることが同じであることを示した。その手順はアルゴリズムと呼ばれ、いまではソフトウェアと言われている。
　本書は、コンピュータの原理としてのチューリング・マシンを解説するとともに、決定問題を解決した有名な「チューリング・マシンの停止問題」も分かりやすく説明します。さらに計算量と、７大難問の一つ「P＝NP問題」についても、わかりやすく解説します。」

チューリングの計算理論入門
	まえがき
	第1章 人間にとっての計算
		計算は人間の営み
		東京タワーは一つで十分(数の概念)
		数をまとめる
		ゼロの概念
			漢字で数字を表すと0は現れない
		足し算
		引き算
		掛け算と割り算
			数をまとめて足したり引いたりする
		お釣りの計算は足し算でする?引き算でする?
		お釣りの計算を行う手順
			計算を行う場合には必ず手順がある
			手順が組み合わさって複雑な手順になる
			手順の基本要素
				順序(順番)
				分岐(ならば)
				反復(繰り返し)
		人間にとっての計算とは
			ある状態のとき、外からの刺激によって判断を行い、次の状態へ移る
				計算
			計算とは
				物の数量をはかり数えること
					count
					Cash up
				加減乗算など、数式に従って数値を引き出すこと
					calculate
				結果や成り行きをある程度予測し、それを予定の一部に入れ替えること
					calculate
		人間が行う判断や予測
			電車やバスの遅延がないかどうかチェックする
				遅延がなければ通常通りのコースで通勤
					終了
				遅延があれば
					朝ごはんを食べる時間がルアかどうかをチェック
						時間があれば通常通り食べる
							終了
						時間がなければ食べずに通勤
							終了
			「判断」や「予測」という行動も「計算」と言って良い
	第2章 機械に計算をさせようという試み
		コンピュータにとっての計算
			computer
				ラテン語のcomputare
					計算
					2つの数の足し算
					com(ともに)+putare(考える)
			コンピューターは自分で考えることができない
				入力として過去の履歴やある条件が与えられ
				それらを「決められた手順に従って」黙々と計算する
			データが入力されて、ある計算を行った結果が出力される
		コンピュータは考えるのだろうか?
			コンピューターの計算能力にも限界がある
		計算の手順を表したもの-アルゴリズム
			コンピューターが何か行動を起こすということは、 「人間が解決したい問題」が先にあって、 それに必要な手順を一つづ順番にこなす
			人間のようにとりあえずではダメ
			指示書を与える必要がある
				すべきことがもれなく含まれていること
				終着点があること
				指示書があれば誰でも同じようにできること
		良いアルゴリズムと悪いアルゴリズム
			一つの問題を解くためのアルゴリズムは複数存在
				リボンを8等分したい
					メジャーで測って8で割り、その長さではかりながらハサミで切る
					2つに折って真ん中をハサミで切る、さらに2つに折って真ん中をハサミで切る、さらに2づておって真ん中をハサミで切る
			複数のアルゴリズムを比較するには作業量(計算量)を比較する
		全部の計算に言えること
			コンピューターの計算は「ある状態が、外からの刺激によって変化して、状態が変わる」こと
		コンピュータの計算手順の構造
			コンピューターの計算における手順の基本構造
				順次
				分岐
				反復
		アナログ計算機とデジタル計算機
		数表
		歯車で計算をする
			パスカルの歯車式計算機
			パスカリーヌ
				加算と減算
			ライプニツ
				掛け算・割り算もだ切るようにする
		蒸気で動かす計算機
			チャールズ・バベッジ
				自動的に間違いのない数表を作る
				あるルールに従って計算
				階差機関
		多機能計算機
			パスカルやライプニッツの機会は数値だけしか外から支持することが出ない
			バベッジの機会は計算と数値を外から支持して計算手順を自分で判断
		ライプニツはチューリングを予言した
			記号論理学の奏者であるゴットフリート・ヴィルヘルム・ライプニッツ
			「普遍言語」という概念を打ち立てる
		2進法
			「計算」が機械的な作業に置き換えられることを理解するには、2つの記号しか必要がない
			中国の易経(陰陽)がルーツ
			全てのコミュニケーションをコード化するには2つの記号で十分
				フランシス・ベーコン(1623年)
			計算するとは、 足し合わされたたくさんのものの合計をかぞえあげるか、 あるものを別のものから取り除いた時に何がのこめかを知ること
				推論は足し算、もしくは引き算と同じ
		19世紀後半の数学の発展
	第3章 オートマトンとチューリング・マシン
		決定問題
			計算モデルとはアルゴリズムを表現する一つのモデル
				チューリング・マシン
			「機械的な手順によって、証明可能であるか証明不可能であるかチェックすることは可能か?
			「機械的な手順」→アルゴリズム
			証明できるか、できないかを計算する(チェックする)手順を書き表すことは可能か?
			チューリングの論文
				計算可能数とその決定問題への応用
		コンピュータの万能性を保証するチューリングマシン
			可能でないことの証明
		3-1 オートマトン(automaton)
			ハンバーガー、いかがですか?(状態)
				「計算」とは、「ある状態が外からの刺激によって変化して状態が変わること」である
				「状態」とは
					人や物事の、ある時点でのありさま
			ゲームの持ち点
			ゲーム自体がオートマトン
				オートマトン
			じゃんけん
			オートマトンの機械
				オートマトンはアルゴリズムを示す一つの手段
				自動販売機
				エアコン
			オートマトンと計算の関係
				オートマトン: ヨーロッパで古くから種々のアイデアを元に作られた 自動機械や自動人形を意味する言葉
				ソフトウェアはアルゴリズムをプログラム言語を使って「プログラム」にしたもの
				あらゆるソフトウェアはオートマトン
				コンピュータが「判断」をする時には、 何か物事の「状態」があり、 それぞれの状態の時にある「入力」があったらどう処理するかを示したルールがあり、 そのルールに従って判断を行い、 その結果「状態」が変わる
				「コンピュータが行う処理のルールを表すことができる」 = 「状態が変わっていく様子を表すことができる}
		3-2 チューリングの計算理論
			チューリング登場
				オートマトンの入出力を 「無限のテープを使って行おう」という考え方で、 テープ状に結果を残すように拡張した計算モデル
			チューリングマシンの構造
				計算できるかできないかをチェックする機械的な手順(アルゴリズム)が存在するか?
				上記を数学的に証明
				人間が計算する時にどのようにするか?
					人間を「いくつかの状態を取ることができる機械」に置き換える
				例:(10+2)x3を計算する
					① 10と紙に書く
					② ①で書いた数値に2を足す(紙には「+2」を付け加えて多分「10+2=12」と書いてある)
					③ ②の結果に3をかける(紙には「x 3」を付け加えて多分「12x3=36」と書いてある)
					④ 終わり
				チューリングマシン
			外からの刺激(テープとヘッド)
				ルール表にはヘッドの動きと、そこでの読み書きが支持されている
				ヘッドは一度にマス目を1つだけ右動くか左に動くかしかできない(動く(左右)、動かないの3パンのみ)
				マス目には番号はついていない
				右に3つ動く場合は右へ移動を3回行う
			ヘッドの動きとテープの読み書きのルール
				ルール表の表現
					マス目の記号が0ならば、そのマス目には1を書き込み、その後ヘッドを右へ移動
					0, P1, R
			状態が分からないと困る
				状態1の時に、マス目の記号が0ならば、そのマス目には1を書き込み、その後ヘッドを右へ移動
				状態1 : 0, P1, R
			簡単なチューリングマシン
			3+2をやってみよう
			0と1を交互に表示するチューリングマシン
			掛け算をするチューリングマシン
			チューリングマシンの計算はなぜこんなに大変なのか
				何かの式(証明すべきことがら)与えられたら、 それが証明できるかできないかを機械的に判断することができるか
				何かの式(証明すべき事柄)が与えられたら、 それを計算するアルゴリズムはあるか?
				計算できること
				アルゴリズムで書き表すこと
				チューリングマシンで記述できること
			チューリングマシンで記述できるものがアルゴリズム
				チューリングマシンで記述できるものをアルゴリズムと呼ぶ
				人間(またはコンピュータ)が実行できるアルゴリズムは、 チューリングマシンで実行できる
					チャーチ=チューリングの提唱
			チューリングマシンで記述できるものは「計算できる」
			無限なのに有限!?
			3分の1の計算をするアルゴリズム
				計算できるとは
					四則演算ができることではなく
					「ある状態が外からの刺激によって変化して状態が変わること」が有限の手順で書き表わせること
			チューリングマシンはいくつあるのか?
			アルゴリズムを整数で表すとは?
				アルゴリズムを数えるために、チューリングマシンを表現する表を変形して整数で表す
				アルゴリズムを整数で表すことができるので、数えることができるはず
				計算できる
				計算できないとうことはアルゴリズムに番号が整数で振ることができない
				アルゴリズムのリストに存在しない
			未来のソフトウェアも数え上げられる
			できるとできないをなぜ区別する?
			チューリングマシンはソフトウェア
			コンピュータはチューリングマシンか
				ある一つの目的を持ったチューリング・マシンはソフトウェアであって現在のコンピュヘータではない
				コンピュータは「単能チューリングマシン」ではなく「万能チューリングマシン」
	第4章 決定問題
		できる、できない
			計算できる(計算可能)=アルゴリズムで記述できる
			計算不能=問題を解くアルゴリズムが存在しない
		YesかNoか?
			決定問題
				YesかNoかで決める問題
			答えとしてYesかNoかだけを求めるある問題を解くアルゴリズムが存在するならば、 その問題にはYesかNoで答えられる
			ある問題が計算可能であるかどうかを判定するために、 その問題を変形させていって、 最終的なYesかNoかで答えるような決定問題の形にすることが可能
		止まらないチューリングマシンがある?
			ヒルベルトの時代の数学者は 「あるパターンの数式で表せれば、 その数式の世界の中で表せないことはない」 という数式を求める
			「どのような数式の世界を作ったとしても、 その数式の世界の中で表せないことが存在する」 ことが証明されれば、 「矛盾の生じない数式の世界が作れる」という仮説が間違っている
		嘘つきのパラドックス
			「クレタ人は嘘つきだ」とクレタ人は言った
		止まらないことは分からない
			停止性判定チューリングマシンは作れない
			停止性判定問題は計算不能
		最終的にたどり着いた
			チューリングよりも5年前(1931)にゲーテルも 「不完全性定理」で 「証明も反証もできない命題が存在する」ことを示す
			ゲーテルのゲーテル数のアプローチと近い
	第5章 万能チューリング・マシン
		万能である=モノマネが出来る
		万能チューリング・マシンとは
		物真似チューリング・マシンの仕組み
		物真似の種明かし
		いざ代理実行
		コンピューターはチューリング・マシンなのか
		チューリングマシンを日本語で書いてみよう
		ヘッドの場所と動きを表そう
		条件分岐
		プログラムを綺麗に書くために
		決まった処理をまとめる
			消去する
			比較する
			印をつける
			メモ:動詞全てを使って定義CISC?
		オプションもどうぞ。「いんすう」と呼ばないで
			関数の引数の違いで使い方を変えることで、関数を無限大にしない
		万能チューリング・マシン実現のためには
			万能チューリングマシンを構成する最小の要素
				基本的機能
					文字を検索する
					消去する
					模写する
					書き換える
					比較する
				ベース機能
					決まった処理を一つにまとめる機能
					順番
					条件分岐
					繰り返し
		全ての計算モデルは同じ
			チャーチのモデル
				Λ計算
					計算できるといえる全ての事柄は、 λ計算の中で具体的に表現できる
			クリーネの「帰納的関数」
			その他のモデル
				再帰的関数
				ランダムアクセスマシン
				プログラム内蔵方式RAM
				マルコフアルゴリズム
				チョムスキーの句構造構文
	第6章 計算量の話
		検索するときの手順
			ロボット検索エンジン
				Webページのデータを収集する
				キーワードを抽出して、キーワード毎にデータベースに登録する
				ユーザーの情報に応じて検索結果を表示する
		1+2=3の計算
		プログラムの定義
		計算できるかできないか判断する方法
			オートマトンやチューリングマシンを使った計算モデルで擬似的に実行させることでチェック
		計算量
		サンタクロースの汚れた靴下
			コンピューターを使わない情報教育(Computer Science Unplugged)
				ニュージーランドのTim Bell博士提唱
			1024個の中から探す
		同じ数があるかを判定する問題
			4個の整数があるとき、全ての整数が異なっているかどうかを判定
		実行に必要な時間の計算
			上記の手順を文章と図で表現する
		全ての数が異なる場合
		時間計算量
		実行にかかる時間は何に影響されるの?
		時間計算量の表し方
		オーダー(注文ですか? いいえ、違います)
			時間計算量:オーダーO
		明日の予報は明日には分からない?
		倍になっても倍になるとは限らない
		良いアルゴリズムのオーダー
		悪いアルゴリズムのオーダー
		オーダーを計算しよう
		実行に必要な記憶領域
		解ける問題のグループ分け
		クラスP
			Polynomial 時間計算可能なクラス
		どうしようもないかどうか?
			決定性(Deterministic)アルゴリズム
				たくさんの組み合わせの中から一番良いものを選ぶ
				たった一つ理解を選ぶアルゴリズム
			非決定性(Non-deterministic)アルゴリズム
		見当つけてから、チェックする
		クラスNP
			Non-deterministic(非決定性) Polynomial
			一番良い答えを探し出す多項式オーダーのアルゴリズムは見つかっていないけれれど、 非決定アルゴリズムを用いて答えの見当をつけてから それが問題の条件を満たしているかどうかを判断する多項式オーダーのアルゴリズムは見つかっている
		非決定性アルゴリズムの特徴
		PとNPのおさらい
		PとNPの関係
		P=NPか?
			決定性アルゴリズム=しらみつぶしに探す
			非決定性アルゴリズム:問題を満たすような候補をいくつか見つけておいて、 それがその問題に適合するかどうか後でチェック
		素因数分解
		NPであるがゆえに安全である暗号
		NPとPを区別する意味
		NP完全
		最初のNP完全問題
		NP困難
		PやNPの記憶計算量
	第7章 コンピュータへの道のり
		チューリングの計算理論の復習(エッセンス)
			判断し、予測し、推論する
			チューリングマシンで記述できるものがアルゴリズム
			アルゴリズムを記述したものがプログラム
		論理と計算をつなぐ理論-プール代数
			チューリングマシンを物理的に実現すればコンピューターになる
			論理式
				「〜だったら、〜する」
			プール代数
				論理式を計算に置き換えて機械的に処理できるようにする
		天才シャノンのひらめき
			シャノンによるプール代数の回路による実現
			A Symbolic Analysis of Relay and Switching Circuits (リレーとスイッチ回路の記号論的解析)
			あらゆるアルゴリズムはプール代数により論理計算に変換
			さらにプール代数はカイロになって機械的に計算可能になる
		ライプニツの夢とプール台数
			ライプニツが2進計算によるデジタルコンピュータを構想
			デカルトの文字による記号表現
		そしてコンピュータが完成した
			フォンノイマンによる実際のコンピュータの完成
			非フォン・ノイマン型コンピュータ
				チューリングマシンのフォン・ノイマン型と異なった実現
		コンピュータは何故2進数を使うのか?
			2進法を使うことで処理のバリエーションを減らすことができる
		4枚のトランプ?(2進数の仕組み)
		2進数の足し算
		論理の演算
		事実を表す命題
		AND(論理積)
		OR(論理和)
		XOR(排他的論理和)
		NOT(否定)
		チューリング・マシンと論理回路
			ANDとORとXORとミラかを買えば全ての論理を演算で表すことが可能
	あとがき

さらに歴史的な流れを掴むものとしては「万能コンピュータ ランプニッツからチューリングへの道筋」がある。

「コンピュータ前史ライプニッツからチューリングに至る数理論理学の系譜は，コンピュータの理論的バックボーンを形成しAIの登場までも予見している。代数の記号表現を通じて人間の思考の範囲すべてを包括するような記号体系の構築に献身したロジシャンたちの苦闘を，時代背景を取り込みながら解説する。さらに本書を構成する7人のロジシャンたちを，豊富なエピソードをもとにその人となりを描写する。また，本文に取り込むと冗長になりすぎる数学的解説は，原註に取り込むことで半独立的な構成としている。比較的平易に書かれているので，コンピュータロジックの成り立ちに関心のある高校生以上の読者や，人工知能のロジックの成り立ちに関心のある読者にも必携の書である。」

万能コンピュータ  ランプニッツからチューリングへの道筋 マーティン・デイビス
	序章
	第1章 ライプニつの夢
		ライプニつの「素晴らしいアイデア」
		パリ滞在へ
		ハノーヴァーでの後半生
		普遍記号への試み
	第2章 論理を代数に変換したプール
		プール艱難辛苦の人生
		プールの論理代数
		プールと「ライプニツの夢」
	第3章 フレーゲ:画期的達成から絶望へ
		フレーゲの概念記法
		形式構文法の創始者フレーゲ
		ラッセルの手紙が壊滅的な打撃となった理由
		フレーゲと言語哲学
		フレーゲと「ライプニツの夢」
	第4章 無限を巡り歩いたカントル
		エンジニアか数学者か
		サイズが異なる無限集合の発見
		カントルによる超限数の探求
		対角線論法
		抑鬱と悲劇
		決定的な問いへ?
	第5章 ヒルベルトの救済プログラム
		若きヒルベルトの数学的成功
		新しい世紀に向かって
		クロネッカーの亡霊
		超数学
		破局
	第6章 ヒルベルトの計画を転覆させたゲーテル
		隠れた呪縛:クロネッカーの亡霊
		決定不可能な命題
		プログラマとしてのゲーテル
		ケーニヒスベルクでの会議
		愛と憎悪の渦中で
		ヒルベルトの格言
		奇妙な男の悲しい最期
		付録:ゲーテルの決定不能命題
	第7章 汎用計算機を構想したチューリング
		大英帝国の申し子
		ヒルベルトの「決定問題」
		チューリングによる計算過程の分析
		チューリング機械の動作
		チューリングによる対角線論法の援用
		アルゴリズム的に解けない問題
		チューリングの万能機械
		チューリングのプリンストン滞在
		アラン・チューリングにとっての世界大戦
	第8章 現実化された万能計算機
		誰がコンピューターを発明したのか?
		フォン・ノイマンとムーア校のグループ
		アラン・チューリングのACE
		エッカート、フォン・ノイマン、チューリング
		恩寵深い国家がヒーローに与えた報酬
	第9章 ライプニツの夢を超えて
		コンピュータ・脳・心
	終章

ニューラルチューリングマシン

ニューラルチューリングマシンとは、ニューラルネットワークとチューリングマシンを組み合わせた計算モデルのことを指す。

通常のニューラルネットワークは、入力データを数値データとして扱い、数値演算に基づいて計算を行い、一方チューリングマシンは、シンボル操作に基づいて計算を行う。ニューラルチューリングマシンは、これらの両者を組み合わせることで、より高度な計算を実現することを目指すものとなる。

ニューラルチューリングマシンでは、入力データをシンボル列として扱い、それをニューラルネットワークによって処理する。処理の過程で、ニューラルネットワークは、シンボル列のパターンを学習し、シンボル列を生成することができる。また、チューリングマシンの機能を組み込むことで、ニューラルネットワークによって生成されたシンボル列を入力としてチューリングマシンを実行することができる。これにより、ニューラルチューリングマシンは、従来のニューラルネットワークよりも複雑な計算を実行することが可能となる。

ニューラルチューリングマシンは、人工知能や自然言語処理などの分野で、特に有用な計算モデルとして注目されているが、現在では、ニューラルチューリングマシンの実装には技術的な困難があり、まだ研究段階に留まっている。

• ニューラルチューリングマシン入門(外部リンク)
• 人の心に似た機械を設計できるのか(外部リンク)
• ニューラルネットワークでチューリングマシンを作る(外部リンク)