博文
N位二进制数加减法运算图灵机
|||
N位二进制数加减法运算图灵机
姜咏江
为了能够更清楚地说明非确定型图灵机可扩充性，特将固定n位二进制数的加减法图灵机的状态转移表设计如下。
表中的数值计算未加详细检查，但详细的方法我想已经表达出来了。同样将表1的“输出a+b”改成“输出a－b”，并把相应值改动，就是减法状态转移关系了。
表1 n位二进制数加减法非确定型图灵机
序号 | （q0）加运算（q1） | ||
0 | 输入a | 输入b | 输出a+b |
1 | （q1）0…0（q2） | （q2）0…0（q0） | 0…0 |
2 | （q2）0…1（q0） | 0…1 | |
… | （q2）……（q0） | …… | |
2n | （q2）1…1（q0） | 1…1 | |
2n+1 | （q1）0…1（q3）
| （q3）0…0（q0） | 0…1 |
… | （q3）0…1（q0） | 0..10 | |
… | （q3）……（q0） | …… | |
22n | （q3）1…1（q0） | 0…0 | |
22n+1 | （q1）0..10（q4） | （q4）0…0（q0） | 0..10 |
… | （q4）0…1（q0） | 0..11 | |
… | （q4）……（q0） | …… | |
23n | （q4）1…1（q0） | 0..01 | |
… | （q1）……（…） | （…）0…0（q0） | …… |
… | （…）0…1（q0） | …… | |
… | （…）……（q0） | …… | |
… | （…）1…1（q0） | …… | |
… | （q1）1…1（q22n+1） | （q2n+1）0…0（q0） | 1…1 |
… | （…）0…1（q0） | 0..10 | |
… | （…）……（q0） | …… | |
2T | （q2n+1）1…1（q0） | 0…0 | |
愿有兴趣的网友侃侃。
注：T=2n
https://blog.sciencenet.cn/blog-340399-842021.html
上一篇：量子计算机加法运算的非确定型图灵机实例，p＝np
下一篇：图灵机状态转移函数为什么是部分函数？
