探针计算机模型及实现研究

A novel underlying full-parallel computing model, called Probe Machine, is proposed in this project. Compared with the sequential processing of linearly-adjacent data in Turing Machine, the Probe Machine can simultaneously process multiple pairs of data. The Probe Machine consists of nine parts, including data library, probe library, data controller, probe controller, probe operation, computing platform, detector, true solution storage, and residue collector. According to the principle that the computer is conceptually a general purpose device integrating computing model with certain materials, the research contents of this project mainly are as follows: to establish a well-defined mathematical model of Probe Machine, and to demonstrate the conjecture that PMs=2^{TMs}; to explore the implementation methods of connective Probe Machine based on DNA nanotechnology, DNA nano-chip and logic switch, and to explore the implementation of transitive Probe Machine by means of neurotransmitter; to investigate the applications of Probe Machine in the aspects of encryption & decryption and solving other NP problems with the help of underlying full-parallel characteristic. The research of this project may break through the bottlenecks of electronic computer technology, enrich the theory and algorithms of DNA nanotechnology, and provide theoretical and technical supports for the development of the relative industries.

本项目提出了一种从底层全并行的探针计算机模型。该模型由数据库、探针库、数据控制器、探针控制器、探针运算、计算平台、检测器、真解存储器与残支回收器等九部分组成。根据计算机=计算模型+实现的材料这一基本原则，项目研究内容主要包括：建立完备的探针机数学模型，对PMs=2^{TMs}猜想展开论证；在研究DNA纳米颗粒复合物、DNA纳米芯片技术和逻辑开关技术的基础上，探索连接型探针机的实现，采用神经递质等相关技术手段探索传递性探针机的实现；利用探针机从底层全平行这一特点，探讨它在加密解密和求解NP完全问题中的应用。本项目的研究有望突破电子计算机发展所面临的瓶颈，丰富DNA纳米技术的理论与算法，为促进相关产业的发展提供理论和技术支持。

电子计算机不能有效求解NP难问题，本质上，电子计算机的计算模型是图灵机，而图灵机是一种串行操作结构。探针机是项目组在已有研究成果积累的基础上提出的一种新型计算模型，是一种不同于以往任何计算模型的底层并行的计算模型。.项目组在已有定性化的9-元组探针机基础上，建立了定量化探针机模型，数据的表现形式从星图结构转化为一个向量，数据之间的探针转化成向量分量间的算子。以探针机为计算模型，以DNA-纳米为材料建立了DNA-Ⅰ-型和DNA- Ⅱ-型探针计算机模型，其中Ⅰ-型是检测技术依赖于生物检测技术的半自动化计算机；Ⅱ-型是基于光信号、电信号及生物信号相互转换的探针计算机模型。先后完成了6个数据、20个数据的DNA-纳米型探针机的生物实现。针对探针机数据间连接问题，设计了一种可复用并且可控的十字形DNA瓦片结构。通过对DNA序列的编码设计，仅用一种DNA瓦片实现了自底向上形成不同大小和功能化的DNA阵列。实现了DNA折纸阵列设计可复用、可拼接、可控规模、可控结构的DNA阵列组装。开展了对探针计算结果检测的光电转化研究，完成了三色荧光的光电转化、DNA数据荧光基团的单色双色及三色荧光标记、以及基于三角拼接数据的DNA折纸等多项关键技术，三色荧光区分度p值达到0.2、荧光能量共振距离指标达到20nm，技术指标达国际领先水平。在应用方面，项目组提出将整数分解多项式时间规约为唯一图着色的方法，设计了多种有效减少非解的基于探针机的图顶点着色算法。本项目中提出的新型计算模型理论、实现与应用等成果对促进计算机科学、DNA纳米技术、生物医药等相关领域的发展提供了重要理论和技术支持。