状態の概念が存在しない計算モデルはあります (例: ブーリアン回路)

きしださんは（チューリング完全な）計算モデルにはかならず状態の概念がある、と主張しています。文脈は次のツイートのあたりを見るとまあわかると思います。

この主張に対する反例として、ブーリアン回路による計算モデルを紹介します。

ブーリアン回路とチューリングマシンの等価性

ブーリアン回路*1とは、ANDやORといった組み合わせゲートを集めてできる回路のことです。
ブーリアン回路に対する入力をnビットのビット列、出力をmビットのビット列としましょう。
ブーリアン回路を構成するゲートとして{AND, OR, NOT}の三種*2を用いると、ブーリアン回路はnビットのビット列をmビットのビット列に移すどのような関数も表現することができます。

1つのブーリアン回路では入力サイズが固定されてしまっているので、代わりに各入力サイズnごとに異なる回路を利用することにしましょう。例えば、1ビット加算器、2ビット加算器、3ビット加算器…といったブーリアン回路の族（列）を考えると、この回路族全体で足し算という計算を表現していると考えることができます。

それぞれの入力サイズについてブーリアン回路はどのような関数も表現できたわけですから、それぞれの入力サイズに対応する回路に入力してあげることによって、ブーリアン回路族はチューリングマシンで表現可能などのような計算も再現することができます*3。

ブーリアン回路に状態は無い

上で書いた通り、ブーリアン回路は組み合わせ回路だけでできています。反対に言えば、ラッチ回路やフリップフロップのような状態回路は全く使っておらず、回路に対する入力を決めると出力はただ一つに決まります。従って、ブーリアン回路には状態の概念は（少なくとも陽に）存在しないと言えるでしょう。

ブーリアン回路に状態概念は暗に存在するか？→しないと思う

この意見に対する反論として、ブーリアン回路の実行には状態が暗黙的に存在するという主張が考えられます。

例えば、ANDゲートの出力に対してNOTゲートをくっつけることでNAND回路を構築したとしましょう。このNAND回路に対して[1, 0]というビット列を入力したとき、

  1. まず、ANDゲートが[1, 0]という入力に対して0を出力する。
  2. 次に、NOTゲートが0という入力に対して1を出力し、結果としてNAND回路が1を出力する。

というステップで回路の出力が分かります。そして、きしださんはこのステップをNAND回路に暗に存在する状態であると主張するかもしれません。

しかし、私はこの主張は成立しないと考えます。なぜならば、このステップはNAND回路をシミュレートする私たちの頭の中に存在するのであり、NAND回路の本質ではないと考えているからです。やはり、NAND回路自体は状態の無いブーリアン回路でしかないと考えます。

同様の再反論がラムダ計算についても言えるでしょう。確かに、私たちはラムダ項の書き換えプロセスに状態を見出すことはできます。しかし、その状態は項書き換えプロセスをシミュレートする私たちの頭（もしくはラムダ計算をシミュレートするチューリングマシン）の方にあるのであって、ラムダ計算自体には無いのでは無いでしょうか。

*1:https://en.wikipedia.org/wiki/Logic_gate

*2:NANDだけでもOKです。

*3:本当はほかにも色々と考えることがあります。例えばhttps://cs.stackexchange.com/a/96618を見てください