关于交互和图灵可计算性的一些注记

摘要：

@@ 图灵机作为通用的算法模型在计算机科学中占据统治地位长达半个世纪, 它反映的是"封闭世界"假设, 认为计算实体的行为完全由自身的因素决定, 和所处的环境、外部时间没有关系. 随着基于网络的计算技术[1,2]的兴起, 计算实体之间通过网络互联并且互相影响, 它们的行为既相对独立, 又彼此依赖, 于是计算已经突破了图灵机模式[3], 而交互被认为是这个突破的决定性因素[4,5]. 但是, 目前网络计算还缺乏好的基础模型, 特别是交互的研究还远不够成熟. 为此, 我们的工作是探索交互和算法的关系. 交互的本质在于个体的行为和环境相关, 使得多个个体可以合作, 从而增强各自的能力. 因此, 一个自然的问题是: 是否存在一类比图灵机弱的机器, 它们之间通过交互可以实现图灵机的功能? 该问题的解决对算法的并行化、分布式系统的构建、以及交互能力的评价都有重要意义, 但是相关研究却很少. 本文提出了一种新的交互模型--交互积, 基于此给出一些针对上述问题的肯定性结果, 并且讨论了这些结果在编程模式以及网格计算中的意义.

机标关键词：交互模型、图灵机、计算机科学、行为、网络计算、算法模型、能力的评价、决定性因素、分布式系统、相关研究、网络互联、网格计算、统治地位、编程模式、计算技术、基础模型、环境相关、互相影响、个体、法的关系

所属期刊栏目：49

分类号：TP3;TP1

资助基金：国家自然科学基金69925205;国家高技术研究发展计划863计划2002AA104310;中国科学院引进国外杰出人才基金20014010

在线出版日期：2005-01-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：2375-2376