読者です 読者をやめる 読者になる 読者になる

>くるるさんがTuring機械と見做せない「機械」としてどのようなものを想定されているのか想像が付きません。
いくらでもあると思うんですが。AIBOとかブルドーザーとか水車とか。アナログな入出力があった時点でTuring機械とはみなせないわけで。もう少し文脈に沿ってイメージしていたのは、

  1. 勝手にウェブをクロールして新しい情報を追加していくようなもの。(人間からのインプットがあるのはルール違反といえばそうかもしれませんが)
  2. シュレーディンガーの猫を定期的に観察して、その出力をオラクルとして使うようなもの。

特に2がTuring機械で表せるなら、シュレーディンガーの猫の生死を判定するアルゴリズムが存在して、多分不確定性原理に反するのではないかと思っていたのですけど。

乱数を扱えるチューリングマシンを考えれば2は解決すると思います.
例えば,

  1. ポアソン過程からのサンプリングを行って猫が死ぬ時間を決める
  2. その時間までは生存と答え, 時間後は死亡と答える

ってのはどうでしょう.

量子チューリングマシンを使って良いのならば, そのオラクルを具体的に構成できます. オラクルの返答は生死の重ね合わせです. この場合は観測はオラクルを呼んだ側が行います.

(呼び出し: id:kumano_tarou)