F-nameのブログ

はてなダイアリーから移行し、更に独自ドメイン化しました。

計算モデル概論(2)(コンピューティング第2回)

The理系という内容だけど結構面白く聞けた。パソコンと絡んだ内容は興味深く聞けるので網羅的に学ぶのも良いかもしれない。

 

萩谷真己。計算モデル。ラムダ計算の簡約の概念。状態と状態遷移。状態機械。チューリング機械。現実の回路やcomputer。
簡約の概念。状況の書き換え。ラムダ計算で簡約。ラムダ項をより簡単なラムダ項で。数式とその一部を他の数式で。簡約。数式の値を計算する。7引く2、5という数式で置き換える。同じものを表現する5という数式。7引く2の値。つまり同じもの。数式の一部を置き換える。数式全体同士は同じ。等式が成立。簡約の前と後とは等しい。計算を更に進める。4×5は20。更に簡約される。それを繰り返す。同じものを表現している。等式が成立する。7引く2の操作。1を引いて更に1を。7引く1引く1で置き換える。7引く1を6で簡約出来る。簡約のステップは時と場合に依存する。計算のモデルの中で。機械的に簡約が出来るように。大雑把であっても細かくても等式は成立する。意味を変えない操作。計算の対象として文字列などを扱うことも沢山ある。ベクトルや関数も。様々な式に対して簡約が成立する。項が用いられることも。ラムダ計算ではラムダ項。式の簡約を繰り返してこれ以上簡約が出来ない。正規形と呼ぶ。23はこれ以上に簡約できない。元の式の値。簡約の前と後とは変わらない。簡約を置き換えることとして定義。式の値を求めるために簡約を。より簡単にしなければならない。正規形。なるべく正規形に近づくように簡約を。簡単化。置き換えのルールを定義するための。状況の書き換え。筆算とチューリング機械。状況。計算の進み具合を指す。必ずしも状況の一部を同じ式に置き換えるのではない。テープ状の式が同じ式に書き換えられたのではなく1ステップ進んだに過ぎない。計算したい式をテープに書き込む。終了状態に至った時に式を読む。簡約しようとする式全体が状況。簡約は書き換えの一種。正規形に到達。終了状況。正規形そのものが式の値。
状態機械の考え方。チューリング機械の初期状況。書き換えのルールにより書き換えが繰り返される。初期情報にのみ外から情報が与えられる。簡約も同じ。この間に外から何らかの情報が入ることはない。初期設定をして動け、ずっと動く。内部的変化はあるが外から情報は入らない。computerでも機械でも外からの情報をやり取りするのが通常。どうやって。応答して外の世界に働きかけを。外の世界も応答して情報を返す。それに対して応答。それを繰り返す。外の世界を観測に行くかもしれない。入力を受け取って何らかの応答を。入力に対する出力。外の世界から入力をもらって出力を返す、その繰り返し。チューリング機械も簡約も。停止してから出力を変える。また入力を貰うことは想定されていない。ここで想定するcomputerや機械は、入力をもらって一旦停止して出力をするのが一般的。そうでないと異常事態。何らかの変化が。xを入力されてyを返す。同じ入力xでも同じyを返すとは限らない。出力が異なるとすると、変化が起こったと考えることになる。そもそも入力が同じだったかという問題はあるけれど。何らかの変化が。computerや機械は何らかの状態を保持していて、内部状況を変化させると。状態は外からの入力により変化を。state。状況とは異なる。状態を実現するには何らかの記憶が必要。メモリでなくても保持されていれば状態が実現する。computerや機械というのを状態機械という一般的概念に。生物も天体も。機械という言葉を含むが数理的モデル。特定の状態機械。入力の集合と出力の集合。状態遷移。状態機械の例、自動販売機。computerを内臓。蛍光灯もリモコンが主体。昔ながらの紐付きの蛍光灯。点灯を制御する機械。紐を引くという動作1つのみ。1本だけで。1回引っ張ってつけて消す。2つ在る。ONとOFF。状態がOFFの時に司令があってONに。状態がONのときにOFFと変化させる。数学的定義。入力の集合は紐を引くという要素のみ。つけると消すの2つの可能性。出力の可能性は2つの要素からなる集合。状態はONとOFF。状態遷移。状態機械が。状態の変化は現状に依存する。数学的には入力と現在の状態の組み合わせと現在の状態の組み合わせと出力の関係。関数にする。出力と次の状態が一意的に定まるとする。紐を引くとONの組。消すとOFFの組。その2つの関数。遷移関数と呼ぶ。状態機械の状態繊維。状態遷移図という図形で図示。点灯を制御する状態機械の状態遷移図。円と→。遷移の先へ。矢印は入力と出力。/で区切る。チューリング機械。チューリング機械の有限状態制御部。状態が入っている。有限個の状態が。有限状態制御部はヘッドを通じて読み込む。入力の集合。マス目に文字を書き右か左に。書き込む文字とヘッドの動きの組み合わせが出力。テープは外の世界、そこから入力を得る。チューリング機械を世界と考えるとその中で情報のやり取りを。状態遷移は関数として考えているが、状態遷移が決定的であるか非決定的であるか。非決定であれば一意的ではない。関数ではなく関係。沢山あり得るのでそれらの中から何らかの方法で1つに。サイコロを振ったり神様のような存在を想定したりと。組を全て試す方法もある。状態遷移を許す。入力なしという仮想的入力を。内部遷移。仮想的入力は何時でもよいので、内部遷移は何時でも起こりうる。内部遷移を1回行ってから入力を受け入れることも可能。非決定的に。チューリング機械は内部遷移だけを。状況を状態の区別は相対的。機会全体を状況とすると状態として定義しうる。状態機械が並列計算、分散計算を。他の機械は外の機械と考える。
現実のcomputerはどのような計算モデルで動いているか。フォン・ノイマン型アーキテクチャとチューリング機械との関係。論理回路。0または1。組み合わせ回路と順序回路。組み合わせ回路。ゲートが構成。幾つかのビットをもらってビットを返す関数を構成。順序回路はメモリを持つ。組み合わせ回路とメモリから構成。入力とメモリの現在の内容から。同じ数のビットで成り立つ。5ビットをもらって6ビットに返す。クロックの信号が周期的に送られている。メモリに書き込む。順序回路は状態機械そのもの。メモリの内情が状態を表す。論理回路を用いて現実のcomputerはフォン・ノイマン型アーキテクチャで。アーキテクチャ。コンピュータアーキテクチャの中でも古典的で基礎となる。メモリと中央処理装置とパスから。CPU。メモリはバイトなどに分割。16ビット32ビット64ビット。ワード。番号が振られている。バイトごとに振られることが多い。アドレス、番地。マス目に相当。ヘッドはなくて、アドレスを指定して。バス。通信路。データバスとアドレスバス。データを読み書き。アドレス情報をアドレスバスに。内容をデータバスに。CPUが受け取る。アドレス情報をアドレスバスに。データをデータバスに。メモリは受け取って書き換える。フォン・ノイマン型アーキテクチャではメモリの一部に機械語命令が。1つの機械語命令は数バイトの中に。機械語プログラム。CPUは読み取って計算を。算術計算など。プログラムカウンター。機械語命令の内容に。変化もする。条件分岐や繰り返しなどの機械語プログラムが実行。CPUは機械語命令を読み取るなどの。順序回路。CPUの出力。CPUはメモリとの間で情報のやり取りをおこなう。レジスタ、CPUの中のメモリ。状態に相当。フォン・ノイマン型アーキテクチャとチューリング機械の類似点。アドレスを指定してメモリの読み取りを。CPUはメモリから読み取り変化させる。フォン・ノイマン型アーキテクチャ全体を状態機械と捉えることが出来る。入力装置と出力装置をバスに接続。入出力装置との間でもデータのやり取りを。

 

コンピューティング―原理とその展開 (放送大学大学院教材)

コンピューティング―原理とその展開 (放送大学大学院教材)