UTM騒ぎ

CS

/.-Jで「Wolframが提唱したTuring機械がuniversalだと証明された．これは最小のUTMが見つかったことを意味する」との記事を読んで，これは証明を眺めてみたいと強く思ったのだが，証明の印刷を忘れたまま帰ってきてもう一度/.-Jを見たら，なんと証明に初歩的な誤りが発見されたそうではないか．

しかしこれは定義をどう取るかの問題で，「こんな基礎の定義も知らない初歩的な誤り！」と切って捨てるのは微妙らしい？

... When Minsky posed the question of finding the smallest universal Turing machines in 1967 [1], he restricted the problem to Turing machines with finite initial conditions. Indeed, arbitrary infinite (but non-computable) initial conditions can allow a machine to solve the halting problem and perform other miraculous computations that are seemingly impossible in our physical universe. Clearly, Minsky was justified in forbidding arbitrary infinite initial conditions.

But later researchers, namely [2], noted that although arbitrary infinite initial conditions should not be allowed, that interesting results could be obtained if Minsky's restrictive definition of a 'universal Turing machine' were relaxed to allow repetitive infinite initial conditions. This relaxing of the restriction on a Turing machine's initial condition generalizes the definition of a universal Turing machine, and allows machines that were previously non-universal to be considered universal.

Of course, once one allows repetitive infinite initial conditions, one is compelled to ask what sort of non-repetitive infinite initial conditions might be allowable. Again, one does not want to allow arbitrary infinite initial conditions, since trivial machines would become universal, but how far can one relax the restriction on initial conditions, and still retain a reasonable definition of a universality? ...

Smith's use of non-repetitive infinite initial conditions is controversial, but is a natural extension of current definitions which allow infinite repetitive initial conditions. ...

[2] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of ACM, 8(4):476-483, October 1961.

（強調はflatlineによる）

「オーソドックスな定義に従えば弾かれるが，しかし『万能性』を論ずる意義は保たれる程度の範囲内での拡張」ということらしい？ これは素人の私にはちょっとよく分からない現状だ．しょうがないので地道に2, 2以下がuniversalたり得ないことの証明でも勉強してみるか．Sipser辺りに載ってる？