ケータイ小説 計算機科学入門 第1話

なんでこんなキモい話書くの？

計算機科学（コンピュータサイエンス）にも「常識」があるンだけど
現代人は忙しいし
ましてや技術者はデスマーチ
（研究者でもいるけど）
大学の授業受けたり
教科書とか読む暇ないでしょ（書く暇も）

情報とか計算機（コンピュータ）とか

Computer = 日本語では計算機だけど
1+2=3みたいな計算だけじゃない
「情報」を処理することはみんな「計算」
情報って何、とか言い始めると哲学になっちゃうけど
知識の表現ってことにしておいて
だから文字や文章はもちろん
画像とか音声・音楽とかも情報

計算モデル

「計算機科学」だから
計算機（っていうか「計算」そのもの）について「科学」するんだけど
いちいち電子回路から考えてたら大変だし
古来、「計算（機）」は電子回路だけじゃないの
本質を明確にしたいから抽象化＝一般化して
数学的なモデルを考えるわ

有限状態オートマトン

一番基本的な計算モデルから始めてみるわ
メモリ＝状態(state)は有限なの
有限だからq_0, q_1, q_2, q_3, ..., q_nと列挙できるの
それらの集まりQ = {q_0, q_1, q_2, q_3, ..., q_n}を状態集合と呼ぶわ

「ある状態q_iから、入力aを受け取ると、ある状態q_jに変化する」とき
状態q_iから入力aにより状態q_jに「遷移する」と言うわ
そういう一つ一つの遷移は(q_i, a, q_j)という三つ組で書けるから
遷移の集まりは{ (q_i_1, a_1, q_j_1), (q_i_2, a_2, q_j_2), (q_i_3, a_3, q_j_3), ..., (q_i_m, a_m, q_j_m) }とか書けるわ
それが遷移関係T
(q_i, a, q_j)がTに属しているとき
見やすくするため q_i ---a---> q_j とか書くわ

あと、最初の状態＝初期状態を決めておかないと計算が始められないから
普通、q_0を初期状態とするの

初期状態q_0から入力a, b, c, d, ...を受け取って
q_0 ---a---> q_i ---b---> q_j ---c---> q_k ---d---> ...
とか状態遷移を繰り返すの
それがオートマトンっていう計算モデル
ここでは状態が有限だから
正確には有限状態オートマトンって呼ぶの

…続く…（また暇になったら／気が向いたら）