Closed2025/01/21にクローズ40

チューリング完全って何

Turing complete

よく聞くチューリング完全ってのが何なのか理解しておきたい

まずこれ読む

ペアノの公理いわく0は自然数らしい......！！
0は自然数である。
その都度の定義によって変わるのか...数学ってそんな柔軟なのか........

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1352181478

ちなみに公理とは「証明不要の前提」

ふむふむ
本記事では「計算」を以下の性質を持つものとして定義します。
有限の記号列を入力とする
記号列に関する操作規則が定義されている
要は「記号」と「ルール」の2つが必要ということ

ん？矛盾してないか？

系列
いくつかのアルファベットの要素を連ねた記号列

空系列
何も文字がない系列

\epsilonで表す

系列というのはいくつかのアルファベットを連ねたもの、つまり複数個の文字があることは確定しているはず。なのに空系列の定義は「何も文字がない系列」とある。矛盾してない...？

そしてこれ、意味がわからない
この有限オートマトンに「aab」という系列を入力した場合、系列の一番目の記号から順番に処理され、状態が遷移します。q_0 \rightarrow q_0 \rightarrow q_1 \rightarrow q_0 \rightarrow q_0という内部状態の遷移を経て、最終的に受理状態であるq_0で落ち着きます。
何でその5つの経路をたどる？aabという3つの文字の入力から何が起こっているのか...
プログラムでif文で偶数の判定してるとかでもないしなー、何だこれ
んー、ちょっとわからんので他の記事見るか

まず、定義からちゃんと見ていこう

https://e-words.jp/w/チューリング完全.html
チューリング完全（Turing complete）とは、何らかの計算を行う機構(論理回路や人工言語とその処理系など)が、万能チューリングマシンに等しい能力を持っていること。あらゆる計算を記述、実行できることを表す。
なるほど、じゃあ万能チューリングマシンとは何かを次に調べれば良い

ふむふむ
チューリングマシンは1936年にイギリスの数学者アラン・チューリング（Alan M. Turing）が考案した計算機械の数学的なモデルで、形式的な記号操作の組み合わせ、繰り返しで構成されるすべての計算を実行することができる
雑に言うと四則演算ができるってことかな

なるほど...？
チューリングマシンの構成や動作は符号列として定義および記述することが可能だが、任意の符号化されたチューリングマシンを受け取って、その動作を完全に真似ることができるチューリングマシンを「万能チューリングマシン」（universal Turing machine）という。
チューリングマシンを完全に真似できるチューリングマシンのことを万能チューリングマシンと呼ぶ

ほー
汎用のソフトウェア開発を念頭に開発されているマイクロプロセッサ（CPU/MPU）やほとんどのプログラミング言語はチューリング完全だが、組版言語のTeXやC言語のプリプロセッサなど、プログラミングを主用途としない言語などでも（開発者が意図せず）チューリング完全になっているものがある。
じゃあかなり身近って考えて良さそう
たしかに四則演算は当然できそう

読みづらくても計算できれば万能チューリングマシンやでーみたいな感じか

あくまで理論上は万能チューリングマシンを構成可能であるという意味であり、効率性や可読性は考慮されない。極限まで言語仕様を縮小した数語程度しか命令語を持たない難解なプログラミング言語（ほとんど実用にはならない）や、極めて単純な論理回路などでもチューリング完全となりうることが知られている。

次は、同じIT用語辞典のサイトでチューリングマシンについて詳しく見ていこう

ほんとに四則演算だけできるという定義で良いのか不安だし

