|||
于博文(http://blog.sciencenet.cn/blog-2322490-874183.html),我们分析了NP二个定义涉及到二个内涵完全不同的“非确定型图灵机”,为了方便表达,我们提议约定几个术语的中文、英文及缩写:
一,术语的约定
TM (Turing Machine) = 图灵机
DTM (Deterministic Turing Machine) = 确定性图灵机
NTM (Non Turing Machine) = 非图灵机
NDTM (NonDeterministic Turing Machine )= 不确定性图灵机
这里,TM=DTM,皆指通常的“图灵机”;NTM ≠ NDTM :
- NTM,指具有“神喻机”意义的“非图灵机(Non Turing Machine)”;
- NDTM,指基于“不确定性自动机”的“不确定性图灵机(NonDeterministic Turing Machine)”。
NTM是图灵在他的博士论文中引入的,用以指称“非图灵机(Non Turing Machine)”。NTM具有的“神喻机”意义,是图灵一种不得已的说法。
我们已指出“不确定性图灵机(NDTM)”的本质是“确定性图灵机(DTM)”,即“图灵机(TM)”,我们将在后面的博文中进一步解读“不确定性图灵机”指称的“不确定性”的本质。
二,“不”与“非”(汉字基因-http://www.hanculture.com/dic/v.php?id=29997&m=jy)
这里,顺便谈一谈中文“不”与“非”:
1,不:鳥上飛無法下來狀,未定也。
2,非:兩翅一左一右,反背也,不是也。
于是,“不”具主观、动态;“非”具客观、静态。但是,于西文却无法区分“不”与“非”。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-23 16:58
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社