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