なるほどぉぉ～おもしろい
チューリングマシンはマス目に分かれた任意の長さのテープと、テープの上を一マスずつ前後に移動でき、現在位置のマス目の記号を読み取ったり書き込んだりできるヘッドで構成される。
ヘッドは「状態」（内部に記憶された値）を一つ持つことができ、読み込んだ記号と現在の状態の組み合わせによって次の行動を決定する（ヘッドの制御部を独立した要素とみなす場合もある）。ヘッドの行動は3種類あり「テープ上でどちらかの方向に一マス移動する」「現在のマスに記号を書き込む」「内部の状態を変更する」のいずれかを行う。
この機械に外部から、有限個の記号の定義、あらかじめ記号の列が書き込まれたテープ、ヘッドの状態を遷移させる規則の集合（ある「記号-状態」の組み合わせの時にどのような動作を行うかを列挙した表）を与えると、規則に従って次々にヘッドが動作する。
状態遷移表で終了と定義された状態にたどり着くと計算は終了し、その時テープに記載された記号列が計算結果となる。これらは現実のコンピュータにおけるソフトウェア（数学的にはアルゴリズム）に相当する。
テープとヘッドと内部状態かー

なるほど～～

 万能チューリングマシン (universal Turing machine)チューリングマシンの動作を定義する記号集合や初期状態、遷移表などは何らかの規則に基づいて符号化し、特定の符号の列（例えば0と1の並んだビット列）として表現することができる。
このとき、任意の符号化されたチューリングマシンを受け取って、その動作を完全に真似ることができる特殊なチューリングマシンを構成することができ、これを「万能チューリングマシン」（universal Turing machine）という。
論理回路やプログラミング言語とその処理系など、何らかの計算機構が万能チューリングマシンとしての能力を持つことを「チューリング完全」（Turing complete）あるいは「計算完備」であるという。
チューリングマシンの存在そのものや動き方の規則なども全部ビット列で符号化して表してしまい、そのビット列を渡すだけで同じ動きを真似できる機械があったら、それを万能チューリングマシンと呼ぶ
んでその万能チューリングマシンの能力を持つ状態を「チューリング完全」とか「計算完備」と呼ぶ

図解してるわかりやすそうなのがあったので見る
https://cocolofun.co.jp/turing-machine/

ほー、言語化おもしろい

チューリングマシンの特徴は極めて単純です。

$q S S' q'$
この式が表す意味は「qという内部状態において、外部の特定変数を観察して、それがSならば、
外部にS’という働きかけを行い、内部状態をq’に変化させる」ということです。

なるほど
このときqとSの組み合わせに対してことなるS’とq’はあってはなりません。
例えば「1という状態において+1という働きかけを行い内部状態を2に変化させる」みたいなことです。

このとき何度繰り返しても+1をしたらいくつ変化するかは同にならなくてはなりません。
でもSってなんだ？？qとS'とq'しか出てきてない気が
あー普通にif文の条件式で用いるための外部にあるグローバル変数みたいなことなのかな？

ふむ

そして、内部状態が観察する変数を選んでいるということも特徴です。
あくまでヘッドのある場所に書き込まれている0か1という記号を見て判断します。

計算機械としてはS’という働きかけはヘッドを左右に動かして、
指定された記号、0又は1を書き込むことで行います。

より詳しくは以下pdfらしい。読んでみるか

へー、人間の思考プロセスを振り返ることでモデル化したのか

チューリングは 1936 年の論文 7) のなかで，計算者（computer）である人が紙，鉛筆，消
しゴムなどを使って行う計算の過程を思い浮かべて分析し（図 4・1 はその想像図），その動
作を非常に単純な，思考上の機械によってモデル化した

有限制御部というのが内部状態のことだな多分
チューリング機械は，概念的には図 4・2 のように，ます目に分割され左右に無限に伸び

たテープ，有限制御部，及びテープ上の記号を読み書きするためのヘッドから構成される
うん、やっぱりそうだ
そして，この記号と現在の有限制御部の状態（内部状態）に

「記号を書き換え」る理由がわからない。記号は読み取るために用意されているだけなので、それを用いて計算して内部状態書き換えるだけで良いのでは？

まず，ヘッドが位置するます目の記号を読み取る．そして，この記号と現在の有限制御部の状態
（内部状態）に依存して，このます目の記号を書き換え，ヘッドを左か右に 1 コマ移動し，内
部状態を遷移させる．このような動作の規則を適切に定めることによって，いろいろな計算
をチューリング機械に実行させることができる

