原理的に考察するのも必要なのだろう。
萩谷昌己。計算モデル概論。簡約の概念。状態と状態遷移。状態機械。現実の論理回路やコンピュータの構成。
ラムダ計算から離れて。ラムダ項をより簡単なラムダ項で。数式を同じ内容の数式で置き換えることを簡約という。数式の値を計算。7-2の部分。同じものを表現する5という数式で置き換える。値を表すので、7-2と5は同じ数式。一部を同じ内容の数式で置き換えると、=。等式が成り立つ。簡約の前の数式と後の数式が等しい。4*5を20で置き換える。23の数式は元の数式から簡約を繰り返して。等式が成り立つ。この過程をもう少し細かく捉えることも出来る。7-1-1に。6-1に簡約。簡約の1回のステップは定義は自由。ときと場合に依存する。煩雑になるかもしれないが、計算のモデルの場合は機械的に簡約が実行できる程度に細かく定義をしないといけない。前の数式と後は等しいのは同じ。意味を変えない操作。計算の対象は数に限られない。計算の対象として文字列や表や木構造なども。スカラーの数ではなく、ベクトルや関数も扱う。様々な対象の式についても簡約を定義できる。単に式と。それに加えて項、term。書き換えの対象を、項、λ項。式の簡約を繰り返してこれ以上簡約出来ない式に到達。正規系と呼ぶ。23は正規形。元の式の値。正規形の式の値を求めるために簡約を。式の値を求めるためには、式をより簡単にしなければならない。正規形に近づくように簡約を行うべき。簡単化するのが簡約。置き換えのルールを適切に作る様々な工夫。状況の書き換えについて。チューリング機械。状況。一般には計算全体の進み具合を。計算全体の進み具合。状況の一部を置き換える、ということではない。チューリング機械のテープの一部が書き換えられる。チューリング機械の計算が1ステップ進んだに過ぎない。状況の書き換え。計算したいことを初期状況に書き込む。チューリング機械の場合は文字列としてテープに。終了状況に至った時に式の値を。式の簡約は特別な場合。式全体が初期状況。簡約される式が。正規形に到達したとする。終了状況に相当。正規系そのものが式の値。
状態機械。チューリング機械の初期状況が設定。初期状況にのみ外から情報が。一部の式をより簡単に。コンピュータに書き換えると初期状況から進み続ける。停止するまで外の世界とは関係なく動き続ける。コンピュータでも機械でも外の世界とやり取りをしながら。何らかの内部状態を持って外の世界と。一般には外の世界から情報をもらい働きかけを。外の世界も何らかの情報を返すので応答する。この繰り返し。より積極的に外の世界を観測に。受け取り応答をする。入力に対する出力。この繰り返し。チューリング機械も式の簡約も同様の仕組み。停止したら出力を返す。停止しないかもしれない。ここでは外の世界から入力をもらい。入力を貰ったら停止して出力を返すことが想定される。そうでないと異常事態。出力したら入力をもらうことが可能に。何らかの変化が起きているかもしれない。XをもらいYを受け取りまたXをもらう。同じ入力でも同じYとは限らない。外から観測して出力が違うと、内部に何らかの変化が。出力が1つではない場合も。同じ入力を受け取る間に内部に変化が起こったということは、内部に何らかの状態を保持していて、内部状態を変化させることが。状態という言葉は外からの働きかけで変化する。state。状態と状況の違い。状態を実現するには何らかの記憶が必要。コンピュータのメモリなど。状態という概念は極めて一般的。コンピュータや機械から状態機械という概念。外の世界と情報の遣り取りをするもの。生物も状態機械。天体も。抽象的な数理的モデル。集合を与えて情報遷移を定義。状態機械の例。自動販売機が例になっていた。例えば紐付きの蛍光灯を。点灯を制御する機械。入力は紐を引くことのみ。紐を1回引くと点灯してもう1回引くと消灯する。機械の状況は2つ。ONとOFF。状態OFFのとき。状態ONのとき。指令を送り変化させる。数学的定義を。入力の集合は1つの要素のみ。2つの可能性。出力は2つの要素からの集合。状態の集合はONとOFFの。状態遷移とは状態を変化させる動作。状態機械の現在の状態に依存。入力と現在の状態に対応させる。入力と現在の状態の組み合わせの対応。関数になっている場合。出力などが一意的に定まる。OFFの組に対して点灯とONの組。関数。状態遷移が関数により定まる場合に遷移関数と呼ぶ。状態遷移図を用いて図示。点灯を制御する状態機械。状態遷移図では矢印などを用いる。遷移の先の状態。入力と出力はスラッシュで区切る。チューリング機械。その有限状態制御部に着目。状態が入っている。有限状態制御部に対しては有限個の集合が。状態機械とみなせる。ヘッドを通してテープを読み込むので入力の集合は文字の集合。その升目に文字を書く。出力と捉えるとその組み合わせが。有限状態制御部にとってはテープは外の世界に属する。テープから情報を得る。テープに働きかける。チューリング機械と外の世界との情報のやり取りはなくても世界の中で。テープとヘッドでやり取りが。状態遷移は関数であると考えているが。決定的であると。そう考えない場合は非決定的であると。状態遷移が非決定的である場合は一意的ではない。数学的には対応は関数でなく一般の関係に。許されている出力などの組み合わせがたくさんあり選択が。サイコロをふったり。組に適当な確率を割り当てて情報遷移を。神様の存在。将来を見通して。全て試すという方法も。組を全て。状態機械に入力が無くても状態遷移を許すことを。仮想的入力と。内部遷移。いつでも起こりうる。そのまま本当の入力に対しか内部遷移を1回行ってからすることも可能。内部遷移を許すと状態機械の遷移は必然的に非決定的に。チューリング機械は内部遷移だけを繰り返しているとも。チューリング機械全体の状況。状況と状態の相違は相対的。テープも含めて状態に。それぞれの状態機械が他と情報をやり取りしながら遷移する。分散計算。並列計算。全体と部分の。状態全体は外の世界と。外の世界と情報をやり取りしながら状態遷移を。
現実のコンピュータはどのような計算モデルで。様々な見方が。フォン・ノイマン型アーキテクチャとチューリング機械の関係。論理回路。0又は1の。組み合わせ回路。ゲートから。幾つのかのビットを貰い別のビットを返す。関数。順序回路。メモリを持つ。組み合わせ回路とメモリから構成。メモリの現在の内容も同じ数のビットから。
