チューリングマシンとは何か？（第1回/全3回）
計算とは何かを定義する、エレガントな抽象概念 先月、DeepMindのCEOであるDemis Hassabisが、XでYann LeCunに反論した。その中で、私の目を引く主張があった。 「人間の脳（およびAI基盤モデル）は、近似的なチューリングマシンである。」1 「チューリングマシン」や「チューリング完全」という言葉は、これまで何度も耳にしてきた。しかし正直なところ、本当の意味を理解していたかと言われると怪しい。この記事では、短く、密度高く、それでいてわかりやすい説明を目指す。第1回では、チューリングマシンが実際に何であるかを扱う。第2回では、「チューリング完全」の意味を説明し、Demisの主張を再検討する。 1930年代、数学者たちは「計算」とは何かを形式化しようとしていた。電子計算機が存在する以前、「computer」とは文字通り、規則に従い、紙に途中経過を書きながら手計算を行う人間のことだった。 Alan Turingはこう問いかけた。あらゆる機械的な計算を捉えるために必要な最小限の操作は何か？彼の答えは、一見自明に思えるほど単純でありながら、計算可能なものすべてを計算できるほど強力な抽象機械だった。 机に座っている人を想像してほしい。その人は次のものを持っている。 その人ができることは次の4つだけ。 これだけだ。演算装置もメモリバンクも並列処理もない。読み、書き、移動し、状態を変える。その繰り返しだ。 これを実際に見てみよう。 1の個数が偶数である2進数文字列を受理するマシン $M$ を構築しよう。 入力 $w = \texttt{1011}$ を考える。これは1が3つ（奇数）なので、$M$ は拒否すべきである。入力 $w = \texttt{1100}$ は1が2つ（偶数）なので、$M$ は受理すべきである。 テープは入力が書かれた状態で始まり、その後ろに空白（$b$ と書く）が右に無限に続く： $$\texttt{1} \quad \texttt{0} \quad \texttt{1} \quad \texttt{1} \quad b \quad b \quad b \quad \cdots$$ マシンのヘッドは最も左のセルから、初期状態 $q_0$ で開始する。戦略はこうだ。右に走査し、1に出会うたびに「偶数個見た」と「奇数個見た」を切り替え、0は無視し、空白に到達したら受理または拒否する。 状態：$Q = \lbrace q_{\text{偶数}}, q_{\text{奇数}}, q_{\text{受理}}, q_{\text{拒否}} \rbrace$、$q_0 = q_{\text{偶数}}$（0個の1は偶数）。 遷移： 各行はこう読む。「状態にいるときに、この記号を読んだら、この記号を書いて、この方向に移動（左または右）し、次の状態になる。」 $w = \texttt{1011}$ を追跡してみよう： 予想通り、拒否された。$w = \texttt{1100}$ を自分で試してほしい。$q_{\text{受理}}$ で終わるはずだ。 気づいただろうか？このマシンは新しいものを何も書かず、左にも移動しない。ただ右に走査し、状態を切り替えているだけだ。チューリングマシンの全能力はまだ使っていない。 では、書き込みと双方向の移動を必要とするものを試そう。回文の検出だ。 文字列が回文であるとは、前から読んでも後ろから読んでも同じということだ。$w = \texttt{101}$ を考えよう：これは回文なので、$M$ は受理すべきである。入力 $w = \texttt{100}$ は回文ではないので、$M$ は拒否すべきである。 アルゴリズム $w = \texttt{101}$ を追跡してみよう。テープは次のように始まる： $$\texttt{1} \quad \texttt{0} \quad \texttt{1} \quad b \quad \cdots$$ 反復1：状態 $q_0$ で、左端の $$X \quad \texttt{0} \quad \texttt{1} \quad b \quad \cdots$$ $q_{\text{1を探す}}$ で、マークされていない最も右の文字（ $$X \quad \texttt{0} \quad X \quad b \quad \cdots$$ $q_{\text{戻る}}$ で、最初のマークされていない文字（ 反復2：$q_0$ で $$X \quad X \quad X \quad b \quad \cdots$$ $q_{\text{0を探す}}$ で、マークされていない最も右の文字を探して右に走査する...存在しない。すべてマークされているので、$q_{\text{受理}}$ に遷移する。 この例は、例1では必要なかったものを示している。 $X$ は入力の一部ではないことに注意。入力アルファベットは $\Sigma = \lbrace \texttt{0}, \texttt{1} \rbrace$ だが、テープアルファベットは $\Gamma = \lbrace \texttt{0}, \texttt{1}, X, b \rbrace$ である。マシンは有効な入力に現れるもの以外の記号も読み書きできる。 例を見てきたので、ここで形式的な定義を示す。チューリングマシンは7つ組である： $$M = (Q, \Gamma, b, \Sigma, \delta, q_0, F)$$ 遷移関数 $\delta$ はマシンの頭脳だ。「状態 $q$ にいて記号 $s$ を見たら、$s'$ を書き、左か右に移動し、状態 $q'$ に切り替える。」 マシンは、最終的に $F$ 内の状態に到達すれば、入力 $w$ を受理する。マシンが認識する言語は、受理するすべての文字列の集合だ。$L(M) = \lbrace w \in \Sigma^* \mid M \text{が} w \text{を受理する} \rbrace$ と書く。ここで $\Sigma^$ は入力アルファベット上のすべての有限文字列を意味する。例えば $\lbrace 0, 1 \rbrace^ = \lbrace \epsilon, 0, 1, 00, 01, \ldots \rbrace$ だ。 $L(M)$ をもう一度見てほしい。マシン $M$ は有限だ：有限個の状態、有限のテープアルファベット、したがって有限個の遷移規則。しかし言語 $L(M)$ は無限個の文字列を含みうる。チューリングマシンは、潜在的に無限の集合の有限な記述である。 これはラッセルのパラドックスに関する記事で探求したことと重なる。内包的記法では、$\lbrace x : x > 5 \rbrace$ はわずかな記号で無限個の数を表す。チューリングマシンも同様のことをする。 $$\lbrace x : x > 5 \rbrace \quad \text{vs} \quad \lbrace w : M \text{が} w \text{を受理する} \rbrace$$ どちらも所属条件によって集合を定義している。違いはこうだ。内包的記法は任意の性質を許すが、その中には機械的なテストが存在しないものも含まれる（「$n$ は来週の宝くじの当選番号に現れる」は集合を定義するが、所属をテストするのは無理だ）。一方、チューリングマシンは構成上、それ自体がテストである2。定義と手続きは同一なのだ。候補 $w$ を渡してくれれば、$M$ を実行できる。 「1の個数が偶数」マシンは6つの遷移規則しかないが、無限個の文字列を受理する。$\epsilon$、 1つ注意点がある。マシンは停止せずに永遠に動き続ける可能性がある。これについては第2回で詳しく述べる。 チューリングマシンとは何かを見てきた。機械的計算のための最小限の抽象化だ。読み、書き、移動し、状態を変える。 しかし、なぜこのような単純なマシンが重要なのか？第2回では、「チューリング完全」の意味、なぜこの原始的なマシンが最大の計算能力を持つのか、そしてDemisが「近似的なチューリングマシン」で何を意味したのかを扱う。 Yann is just plain incorrect here, he's confusing general intelligence with universal intelligence. この記事はClaude（Opus 4.5）と協力して執筆しました。歴史的背景
チューリングマシン
直感的な理解
例1：1の個数が偶数
状態 読む 書く 移動 次の状態 $q_{\text{偶数}}$ 0 0 右 $q_{\text{偶数}}$ $q_{\text{偶数}}$ 1 1 右 $q_{\text{奇数}}$ $q_{\text{偶数}}$ $b$ $b$ — $q_{\text{受理}}$ $q_{\text{奇数}}$ 0 0 右 $q_{\text{奇数}}$ $q_{\text{奇数}}$ 1 1 右 $q_{\text{偶数}}$ $q_{\text{奇数}}$ $b$ $b$ — $q_{\text{拒否}}$ 1 を読む → 右に移動、$q_{\text{奇数}}$ に切り替え0 を読む → 右に移動、$q_{\text{奇数}}$ のまま1 を読む → 右に移動、$q_{\text{偶数}}$ に切り替え1 を読む → 右に移動、$q_{\text{奇数}}$ に切り替え例2：回文検出
1 を読む。$q_{\text{1を探す}}$（「1を探している」）に遷移し、$X$ を書く。1）まで右に走査する。一致した！ $X$ を書き、$q_{\text{戻る}}$ に遷移する。0）まで左に走査し、$q_0$ に遷移する。0 を読む。$q_{\text{0を探す}}$ に遷移し、$X$ を書く。形式的定義
記号 意味 $Q$ 有限の状態集合 $\Gamma$ テープアルファベット（マシンが読み書きできる記号の有限集合） $b \in \Gamma$ 空白記号（入力の先にある無限のテープを埋める） $\Sigma \subseteq \Gamma \setminus \lbrace b \rbrace$ 入力アルファベット（有効な入力記号） $q_0 \in Q$ 初期状態 $F \subseteq Q$ 受理状態の集合 $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \lbrace L, R \rbrace$ 遷移関数 0、00、11、0000、1111、0110...すべてを列挙することは不可能だが、任意の文字列を渡してくれれば、マシンを実行してそれが集合に属するかどうかを判定できる。次回予告
Brains are the most exquisite and complex phenomena we know of in the universe (so far), and they are in fact extremely general.
Obviously one can't circumvent the no free lunch… https://t.co/RjeqlaP7GO