チューリングマシン(チューリング機械)ならどんな計算でもできる

そしてチューリングは，実行可能な「あらゆる計算」がこのチューリング機械という枠組みのなかで定式化できるのだというテーゼを主張した（チャーチ-チューリングの定立〔本章 4-6 参照〕）．彼の主張は「計算可能性」の概念の定義であるとも解釈できるが，この定義の適切性は今日に至るまで広く認められている

必要そうな数学知識
「属する, \in」は要素と集合の関係、「含む, \subset」は集合と集合の関係
https://math.nakaken88.com/textbook/basic-confusing-set/
なるほどなーイプシロンというものが何となくわかった、案外簡単だ

\varepsilon(イプシロン) ・・・ 関数実行結果と極限値の差分(0に近い) よりギリ大きいもの

\delta(デルタ) ・・・ 関数の引数とその収束地点の差分(0に近い) よりギリ大きいもの
https://mathlandscape.com/eps-delta/
まぁ要は「収束って実際にその値になる訳じゃないからほんのちょっっとだけ誤差出ちゃうはずだよね、それをイプシロンと置こうね」てだけの話かも
てか\varepsilon(イプシロン)と\in(属する)って似てるから注意だな

それを踏まえて定義を見る
チューリング機械は，形式的には T = (Q, S, q_0, q_f, b, \delta) によって定義される．ここで，Qは内部状態の有限集合，S はテープ記号の有限集合，q_0 (\in Q) は初期状態（動作を開始するときの状態），q_f (\in Q) は最終状態（受理状態ともいい，出力または答が得られたことを表明する状態），b (\in S ) は空白記号でテープの有限個のます目を除く残りすべてのます目に b が書かれていると仮定する．\delta は Q × S × S × \{L, R\} × Q の部分集合であり，動作規則の集合を表す．
なるほど。\deltaだけよくわからん

Q ・・・ 内部状態の有限集合

S ・・・ テープ記号の有限集合

q_0 (\in Q) ・・・ 初期内部状態

q_f (\in Q) ・・・ 最終内部状態

b (\in S ) ・・・ 計算に使わない余白(?)
まぁ図を見れば何となくイメージはできる

\delta ・・・ 動作規則の集合(いろいろ掛けたものの部分集合)

\{L, R\}がわからん、あと何でそんな掛けるのかもわからん

\deltaについての更なる説明。なるほどー
\delta の各要素は，[q, s, s', d, q'] のかたちの 5 項組で，これは T が状態 q で記号 s を読んだ場合，記号を s' に書き換え，ヘッドを d 方向に移動し（d = L のときは左，d = R のときは右），状態を q' に遷移させるという動作を表しており，機械に対するある種の命令と考えられる．
qの状態で記号sを読む

↓

記号をs'に書き換える(ここの理由がやはりわからん)

↓

ヘッドをd方向に移動する

↓

状態をq'に遷移(変更?)する
...というのを規則として一般化した集合が\delta

ほう
もし T が状態 q で記号 s を読んでいるにもかかわらず，[q, s, s', d, q'] というかたちの 5 項組が \delta 中に存在しないならば，T は停止する．
具体例見ないとよくわからないけどまぁ一旦ok

ふむ
ここでもし，\delta 中の任意の異なる二つの 5 項組 [q_1, s_1, s_1', d_1, q_1'] と [q_2, s_2, s_2', d_2, q_2'] に対し，q_1 = q_2 ならば s_1 \neq s_2 という関係が成り立つなら，T を決定性チューリング機械と呼ぶ．そうでないものを非決定性チューリング機械と呼ぶ．
んーつまり「状態が同じなら読む記号は違う」ということか。どういうことだろう

非決定性チューリング機械は，次に行う動作が 2 通り以上あり得るような機械である．

