24小时热门版块排行榜

返回列表

新手已上路

木虫 (职业作家)

应助: 82 (初中生)
金币: 4153.3
红花: 422
帖子: 4933
在线: 616.2小时
虫号: 3474904
注册: 2014-10-14
性别: GG
专业: 元素化学

[交流] 超越图灵机，北大教授提出从底层全并行的计算模型—探针机已有12人参与

计算工具被公认为是推动人类文明发展的主要因素之一，而随着人类文明的进步，计算工具也不断演变。人类的发展可以分为五个阶段：即石器时代，铁器时代，蒸汽时代，电气时代和信息时代。因此，计算工具也经历了从简单到复杂漫长的进化过程中，先后出现了：结绳计数，算盘，计算尺，机械计算机，电子计算机，每一个计算工具在相应历史阶段都发挥了重要作用。
计算机其实就是基于一个计算模型，并用可以实现这个计算模型的某些材料制成的通用设备。例如，今天的电子计算机的计算模型是图灵机，采用的制造材料就是电子元件。
图灵机是由数学家图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

图：图灵机示意图
1945年，冯·诺依曼建立了电子计算机的架构，采用图灵机作为其计算模型，使用半导体作为电子计算机的实现材料。在接下来的一年，第一台冯·诺伊曼架构的电子计算机研制成功。到现在为止，电子计算机的发展经历了四个主要阶段，即管计算机，晶体管计算机，集成电路计算机，和大规模集成电路的计算机。
虽然基于图灵机计算模型的计算设备发展迅速，但科学家们仍然一直在寻求新的计算模型，期望建设更强大的计算机。追求新的计算模型背后的动机主要有两点：1）半导体的制造技术将在未来十年达到它的极限；2）由于图灵机的限制，今天的电子计算机一直未能解决大型NP-完全的问题，如图的Hamilton问题、图的顶点着色问题等。
近日，国际权威杂志IEEE Trans. On Neural Networks and Learn System在2016年第7期首篇报道了北京大学信息科学技术学院许进教授团队在计算机科学领域的重大突破性文章“Probe Machine”（探针机），该文提出了人类首次超越电子计算机的图灵机模型，称为探针机。探针机由数据库、探针库、数据控制器、探针控制器、探针运算、计算平台、检测器、真解存储器及残支回收器等九个部分组成。探针机分为连接型与传递型两种，如图示：

图：连接型探针机模型（左）和传递型探针机模型（右）
文章指出，对当今电子计算机无法处理的NP-完全问题，用探针机求解，只需一次探针运算即可求出问题的全部解。由于基于图灵机的所有NP-完全问题在多项式时间内是等价的，这就意味着在探针机模型下不再有困惑人类的NP-完全问题。

图：传递型探针计算机的生物神经网络示意图
对于用什么材料来制造出探针计算机，文章也给出了讨论。文中提出，对于连接型探针计算机，拟采用以纳米颗粒与DNA分子构成的复合材料作为数据，以DNA分子作为探针的一种探针计算机的实现技术——纳米DNA计算机；对于传递型探针计算机模型的实现，一种构想是：其数据由一种复合体构成，数据纤维中的信息由神经递质构成，诸如乙酰胆碱（Ach）等，而探针则由类似于生物神经系统中的“动作电位”实现。文章证明了电子计算机的数学计算模型——图灵机仅仅是探针机的一种特殊情况。
许进教授和他的研究团队长期从事生物计算数据编码与模型构建的理论和方法研究，先后五次任国际生物计算机大会主席，并在2013年荣获年度国家自然科学奖二等奖。
文章链接：
Jin Xu, "Probe Machine," IEEE Transactions on Neural Networks and Learning Systems, July 2016, DOI: 10.1109/TNNLS.2016.2555845
许进教授简介：
北京大学信息技术学院教授，Email：jxu@pku.edu.cn

回复此楼