博文
量子计算机加法运算的非确定型图灵机实例，p＝np
|||
量子运算的图灵机
姜咏江
毫无疑问，量子计算机是使用四进制进行计算的。我们就用二位二进制数来做一个非确定型量子加法运算的图灵机。
非确定型图灵机定义如下：
A non-deterministic Turing machine can be formally defined as a 6-tuple
Μ=(Q，Σ，β，□，Α，δ）, where
Q is a finite set of states
Σ is a finite set of symbols (the tape alphabet)
β∈Q is the initial state
□∈Σis the blank symbol
Α< Q is the set of accepting (final) states
δ( QΑ×Σ)×(Q×Σ×{L,R}) is a relation on states and symbols called the transition relation.
图灵定义的机器多了一个｛L，R｝这是为了编排带子上的输出而已。不考虑输出形式可以将二进制二位数的加法的转移关系设计成表1。其中β=q0,Σ={00,01,10,11}，Α=q5,β=q0，Q =｛q0，q1，q2，q3，q4，q5｝。
表1 四进制一位数加减法图灵机
序号 | （q0）加运算（q1） | ||
0 | 输入a | 输入b | 输出a+b |
1 | （q1）00（q2） | （q2）00（q0） | 00 |
2 | （q2）01（q0） | 01 | |
3 | （q2）10（q0） | 10 | |
4 | （q2）11（q0） | 11 | |
5 | （q1）01（q3）
| （q3）00（q0） | 01 |
6 | （q3）01（q0） | 10 | |
7 | （q3）10（q0） | 11 | |
8 | （q3）11（q0） | 00 | |
9 | （q1）10（q4） | （q4）00（q0） | 10 |
10 | （q4）01（q0） | 11 | |
11 | （q4）10（q0） | 00 | |
12 | （q4）11（q0） | 01 | |
13 | （q1）11（q5） | （q5）00（q0） | 11 |
14 | （q5）01（q0） | 00 | |
15 | （q5）10（q0） | 01 | |
16 | （q5）11（q0） | 10 | |
表1的输入a和输入b中间是状态转移输入的两位二进制数，左边括号内的q是输入时的状态，右边的q是输入之后转移的状态。将｛L,R｝的输出用输出a+b表示。由于输出是限制在2位的二进制数中，请用限位数理论思考。
这张表似乎与图灵给出的表结构有些不同，其实将输入b与输出a+b的每4行插入输入a栏的后面，就是图灵给出的三栏式了。将输出改成相应的减法运算结果，那么就是一个减法图灵机。
由于“Σ is a finite set of symbols”，故而运算的结果一律应在Σ中。
请注意，表中的两位二进制数可以用0，1，2，3来替代，用限位数的理论来思考，在我设计的这种图灵机上显然已经 是 “p=np”了。
2014-11-8
https://blog.sciencenet.cn/blog-340399-841997.html
上一篇：p与np问题的钥匙__限位数
下一篇：N位二进制数加减法运算图灵机
