CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

量子计算机加法运算的非确定型图灵机实例,p=np

已有 7022 次阅读 2014-11-8 09:25 |个人分类:科研讨论|系统分类:科研笔记| 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.

图灵定义的机器多了一个{LR}这是为了编排带子上的输出而已。不考虑输出形式可以将二进制二位数的加法的转移关系设计成1。其中β=q0,Σ={00,01,10,11}Α=q5,β=q0Q =q0q1q2q3q4q5}。

1  四进制一位数加减法图灵机

序号

q0)加运算(q1

0

输入a

输入b

输出a+b

1

q100q2

q200q0

00

2

q201q0

01

3

q210q0

10

4

q211q0

11

5

q101q3

 

q300q0

01

6

q301q0

10

7

q310q0

11

8

q311q0

00

9

q110q4

q400q0

10

10

q401q0

11

11

q410q0

00

12

q411q0

01

13

q111q5

q500q0

11

14

q501q0

00

15

q510q0

01

16

q511q0

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位二进制数加减法运算图灵机
收藏 IP: 123.119.80.*| 热度|

0

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

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

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

GMT+8, 2024-12-23 11:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部