NP, NP-completeness (1) - Thoughts版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Thoughts版 - NP, NP-completeness (1)

相关主题
● NP, NP-completeness (2)	● 到底是和人打交道的工作好还是和机器打交道的工作好
● NP, NP-completeness (3)	● 到底谁快？我？还是光？
● Life is a BIG jigsaw puzzle	● 真的是很奇妙阿
● Re: 精神和肉体是分离的吗？	● PLATO除了REPUBLIC
● 也谈谈共产党的成功和蒋介石的失败	● 下一步，下一步该怎么做？
● Re: 你们多久洗一次袜子？ (转载)	● Re: 誓死保卫孙总理，反击右倾翻案风！
● 高考就是这么回事，对人生没多少决定性的影响	● 第一次来
● 关于圣经问题的回答	● 赞红狼啊

相关话题的讨论汇总
话题: 图灵机话题: np话题: 指令话题: nt

进入Thoughts版参与讨论

(共1页)

wy
发帖数: 14511

为了清晰化大家关于AI的讨论，偶不得不
首先引入以下概念：
1. 非决定性与决定性图灵机：
为了不过于复杂，我们从决定性图灵机出发，
大家可以把决定性图灵机想象成一般的计算机：
每次执行一条指令。在开始，图灵机有一个初使
状态，以后每走一步，图灵机的内部状态--内存的
内容会有改变，联系和当前执行的指令，我们称之为
图灵机的一个状态。
一个图灵机程序是一个“是”“非”测试，在程序执行
完毕后，图灵机应该either accept or reject程序。
非决定性图灵机：从图灵机的当前状态出发，图灵机
的下一个指令是概率的，即，下一步执行哪一条指令，
被一个概率函数决定。注意，这不是因为跳转指令，
而是非决定性的天生性质。
两个重要的区别在deterministic Turing machine and nondeterministic
Turing machine(NT):
1. 在某一步，NT可能选择什么也不执行。由此程序停止，但是既不接受也
不拒绝程序。
2.事实上，NT只有接受状态，而没有拒绝状态。
给一个例子说明一下：
比如说给定一个二叉树，找叶子的值为2者，用决定性图灵机大

(共1页)

进入Thoughts版参与讨论

相关主题
● 赞红狼啊	● 也谈谈共产党的成功和蒋介石的失败
● 转载：人的生活方式	● Re: 你们多久洗一次袜子？ (转载)
● 每一步路都意义非凡	● 高考就是这么回事，对人生没多少决定性的影响
● 究竟应该怎样过好这一生	● 关于圣经问题的回答
● NP, NP-completeness (2)	● 到底是和人打交道的工作好还是和机器打交道的工作好
● NP, NP-completeness (3)	● 到底谁快？我？还是光？
● Life is a BIG jigsaw puzzle	● 真的是很奇妙阿
● Re: 精神和肉体是分离的吗？	● PLATO除了REPUBLIC

相关话题的讨论汇总
话题: 图灵机话题: np话题: 指令话题: nt

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天