ここで次のような簡単なチューリング機械の例 $T1 = (Q_1, \{0, 1\}, q_0, q_f, 0, \delta_1)$ を考える．ただし， $Q_1 = \{q_0, q_1, · · · , q_7, q_f\}$ であり， $\delta_1$ は以下の 5 項組集合である．
$\delta_1 = \{\\ [q_0, 0, 0, R, q_1], \enspace [q_1, 0, 0, R, q_f], \enspace [q_1, 1, 0, R, q_2],\\ [q_2, 0, 0, R, q_3], \enspace [q_2, 1, 1, R, q_2], \enspace [q_3, 0, 1, R, q_4],\\ [q_3, 1, 1, R, q_3], \enspace [q_4, 0, 1, R, q_5], \enspace [q_5, 0, 0, L, q_6],\\ [q_6, 0, 0, L, q_7], \enspace [q_6, 1, 1, L, q_6],\\ [q_7, 0, 1, R, q_1], \enspace [q_7, 1, 1, L, q_7] \\\}$
$T_1$ は，非負整数 $n$ の単進表現（記号 1 を $n$ 個並べたもの）が書かれたテープが与えられ，ヘッ
ドを単進表現の左隣のます目に置いて初期状態 $q_0$ から動作を開始したとき， $f(n) = 2n$ の単
進表現を書き出して最終状態 $q_f$ で停止する決定性チューリング機械である（図 4・3 参照）．

ん－わからん。飛ばす

この例から類推できるように，数の表現法を適切に定めることで，チューリング機械による関数の計算の概念を定式化できる．5 項組集合はいわばチューリング機械のためのプログラムであり，これを適切に与えることにより，実にいろいろな関数が計算できる．そして，チューリング機械で計算できる任意の関数は帰納的関数（recursive function）5) と呼ばれる関数であり，逆に任意の帰納的関数はチューリング機械で計算できることが示されている．従って帰納的関数の族とチューリング機械で計算できる関数の族は一致する．
いろいろ計算できる、一般化できる
チューリングマシンで計算可能な関数を帰納的関数と言う
一般化という意味で帰納という言葉を使っているのだろう

チューリングマシンで計算可能なら帰納的関数だし、帰納的関数ならチューリングマシンで計算可能という両方向の論理が成立する
でもそもそも帰納的関数の定義がチューリングマシンで計算可能という意味なのでそりゃあそうでは...？

とにかく、計算可能な関数はチューリング機械使えば絶対にすべて計算できるよ、という話
これらにより，計算可能と考えられる関数はすべてチューリング機械で計算できるという，チューリングのテーゼの妥当性が更に裏付けられることになり，「計算万能性」を有するような理論的モデルのなかで最も標準的なものとなっている．

やっぱり模倣できるかどうかが万能かどうかの違いか

 4-3 万能チューリング機械チューリング機械（Turing machine: TM）のなかには「あらゆる」チューリング機械をそれ 1 台でシミュレートできるような，そういう TM がある．これを万能チューリング機械（universal Turing machine: UTM）と呼ぶ．このような機械が構成できることはチューリング自身によって示されている10)．本節では，UTM がどのように構成できるのか，その概略を述べた後，小サイズの UTM に関する話題を解説する．
あらゆるチューリングマシンを1台でシミュレートできるかどうか
universal(普遍/一般/万国共通)を万能と訳しているのか

なるほど～～
UTM U は，任意の TM M の動作を模倣（シミュレート）できるような機械である．その

ためには，M の記述と，M に与える入力の記述を，U に入力として与える必要がある．U は

それらを参照しながら M の動作を模倣し，M が最終的に出す答（出力）を U の答とするの

である．
Uに「Mへの入力」と「M自身」の2つを与えるだけで、UはMのように振舞えるってことか

ほー、人間みたいに自立して計算できるようになるって感じか

$M$ の記述が 5 項組集合（チューリング機械〔本章 4-1 参照〕）として与えられたならば，人が紙と鉛筆を使ってその動作を追うのは，いくぶん退屈で手間はかかるが，難しいことではない．UTM $U$ はそのようなことを自身のテープ上で行うだけなので，基本的に困難な点はない．

