知らない概念が色々出てくる。計算モデルは突き詰めておいた方が良さそう。数式が厄介だけど。
コンピューティング。主要な3つの計算モデル。情報の表現方法を与える。30年代に登場し等価であることが。チューリング機械、帰納関数論。ラムダ計算。
チューリング機械。計算。情報の書き換え。コンピューティングはコンピュートから。語源。一緒、数える考える。カリキュレート。小石で数える。数えるという操作の特徴は？機械的なルールで。小石を機械的に動かす。紙の上の筆算で。数字などを書き込む。繰り上がりの数を小さく書く。消したりする。大きい文字に書き直す。筆算であっても消したり書き直したりする。1桁の足し算を行うルールが必要。100通り。繰り上がりがある場合。それも100通り。有限個のルールで済む。どのように適用するか。最初の状況から出発して最終の状態に。状況。初期状況。2番目の状況。終了状況。結果を含む。計算状況に計算ルールが。2番目の状況だけで何をするか分かるか？足すべき。初期状況を見ずに2番目の状況だけで。初期状況から状況を書き換える。各状況は空間上に配置された図形。計算ルール。書き換えることが出来ない時に計算は終了する。計算のルールとは？状況の数字の並び方。状況の書き換えは機械的ルールに。
チューリング機械。状況とは記号が配置された図形。チューリング機械は定式化された計算モデル。計算の過程を数学的に定式化。数学的な対象。数学的に定める。計算の状況はテープとヘッドと。マス目。マス目の下に。有限状態制御部。ヘッドの動きを定める。現在の状態を見る。有限状態制御部の現在の状態。メモ書きのようなもの。pを文字として書き加える。状況を書き換える計算モデル。チューリング機械ではテープが左右に無限に伸びている。必要に応じて空白のマス目が継ぎ足される。各状況は有限のテープとして。m×n。計算の状況は2次元的図形だったが、1次元的な並び。工夫で表現が可能。Webページ。HTMLで表現。充分に複雑な状況を処理しうる。
チューリング機械。チューリング。12年にイギリスで生まれ、計算の理論を。計算できないことを探求したいということから。計算の定義を。チューリング機械により計算できないこと。厳密に数学的に定義。チューリング機械は計算不可能性を示すため。ドイツ軍の暗号解読、コンピュータの開発。計算できることの具体的な。暗号解読機。機械が知能を持つことが出来るか。チューリングテスト、生物の個体が計算すると仮定。チューリング・パターン。
数の計算。典型例として関数の計算。自然数。ここでは0も入れる。最も基本的な数。計算の対象を自然数に限定。チューリング機械では文字列だったが。自然数だけでは議論にならない。様々なデータを表現しうる。素数の無限列。bookという文字列。文字コードで方言。文字コードは自然数で構成される。N番目の文字コード。素因数分解すれば文字コードに。自然数により表現が。自然数を貰い自然数を返す関数。帰納関数論。計算モデル。計算可能と考えられるものを定義。関数により実現。足し算と掛け算を計算可能とする。機械的に実行。2つの自然数を貰い1つを返す。関数を組み合わせるものも計算可能に。既に計算可能とされた関数について最小化。2つの自然数を貰い。F(x,y）。G（X）。x=0も計算可能。繰り返しの計算。最小のyが求まる。G（X)は最小のyを。しかし存在しなければいつまで経っても終わらない。もらった自然数によっては返さないことも。部分関数。繰り返しの途中で止まらないこともあり得る。Gの計算も止まらない。それも部分関数。止まることも。全関数。常識的な計算の多くは全関数。素因数分解やべき乗など。停止して答えが。
ラムダ計算。ラムダ項を対象に。関数を表現する。λ項。xとyの関数。もらったxを捨ててyをそのまま返す。別の例としてfとxを貰う関数。fは何らかの関数。fという関数を貰う。関数を表現するλ項を貰う。何もかもがλ項として表現される。m、p、qというλ項。簡約。一部に生じるλ項を簡約なλ項に。計算の結果。λ項のあるものは自然数を表現する。足し算という計算を実現。簡約を繰り返すといつまでも終わらない。簡約が無限に可能。一般的に部分関数を表現。
チューリング機械などの関係。帰納関数論とラムダ計算。部分関数間の関係。帰納関数論とラムダ計算。定義する能力には差がない。計算能力は等価。チューリング機械も部分関数を定義することが出来る。繰り返し書き換えられて停止状態になった時に停止すると仮定する。終了したテープの内容を。状況の書き換えが永遠に続くと終わらない。部分関数として。ルールを帰れば別の関数に。様々な部分関数を表現。ラムダ計算との計算能力は等価。自然数から自然数への計算。3つの計算モデルで部分関数が表せる範囲は等価。定義可能な部分関数の範囲は同じになる。計算可能性は強い概念。
計算モデルの万能性。万能チューリング機械。状況を書き換えるルールはプログラム。プログラムを文字列として表現する。rという文字は右へ。プログラム全体を1つの文字列として。忠実に実行するチューリング機械。
