超出图灵机的互联网计算(中国计算机学会通讯).docVIP

PAGE 3 PAGE 10 超出图灵机的互联网计算 李德毅1 张海粟2 1中国电子设备系统工程研究所 关键词: 互联网计算 云计算 网络科学 网络化软件 2解放军理工大学 指挥自动化学院 引言 基于IP（Internet Protocol，网际协议）、Web（万维网）和Web服务等标准协议族，互联网应用可以屏蔽底层传输和交换差异，不断向多元化的需求靠近。这不仅促进了用户对信息资源的检索、理解与使用，也改变了传统个人计算环境下，图灵机模型[1]和冯·诺依曼结构[2]作为计算理论基础的状况。在互联网计算环境及云计算模式下，用户以不确定的、智能的交互行为参与到信息的处理中，人机、机机的交互形成了计算节点上持续的输入/输出流。互联网节点间不是以集中统一的控制方式，而是以互操作方式实现尽力而为的服务。因此，与统一调度或单节点上的运算相比，节点之间的交互更加重要。互联网计算的核心转变为节点间通过输入/输出进行互连，超出了图灵机模式，形成了网络化软件工程。 互联网改变了计算机和软件的工作模式 图灵机模型和冯·诺伊曼结构计算机 1936年，图灵（A. M. Turing）的著名论文《论可计算数及其在判定问题中的应用》[1]指出有些数学问题是不可解的，回答了希尔伯特（Hilbert）于1900年提出的逻辑完备性的问题[3]。该文首次提出自动计算机的理论模型（后被广泛称作图灵机），把推理化作一系列简单的机械动作。从20世纪60年代起，计算机理论界开始用图灵机作为说明可计算能力的模型。冯·诺依曼结构[2]是与图灵机模型等价的计算机结构的典型实现，其工作原理的要点为“存储程序”。冯·诺依曼结构由控制器、运算器、存储器、输入和输出设备组成，控制器 按照程序顺序，逐条把指令和数据从存储器中取出并加以执行，自动完成由程序描述的处理工作。 图1 以中央处理器和操作系统为“核”的计算机系统 在冯·诺依曼结构下，由运算器和控制器组成的中央处理器（Central Processing Unit，CPU），承担着数据管理、运算和控制输入/输出的功能。计算机系统一直以中央处理器和操作系统为“核”，如图1所示，由系统软件、中间件和应用软件等逐层???外形成“洋葱”；编程也是由微程序级、一般机器级、操作系统级、汇编语言级和高级语言级等组成不同层次。传统软件工程就是在每一级上进行程序设计的方法，如高级语言级程序设计的过程就是“分析问题—建立数学模型—选择数据结构—设计算法—编程—编译器逐层向下编译成机器可执行代码—机器运行”的过程。因此，传统软件可被认为是“程序（包括算法和数据）+文档”。这种依赖于图灵机模型和冯·诺依曼结构的计算机系统奠定了个人计算环境下计算机与软件的工作模式，即通过计算的核心（中央处理器），对确定的输入通过确定的运算过程，得到确定的输出结果。 互联网发展对图灵模式的挑战 1969年，ARPA1网首次实现计算机间数据传输[4]。从1984年开始，TCP/IP协议族逐渐在互联网上得到广泛应用，形成了“一切基于IP（Everything over IP）[5]”的局面。1989年，万维网[6]将互联网应用推向普通大众，使得信息的大规模共享与交互成为可能。通信、电子等技术为建设互联网基础设施能力提供了重要支撑，吉尔德（Gilder）预言了通信带宽增长速度甚至是芯片的摩尔速度的3倍[7]。从2000年左右开始，为满足大众用户的个性化需求，万维网服务、语义网和Web2.0等通过开放、灵活和大众可参与的服务模式，逐渐将信息及其交互从传统的层次化软件结构里解放出来，促进了网络化软件环境的形成。自2008年，一些IT公司纷纷宣布了各自基于互联网环境的云计算计划。可以看出，通信（尤其是光通信和移动通信）和网络科学（尤其是互联网）比可计算模型和软件理论的发展速度更快，且很快渗透到人类生活中得到普遍应用。 图2 计算环境的变迁 图2显示了计算环境从个人转向互联网的根本性变革。在个人桌面环境下，图灵机和层次化软件是封闭、可控的，操作系统、数据、应用程序、计算和输入/输出主要在本地，面向数据运算和本地事务进行处理，即使是分布式运算，也是中心计算机在本地统一进行任务分配后，在调度算法的控制下完成的。而在互联网时代，操作系统、数据、应用程序、计算和输入/输出通过网络，依托于异构的自治节点间的互操作形成动态的计算环境。 计算机之间的相互作用大体可归纳为消息传递、数据交换和程序调用等几种类型。计算机病毒能够通过修改其他程序并把自身拷贝在其中而感染这些程序，从而在节点间传播。网络蜘蛛在万维网中各站点爬行，捕获网页内容，对词语进行索引编排，并发回主站点。网络机器人则使用某台计算机来控制另一台（批）计算机的资源（带宽、存储空间和计算能力），而且机器人可以“