探针机:从底层全并行的计算模型

左:连接型探针机模型  右:传递型探针机模型
左:连接型探针机模型 右:传递型探针机模型

近日,北京大学信息科学技术学院、高可信软件技术教育部重点实验室许进教授所撰写的《探针机》(Probe machine)一文,在美国电气电子工程师学会(the Institute of Electrical and Electronics Engineers)主办的《神经网络与学习系统汇刊》(IEEE Transactions on Neural Networks and Learning Systems)第27卷第7期上作为当期首篇文章发表。

该文提出了人类首次超越电子计算机的图灵机(Turing machine)模型,称之为探针机。探针机由数据库、探针库、数据控制器、探针控制器、探针运算、计算平台、检测器、真解存储器和残支回收器等9个部分组成,分为连接型与传递型两种。

文中指出,对于当今电子计算机无法处理的NP完全问题,如图的哈密尔顿(Hamilton)问题、图的顶点着色问题等,利用探针机,只需一次探针运算,即可求出问题的全部解。由于基于图灵机的所有NP完全问题在多项式时间内是等价的,这就意味着在探针机模型下不再有困惑人类的NP完全问题。

对于以何种材料来制造探针计算机,该文也给出了讨论。文中提出,对于连接型探针机模型,拟采用以纳米颗粒与DNA(即脱氧核糖核酸)分子构成的复合材料作为数据、以DNA分子作为探针的一种探针机的实现技术——纳米DNA计算机;对于传递型探针机模型,则可以进行一种构想:其数据由一种复合体构成,数据纤维中的信息由例如乙酰胆碱(ACH)的神经递质构成,而探针则由类似于生物神经系统中的“动作电位”实现。文章证明了电子计算机的数学计算模型——图灵机仅仅是探针机的一种特殊情况。

许进教授及其研究团队长期从事生物计算数据编码与模型构建的理论和方法研究,先后5次任“生物计算:理论与应用”国际会议(International Conference on Bio-inspired Computing: Theory and Applications)主席;由他作为第一完成人的项目“生物计算中数据编码与模型构建理论方法研究”荣获2013年度国家自然科学二等奖。

探针机的研究得到了国家重点基础研究发展计划(“973计划”)课题,国家自然科学基金科学仪器基础研究专项、重点项目、重点国际(地区)合作研究项目等资助。

论文链接:http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7466831&newsearch=true&queryText=probe%20machine

(据北京大学)

 

原创文章,如若转载,请注明出处:https://www.scieau.com/articles/2016072046

Copyright © 2016-2021 沙鸥科报 版权所有 - 沪ICP备17044971号-2