よくわからんけど何となくわかった
U が模倣する TM M は，片無限テープをもち，記号数が 2 である決定性 TM であると仮定する（一般の TM はこのような TM で模倣できるので，このように制限しても差し支えない）．U のテープ上に，M の記述つまり 5 項組集合を蓄えるセクションと，M のテープを模倣する片無限のセクションを用意する（図 4・4 参照）．M の各 5 項組は，U が用いるテープ記号の列によって表現する．また各セクション中，M のヘッドの位置と，次に実行すべき Mの 5 項組の位置に印をつけておく（図 4・4 では，それぞれ赤の三角と赤の丸印で表示）．Uはまず，次に実行すべき 5 項組を読み取り，テープに書くべき記号とヘッドの移動方向を有限制御部に記憶したうえで，U のヘッドを M のヘッド位置まで移動する．そして，記号の書換えと M のヘッドの移動を模倣し，M の新しいヘッド位置にある記号を読んで有限制御部に蓄える．次に，今実行している 5 項組の位置まで U のヘッドを戻す．そうすると，次の時刻の M の状態が分かり，それと M が読んでいる記号とから，次に実行すべき 5 項組が決まるので，その位置に赤の丸印を移動する．以上で M の 1 ステップの動作の模倣が完了する．U はこの動作を M が停止するまで反復すればよい．
U自体がチューリングマシンであるというよりUはMのシミュレートするのが上手い、て感じなのかな

シミュレート方法はいろいろあるのか

$U$ による $M$ の直接的な模倣法は基本的には上のとおりであるが，多くのバリエーションがある．また後述のように，TM 以外の計算万能なシステムを模倣することによっても UTM が得られる．

もういいかな、まとめるか。雑に

 チューリング完全とは万能チューリングマシンに等しい能力をその機構が持っていること
万能チューリングマシンとは、チューリングマシンをシミュレートできるマシン
チューリングマシンとは、テープとヘッドと内部状態の3つをうまく使って、あらゆる計算をするマシン
テープ：0/1のビット(記号)が並んでる
ヘッド：テープを読み取るポインタ的なやつ。こいつが行動主体
内部状態：計算結果の過程が更新・保持されるところ

関連して、これも面白くて勉強になるな

Brainfuckがチューリング完全だから、それをGithub Actionsで実装することでGitHub Actionsもチューリング完全であると証明する試み

https://zenn.dev/cybozu_ept/articles/github-actions-is-turing-complete
チューリング完全性の説明の前に、チューリングマシンの説明が必要です。チューリングマシンとは、単一のアルゴリズムのみ実行可能な計算機のことです。例えば、回文の判定のみ可能なチューリングマシンや、ナップサック問題を解くチューリングマシンなどが考えられます。チューリングマシンの力は凄まじく、任意のチューリングマシンを模倣可能なチューリングマシンを作ることもでき、これは万能チューリングマシンとして知られています。少しややこしいかもしれませんが、万能チューリングマシンはプログラミング言語で、チューリングマシンはプログラムに相当すると考えるとわかりやすいかもしれません。
なるほど、チューリングマシンがプログラムで、万能チューリングマシンがプログラミング言語かぁ

万能チューリングマシンでも、無限ループするかどうかの判定はできないってことか、へぇ

チューリング完全より強力な計算能力は今のところ発見されておらず、実際ほとんど全ての計算が可能です。ほとんど全てというのは、万能チューリングマシンでも解けない問題が存在しているためです。その代表格が停止性問題であり、これは「任意のプログラムに対して、そのプログラムが有限時間で停止すると判定可能なアルゴリズムは存在するか？」という問題です。そのようなアルゴリズムは存在しないと証明されているため、万能チューリングマシンを持ってしても停止性問題は解けません。

このスクラップは2025/01/21にクローズされました