理論チューリングマシン

author: 371tti


article, inbox, theory, turing machine

理論チューリングマシンとは一般に、計算可能性を研究するための抽象的な計算モデルである。 これらのほとんどは現実に存在しない。

Accelarating Turing Machines

Zeno's paradox of Achilles and the tortoise から着想を得た理論的なチューリングマシンの一種。
加速チューリングマシンは、各ステップの実行時間が前のステップの半分になるように設計された理論的な計算モデルである。 これはつまり実行時間が収束することを意味する。

∑n=0∞12n=1

このチューリングマシンマシンは理論上有限時間で無限の計算を行うことが可能だ。

関連として、一般相対論における特殊な時空構造、特に Malament–Hogarth 時空や回転ブラックホール時空を用いれば、理論上は有限時間で無限計算の結果を観測できる可能性が議論されている。
ただし、これは強く理想化された議論であり、実際にそのような計算装置を物理的に実現できるかは未解決である。

BSS Machines

BSSマシン（Blum–Shub–Smale machine）は、実数上の計算を直接扱うチューリングマシンである。
通常のチューリングマシンでは数を有限長のビット列として表現するが、BSSマシンでは実数そのものを直接扱えると仮定する。

たとえば通常の計算機では 2 や π を厳密に保持することはできず、近似値としてしか扱えない。
しかしBSSマシンでは、そのような実数をそのまま1つの値として保持し、加減乗除や比較を1ステップで行えると仮定する。

つまり、BSSマシンでは次のような操作が基本になる。

  • 実数レジスタへの値の格納
  • 実数どうしの加算・減算・乗算・除算
  • x>0, x=0 のような判定
  • 判定結果に応じた分岐

このチューリングマシンは連続量を含む問題を理想化して計算することができる。

特に、代数幾何や数値計算の理論、実数上の計算複雑性を考えるときに有用である。

また理論上BSSマシンは、その特性上並列に状態を分岐させることができるため、非決定性や交替の概念とも関連が深い。

Oracle Turing Machines

一般に信託チューリングマシンとは、ある特定の問題を「一瞬で解いてくれるブラックボックス」を持ったチューリングマシンである。
このブラックボックスを Oracle（オラクル : 信託）という。

たとえば、ある言語 A に属するかどうかを即座に答えてくれるオラクルを持つマシンを考えることができる。
このときマシンは、自力では難しい問題を解く途中で、そのオラクルに問い合わせを行える。

これは現実にそのような装置があるという話ではない。
むしろ、

  • ある問題を解けると仮定すると、他の問題はどこまで簡単になるか
  • 計算能力の差はどの程度あるか
  • 複雑性クラスの相対化をどう考えるか

といったことを調べるための道具である。

たとえば複雑性理論では、PNP のように「NPのオラクルを使えるP」という記法が現れる。
これは「NP問題を問い合わせによって即座に解けるなら、多項式時間で何ができるか」を表している。

オラクルは計算の本質を考える上で非常に便利だが、現実世界に信託が存在しないことを忘れないようにする必要がある。

Nondeterministic Turing Machines

非決定性チューリングマシンとは、分かれ道があるたびに、可能なすべての選択肢に同時に進めると考える理論上のチューリングマシンである。

普通のチューリングマシンは、次の動作が必ず1つに決まる。
しかし非決定性チューリングマシンでは、次の動作が複数あってよい。

そして、その計算の分岐のうち、1つでも受理に到達すれば受理とみなす。

これは現実の機械というより、「解が存在するか」を考えるための理論モデルであり、複雑性理論で重要である。
たとえば NP は、この非決定性チューリングマシンで多項式時間以内に解ける問題として定義される。

Alternating Turing Machines

交替チューリングマシンは、非決定性チューリングマシンをさらに一般化したモデルである。
このモデルでは状態が 存在状態 と 全称状態 に分かれる。

  • 存在状態では、遷移先のうち少なくとも1つが受理なら受理
  • 全称状態では、遷移先のすべてが受理でなければ受理しない

これは論理式でいう ∃ と ∀ を計算に組み込んだものとみなせる。

非決定性チューリングマシンが「どれか1つ成功すればよい」モデルだとすると、交替チューリングマシンは「ある分岐では全て成功しなければならない」という条件まで扱える。
そのため、論理式評価やゲーム的な問題の表現と相性がよい。

交替計算は複雑性理論で非常に重要であり、空間計算量との深い関係が知られている。
たとえば多項式時間交替チューリングマシンは PSPACE と対応する。

Quantum Turing Machines

量子チューリングマシンは、量子力学的な重ね合わせや干渉を取り入れた理論計算モデルである。
通常のチューリングマシンでは計算状態は1つに定まるが、量子チューリングマシンでは複数の計算状態の重ね合わせとして進行する。

そのため、ある計算経路が他の計算経路と干渉しあい、特定の答えの確率を高めたり打ち消したりできる。
これは単なる並列実行ではなく、複素振幅に基づく量子的な計算である。

量子チューリングマシンは、量子回路モデルとほぼ同等の理論的計算モデルとして扱われることが多い。
実際の量子アルゴリズムを議論するときは量子回路のほうが使いやすいが、計算可能性や計算複雑性の一般論では量子チューリングマシンも重要である。

また Nondeterministic Turing Machines と異なる点として、量子チューリングマシンは「どれか1つ成功すればよい」モデルではなく、確率的な成功率を持つモデルであることが挙げられる。

まとめ

これらをもとに「停止性問題を解くために、まず Kerr ブラックホールを用意します。」とかをつぶやきましょう。??????????????????