チャーチ・チューリングのテーゼは「この世界の物理法則で計算可能な関数のクラス」を表していると捉えると、厳密に定義できる命題に思える1。極端な例だけれど、ある種のタイムマシンがある世界では、チューリングマシンの計算能力を超える機械が作れたりするんではなかろうか。逆にいえば、チャーチ・チューリングのテーゼが正しいという仮定は物理法則に制限を与える。具体的に定義してみようとすると、インプット・アウトプットをどう定義すべきか私にはよく分からないのだけれど。
追記: 非決定性チューリングマシンは (おそらく) この世の物理法則を超えているので、上の文章は適切とは言えないか。
もちろん物理法則が完全に理解されているという (とんでもない) 条件のもとで。
Backlinks: [202024300].