评论详情页
杨正瓴
赞
+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
non-deterministic Turing machine
缩写为
NTM。
(2)俺最喜欢的缩写
deterministic Turing machine = DTM,
non-deterministic Turing machine = NDTM。
不过,经常被迫使用
non-deterministic Turing machine = NTM。
全部回复1 条回复
柳渝
赞
+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的目的。
- 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