知らなくてもいいよね。

広告に「/*なんたらかんたら*/」なんて、Ｃなのかな？プログラミング言語の区切り記号が使われていた。
署名欄に〈/signature〉なんて書いている人も居て、こんな区切り記号で自分の好きな言語を表現できるっていいよね。なんて思ったりして。
プログラミングなんてFamily Basicしかやった事ないので（嘘）キチンと何かの言語を勉強したいなぁとは、昔から思っている。

じゃあ、一番使われているプログラミング言語ってなんだろう？
キチンと勉強するなら汎用性の高いものがいいよね。
「一番使われているプログラミング言語」でGoogle。
するとやっぱりWikipediaの「プログラミング言語」を読む事になった。


その時は、まだ、あれほど恐ろしいものに出会う事になるとは思っていなかった…。


つらつらと読んでいると「プログラミング言語の定義」の欄に至った。
「表現能力」の項で理解不能となる。

表現能力
計算理論では、言語はその計算表現能力で分類される（チョムスキー階層参照）。チューリング完全な言語ならば、同じアルゴリズム群を表現可能である。SQLはチューリング完全ではない言語の例であるが、それでもプログラミング言語と呼ばれることがある。

ちょ、チョムスキー階層！チューリング完全！じぇんっじぇん知らん！
おそるおそる「チョムスキー階層」を押してみた。

チョムスキー階層（-かいそう、Chomsky Hierarchy）とは、形式言語を生成する形式文法のクラスの包含階層である。これは「句構造文法」（Phrase Structure Grammars）の階層とも呼ばれ、1956年にノーム・チョムスキーが発表した。

チョムスキーさんが発表した以外、全く頭が反応しない。「拒絶」。頭がポンっ！速攻「戻る」ボタンを押す。呼吸を整える。落ち着く。
やめとけばいいのに、「チューリング完全」ってのがカワイイ名前なので気になってしまった。リンクを押してみた。

計算理論で、あるプログラミング言語がチューリング機械と同じ計算能力をもつとき、その言語はチューリング完全であるという。

・・・
・・・・・
世の中には、完全な計算が出来る「チューリング機械」なる、げにも恐ろしげなマシンがあるのだろうか？機械なんだからギアやらピストンやらがガッシャンガッシャンしながら完全な計算を行うんだろうか？うわぁ、恐ろしや恐ろしや。
もう少し読む。

正規表現はチューリング完全でない。
SQLや、ループの書けない表計算マクロなども、チューリング完全でない。

ちょっとだけ聞いた事があるぞ。
文章検索の時に使う「正規表現」やら、エクセルで使う「マクロ」やら、チューリング完全でないものは、どこかまだ親しみのあるもの達だ。
ではチューリング完全なものは、どんなだ？

ラムダ計算はチューリング完全である。これは、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことから証明できる。そのほか、μ再帰関数やマルコフアルゴリズムもチューリング完全である（チャーチ＝チューリングのテーゼも参照）。

♪ざーんーこ～くな、チューリングのてーぜ～♪。などと歌いながら一旦「戻る」ボタンを押す。
どうやらチューリング完全な方々とはお友達になれそうにない気がする。
Yコンビネータさんともマルコフさんともお友達になれないしμ再帰関数なんかとは同じ部屋に居てるだけで気まずくなりそうだ。
こんなにかわいいチューリングなのに、恐ろしい奴等である。


しかし、気になるのは、「チューリング機械」である。

がっしょんがっしょん、しゅーしゅー、と言いながら完全な計算をするマシンは、いったいどこの国にいるのだろうか？
コンピュータ全盛の現代においても、いまだに、蒸気機関を使い、石炭と水蒸気でがっしょんがっしょんと動いているのだろうか？
それとも大英博物館あたりに展示され、余生を過ごしているのだろうか？
写真だけでも見てみたい。
掲載されていれば良いのだが。
と、「チューリング機械」をポチッと押してみる。

チューリングマシン (英: Turing Machine) は計算模型のひとつで計算機を数学的に議論するための、単純化・理想化された仮想機械である。

ほっ、仮想機械か。理論ですね、理論。頭の中にだけある機械。ホッとした。
恐ろしげな蒸気マシンはかき消えました。

概要を読んでみると、チューリング機械とは、無限に続く磁気テープとメモリ付きのヘッドで構成されたもの。こんな単純な機械で、完全な計算が出来ると言う理論だ。
「if とwhileさえあればプログラミングだ」なんて話かな。ってことがわかる。
アラン・チューリングさんが言い出したんだ。
チューリングさんかぁ。
カワイイ名前だけど、きっと気むずかしいおっさんなんだろうなぁ。

などと、油断して次の行に目を移すと、真に恐ろしいものが待っていた。

形式的定義
チューリング機械とは次の7つ組M=〈Q,Γ,b,Σ,δ,qinit,qacc〉である。
●Q は有限集合であり、その元を状態という。
●Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
●b は Γ の元であり、空白記号とよばれる。
●Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
●δ は Q × Γ から Q × Γ × {left, right} への写像であり、遷移函数とよばれる。δ(q, a) = (q’, a’, m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q’ に移し、着目位置に記号 a’ を書き込んでから、着目位置を m 方向に1つずらす」と読む。
●qinit は Q の元であり、初期状態とよばれる。
●qacc は Q の元であり、受理状態とよばれる。

あわわわわー、ぎゃわわー。

ブラウザの「×」ボタンを押して、脳みそを守った。