不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

NP理论中几个术语的约定

已有 3833 次阅读 2015-4-10 10:24 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 图灵机, versus

于博文(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,非:兩翅一左一右,反背也,不是也。

于是,“不”具主观、动态;“非”具客观、静态。但是,于西文却无法区分“不”与“非”。  




https://wap.sciencenet.cn/blog-2322490-881272.html

上一篇:清明时节忆华工-法国诺莱特华工墓园
下一篇:不确定性图灵机(NDTM)与“不确定性”

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (12 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-5-19 22:46

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部