|||
在p/np问题中,有人将非确定型图灵机理解成所有的图灵机,这混淆了有限与无限的根本区别,是产生悖论的本质性原因。请注意,任何一个图灵机都是一个有限状态机。但所有图灵机的概念下,就意味着无限多个图灵机,也就是说论域从有限状态一下子变成了无限状态,而无限状态的机器已经失去了图灵机概念的本质,还谈什么非确定型图灵机?将图灵的非确定型图灵机理解成不确定的图灵机或任何的图灵机全体,都会将有限的状态转化过程,无意识地变成了无限的状态转化。这正是p/np问题长期得不到确定答案的一个原因。
如何理解非确定型图灵机,我十分坚定前博文的观点。要知道,图灵机状态有限,但图灵机的数量无限!
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-16 01:12
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社