20世紀前半、数理科学の諸分野で何人もの天才が綺羅星のごとく出現し、今日の隆盛に至る礎を築きました。
その一部の名前を挙げれば、ゲーデル、フォン・ノイマン、シャノンらであり、チューリングもその一人です。
Wikiによれば、アラン・チューリング(Alan Mathison Turing, 1912～1954)は、イギリスの数学者、暗号研究者、計算機科学者、哲学者。
今日の計算科学の祖の一人とされます。
チューリングの最初の部分は、「テュ」と書く方が英語の発音に近いようですが、ここではよく使われる「チュ」ーリングの方を採用します。
チューリングは、コンピュータの理論的基礎を作るのに貢献し、また当時のコンピュータそのものの設計やソフトウェア開発にも携わりました。
Wikiから、晩年と死亡状況に関するエピソードを引いておきます。
＞1952年、同性愛の罪（風俗壊乱罪）で警察に逮捕され、保護観察の身となり、転向療法としてホルモン治療を受ける。1954年に41歳で死去。検死によると、青酸中毒による自殺と断定されたが、母親や一部の友人は事故だと信じていた。
20世紀では早世の天才ですね。
藤井聡太君を見て天才が変人だというのは偏見だと考えるようになったのですが、変人の天才も確かにいるようです・・・
今回は、チューリングらを始祖とする計算科学の入口の入口であるオートマトンを取り上げます。
オートマトンの次の話題としてはチューリング機械を予定しています。
ネタ本は次の2冊です。
・清水 義夫 著 『記号論理学講義』 東京大学出版会 A5判383頁 2013年3月発行 本体価格￥3,800(税込￥4,180)
副題は「基礎理論 束論と圏論 知識論」
・田中 一之 著 『計算理論と数理論理学』 共立出版 A5判上製310頁 2022年6月発行 本体価格￥4,200(税込￥4,620)
上製というのはハードカバーの意味です。
引用するときは、それぞれ清水著、田中著と呼ぶことにします。
さて、言語は、記号から構成されています。
知性とは言語を操る存在であるとすれば、記号を処理する機械は知性に到達し得るはずです。
（この辺は賛否分かれるところでしょうが、とりあえず志は高くもつ、ということでご納得を）
その機械を計算機と呼ぶことにすれば、計算機は「文を読み書きできる」ことが必要です。
ただし、計算機の読み書きは人間が行うのと同様である必要はありません。
「読む」とは記号の入力により計算機の状態が変化すること、「書く」とは記号を出力することと考えればよいわけです。
今回は、読み書きのうちの「読む」方だけが可能な機械を考えてみます。
このため、「読み書き」ができる機械と比べると、限界があることが容易に予想できますね。
読み書きできるチューリング機械については、この後別の(続きの)記事で取り上げます。
書かれた文章とは、1次元的な記号の連なりです。
これは、数学においてモノイドという数学的対象として研究が行われています。
まず語について説明し、語の集合上で定義される代数構造が自由モノイドとなることを示します。
記号の有限集合 Ω (≠∅) をアルファベット(alphabet)と呼びます。
その要素を有限個並べたもの a1…an を Ω 上の語(word)と言います。
また、nを語の長さと言います。
長さ 0 の語 ε も語であることにして、これを空語(empty word)と呼びます。
語全体を Ω* で表し、空語以外の語の全体 Ω*－{ε} を Ω+ と書きます。
（アルファベットが1つでもあれば、Ω* は無限集合となります。）
2つの語 v＝a1…an と w＝b1…bm に対し、a1…an b1…bm を v，w の連接(concatenation)といい、vw で表します。
もちろん、記号も長さ １ の語です。
Ω ⊂ Ω*．
Ω* の部分集合を、(Ω上の)言語(language)と言います。
数学理論における項全体、論理式全体、定理全体などは、この意味での言語です。
Ω 上の2項演算 v*w を連接 vw で定めると、代数構造 (Ω, *, ε) は Ω で生成される自由モノイド( free monoid )となります。
自由というのは、Ω から任意のモノイドへの関数が、Ω* からそのモノイドへの準同型（演算を保存する関数）に一意的に拡張できることを意味します。
モノイドの公理系を示しておきます。
ａ．すべての元の間に2項演算×が定義されている。
ｂ．結合法則 ： (ｘ×ｙ)×ｚ ＝ ｘ×(ｙ×ｚ)．
ｃ．単位元 1 の存在 ： ｘ×1 ＝ 1×ｘ ＝ ｘ．
つまり、モノイド(monoid)あるいは単位半群とは、群の概念から逆元 ｘ-1 の存在を取り除いたものです。
Ω 上の言語では、空語 ε が単位元です。
自由モノイドの乗法(連接)とは、2つの語を続けることにより新しい語を作ることです。
群とは異なり、逆元が存在しないことで乗法の結果がどんどん「長くなる」のです。
定義上、群はモノイドの一種となりますが、両者のイメージは全く異なります。
それでは、「文を読む機械」のモデルを考えてみましょう。
まず「文」は1次元なので、テープに書かれているものとします。
テープはマス目に区切られており、1つのマス目に1つの記号が入っています。
隣り合ういくつかの（1つでもいいけど）記号がまとまって、1つの語となります。
語と語の間は、空白のマス目で区切られているものとします。
次に、機械の方はいくつかの「状態」をとるものとします。
人間だったら心の状態なのでそれを記述するのは非常に面倒かつ精密にしづらいのですが、機械なので状態も単純な記号を対応させるだけですみます。
ただ、その数は有限個であればいくら多くてもかまいません。
テープは、機械から伸びている「ヘッド」で読み取られます。
（カセットテープレコーダーのイメージですが、今の人は分からないかな？）
これは理解のためのイメージづくり用であり、この後の数学的展開にヘッドが出てくることはほとんどありません。
またテープも、重要なのはテープそのものではなく、そこに書かれている記号とその順序です。
それでは、機械がどのように動くかを示します。
最初、ヘッドはテープの左端にあるものとします。
機械は左端のマス目の記号を読み取って、自らの状態を変化させます。
次に、ヘッドが1つ右、つまり左から2番目のマス目に移動して、そこの記号を読み取り、また状態を変化させます。
ヘッドは1つ右に移動し、そこの記号を読み取って、状態を変化させるという操作を繰り返します。
このような動きをヘッドがテープの右端に来るまで続けます。
ヘッドがテープの右端から外れたらそこで止まるものとします。
テープを全て読み終わったとき、機械の状態がどうなっているかが「文を読み取った結果」です。
そのときの機械の状態が特定の状態のとき、機械は語を読んで受理したものとします。
（人間だと「～と判断した」となりますが、機械なので受理という用語を使います。）
以上で描写したような機械をオートマトン(automaton)といいます。
オートマトンの元々の意味は、からくり人形や自動機械とのことです。
初期状態 止まった状態
┌─┬─┬─ … ┬─┐ ┌─┬─┬─ … ┬─┐
テープ│s0│s1│ │sn│ │s0│s1│ │sn│
└─┴─┴─ … ┴─┘ └─┴─┴─ … ┴─┘
ヘッド△ △
└───┐ ┌────┘
オートマトン オートマトン
形式的な定義を示します。
定義：(Ω上の) 決定性有限オートマトン(deterministic finite automaton)とは、次のような5つ組 M ＝( Q, Ω, δ, q0, F ) のことである。
Q ： 空でない有限集合。Qの要素を状態(state)と呼ぶ。
Ω ： 空でない有限集合。Ωの要素を記号(symbol)と呼ぶ。
δ ： δ∈Q×Ω→Q．δを遷移関数(transition function)と呼ぶ。
q0 ： q0 ∈Q．q0 を初期状態 ( initial state ) と呼ぶ。
F ： F⊂Q．F を終了状態 ( final states ) と呼ぶ。
遷移関数は、δ(qi, s)＝qj となります。
つまり、オートマトンの状態とテープの記号が1つずつ指定されると、次の状態が決まることを意味しています。
（テープの方は右隣りのマス目に移ることが決まっているので、特に指定する必要はありません。）
遷移(せんい)という用語はやや硬いですが、状態の移り変わり方を意味します。
遷移関数は、次のように表すこともできます。
δ＝{ ( qi, s / qj ) ｜qi, qj ∈Q, s∈Ω }
ただし、関数なので、同じ qi と s の組合せをもつ要素は1つだけです。
初期状態とは最初の状態のことで、これはただ１つです。
それに対し、語を受理したことを意味する終了状態は複数あり得るので、集合で指定しています。
決定性有限オートマトンという名前は長いので、決定性オートマトン、あるいは混乱がなければ単にオートマトンと呼びます。
後で、非決定性のオートマトンも出てきます。
---------------------- 続 く ---------------------
この後はまだ書いていないので、いつになるかは分かりません。
この記事のテーマについては、「計算科学」は今のところ作っていないので、「論理と言語」と「数学」のどちらにするか悩んだのですが、ネタ本に倣って論理寄りと考え前者にしておきます。同種の記事が増えたらテーマ「計算科学」を作るかもしれないけど、まあそこまで増えることもないでしょう。
★ 今日の昼は、半そででも過ごせるような陽気でした。黄砂さえなければ良い気候なのですが。
★★ 今日のロジバン 不思議の国のアリス181
… gi’e jgari lo blabi ke kanba gluta re mei fa’u lo barda bifpra lo re xance
・・・ 片手には白い子ヤギ皮の手袋一対、そしてもう片方の手には大きな扇子を持っていました。
jgari ： つかむ/握る，x1は x2(対象本体)・x4(対象箇所)を x3(x1の部分)で。「抱く」も。-jai- [動作・物体操作・移動]
kanba ： ヤギ属動物だ，x1は x2(種類)の。ちなみに、ヒツジ属は lanme．[生命・動物・特定動物]
gluta ： 手袋/グローブ/ミトンだ，x1は x2(材質)の。-glu- [生命・衣類]
fa’u ： それぞれ。接続詞[非論理]JOI類
bifpra ： 送風機/扇風機/うちわだ，c1は 空気/気体を速度b3で送る 過程c3によって <- bif+pra, bif<- brife 風, pra<- cupra 生産
xance ： 手だ，x1は x2(本体)の。-xan-, -xa’e- [生命・動物・身体部分]
一つ前から続く文の後半で、引用部分の主述語は jgari 、そのx2が { lo blabi ke kanba gluta re mei fa’u lo barda bifpra } 、x3が { lo re xance } 「両の手」です。
「一対」は項の後ろに { re mei } を付ければいいわけです。
bifpra 扇風機/うちわ/扇子は、「風を作るもの」なのですね。
出典は、