评论详情页
hidden
杨正瓴 赞 +1
(1)目前不少人将
non-deterministic Turing machine
缩写为
NTM。
  
(2)俺最喜欢的缩写
deterministic Turing machine = DTM,
non-deterministic Turing machine = NDTM。

不过,经常被迫使用
non-deterministic Turing machine = NTM。
2015-04-10 20:13
全部回复1 条回复
hidden
柳渝 赞 +1
目前学术界对“nondeterministic Turing machine”持的二个观点:
- A nondeterministic Turing machine is a "parallel" Turing machine that can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate (http://mathworld.wolfram.com/NondeterministicTuringMachine.html).
- The computation process of a nondeterministic Turing machine can be interpreted as a (deterministic) Turing machine with the capability to create and start other Turing machines processing “alternative” branches of the calculation (http://www.encyclopediaofmath.org/index.php/Nondeterministic_Turing_machine).

正是我们在博文(NP定义中二个不同的“非确定型图灵机”)中解读的二个内涵不同的“非确定型图灵机”:
- “并行(parallel)的nondeterministic Turing machine”=神喻机,在多项式时间内能够判定NP;
- “串行(alternative)的nondeterministic Turing machine”=图灵机,在多项式时间内不能判定NP。

所以,须将二者放开,这就是我们提议区分NTM和NDTM的目的。
04-10 22:26
确定删除指定的回复吗?
确定删除本博文吗?