状態の概念無しで表現できる計算も大事です
私が主張したいのは「私たちが計算*1と呼ぶもののモデル化には、必ずしも状態の概念が現れるとは限らない」です。これを立証するために、ブーリアン回路族という状態の概念を必要としないモデルが、計算をしていると言えるほど十分強力であることを前の記事で紹介しました。
一方、私は「全ての計算は状態の概念を利用せずにモデル化できる」と言いたいのではありません。なぜならば、状態の概念を必要とする計算はあるからです。
状態の概念を必要とする計算はあります
世の中には状態の概念が必要な問題領域が存在します。例えば、時計は現在の時間を状態として持つでしょうし、自動販売機はユーザが投入された金額を状態の形で追跡する必要があります。
当然、このような問題を解く計算機やそのモデルには状態の概念が存在します。ミーリ・マシンがこういった計算機の一つのモデルです。
例えば、きしださんの言う「1を無限に出力する」機械はミーリ・マシンを使って以下のように表現できます。
- 状態は1つです
- 単一の入力（例: 時間経過）に応じて状態が遷移します。状態が1つしかないので遷移先も同じ状態ですが。
- 状態遷移に伴って1を外部に出力します。
状態の概念無しで表現できる計算も大事です
ですが、計算が全てこのようなものであるとは限りません。例えば、コンパイラはソースコードを入力として受け取り機械語を出力するような計算機だと考えられます。
コンパイラが行うような計算はブーリアン回路族でシミュレートできます。つまり、コンパイラを表現するために状態概念は必要ありません。
コンパイラのような計算は私たちが計算と呼ぶもののうち重要な部分をなしていると私は考えます。実際、これらの計算は決定問題という部分に少しの工夫*2で対応します。回路族とチューリングマシンの等価性も決定問題の文脈において示されています*3。
この話題の大元はプログラミング教育についてでした。私たちがプログラミングを学ぶとき、決定問題に対応するような計算をたくさん扱うでしょう。例えば、入力を二つ受け取って足し算するようなプログラムもこの部分に入ります。
プログラミングの基本は順次処理と状態遷移なわけで、公教育ではそこを押さえればいい。
— きしだൠ(K1S) (@kis) 2023年2月27日
あと、オブジェクト指向の前に高階関数のほうが大事やろ。で、高校の授業としては難しすぎる。
話をずらしていくのはやめましょう
結局、きしださんは構文解析がブーリアン回路族で計算できることには合意されるのでしょうか？どんどん話題を変えられるとそもそも何の話をしているか分からなくなってしまいますし、不誠実です。
