基于图灵机的递归技术的实现陈晓亮[1] 卢朝辉[2] 宋文[1]

图灵机是通用的计算机模型,一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征,利用多带图灵机作为计算模型,定义了递归技术转移 函数形式,提出了图灵机递归过程信息传递与保存的方法,给出了图灵机调用的实现,继而给出了图灵机递归技术的实现,同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。     

Undecidability in the Imitation Game

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems.     

Parallel Turing Machine,a Proposal

We have witnessed the tremendous momentum of the second spring of parallel computing in recent years. But, we should remember the low points of the field more than 20 years ago and review the lesson that has led to the question at that point whether “parallel computing will soon be relegated to the trash heap reserved for promising technologies that never quite make it” in an article entitled “the death of parallel computing” written by the late Ken Kennedy — a prominent leader of parallel computing in the world. Facing the new era of parallel computing, we should learn from the robust history of sequential computation in the past 60 years. We should study the foundation established by the model of Turing machine (1936) and its profound impact in this history. To this end, this paper examines the disappointing state of the work in parallel Turing machine models in the past 50 years of parallel computing research. Lacking a solid yet intuitive parallel Turing machine model will continue to be a serious challenge in the future parallel computing. Our paper presents an attempt to address this challenge by presenting a proposal of a parallel Turing machine model. We also discuss why we start our work in this paper from a parallel Turing machine model instead of other choices.     

基本图灵机的Petri网建模研究

该文采用Petri网这种系统描述和分析工具对基本图灵机进行了建模与分析。首先介绍了基本图灵机和Petri网的基本概念与定义,然后给出了一个利用Petri网对基本图灵机进行建模的有效算法,研究了用Petri网为基本图灵机建模的一般方法,说明了该方法的优越性,并最终以一个建模实例验证了该方法的有效性和可行性。     

K带实时图灵机计算能力与图灵机带数的关系

本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。     

Some observations concerning alternating turing machines using small space

We make some observations concerning alternating Turing machines operating in small space. For example, we show that alternating Turing machines using o(log n) space are more powerful than nondeterministic Turing machines using the same space-bound. In fact, we show that there is a language over a unary alphabet that can be accepted by an on-line alternating Turing machine in log n space, but not by any off-line nondeterministic Turing machine in o(log n) space. We also investigate the weak vs. strong space bounds and on-line vs. off-line machines at these low tape bounds.     

Do Accelerating Turing Machines Compute the Uncomputable?

Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation” (Potgieter and Rosinger 2010: 853). But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the term “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical.     

Two tapes versus one for off-line Turing machines

We prove the first superlinear lower bound for a concrete, polynomial time recognizable decision problem on a Turing machine with one work tape and a two-way input tape (also called off-line 1-tape Turing machine).In particular, for off-line Turing machines we show that two tapes are better than one and that three pushdown stores are better than two (both in the deterministic and in the nondeterministic case).     

A Universal Accepting Hybrid Network of Evolutionary Processors

We propose a construction of an accepting hybrid network of evolutionary processors (AHNEP) which behaves as a universal device in the class of all these devices. We first construct a Turing machine which can simulate any AHNEP and then an AHNEP which simulates the Turing machine. We think that this approach can be applied to other bio-inspired computing models which are computationally complete.     

On parallel Turing machines with multi-head control units

This paper deals with parallel Turing machines with multi-head control units on one or more tapes which can be considered as a generalization of cellular automata. We discuss the problem of finding an appropriate measure of space complexity. A definition is suggested which implies that the model is in the first machine class. It is shown that without loss of generality it suffices to consider only parallel Turing machines of certain normal forms.     

On the universality of peptide computing

We present a simulation of Turing machines by peptide–antibody interactions. In contrast to an earlier simulation, this new technique simulates the computation steps automatically by the interaction between peptides and antibodies and does not rely on a “look-and-do” approach, in which the Turing machine program would be interpreted by an extraneous computing agent. We determine the resource requirements of the simulation. Towards a precise definition for peptide computing we construct a new theoretical model. We examine how the simulations presented in this paper fits this model. We also give conditions on the peptide computing model so that it can be simulated by a Turing machine.

Turing Interrogative Games

The issue of adequacy of the Turing Test (TT) is addressed. The concept of Turing Interrogative Game (TIG) is introduced. We show that if some conditions hold, then each machine, even a thinking one, loses a certain TIG and thus an instance of TT. If, however, the conditions do not hold, the success of a machine need not constitute a convincing argument for the claim that the machine thinks.     

Approximation and universality of fuzzy Turing machines

Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.     

交互计算模型概述

由于计算机技术的发展日新月异，以算法为核心，以图灵机和Church论题等为理论依据的计算模型已无力继续成为今天计算科学的理论范式，介绍了一个崭新的计算模型－－交互计算模型的基本思想，它是对算法的扩展，并比算法具有更强的描述能力，一系列基本概念被扩展到交互。     

Turing Test Considered Mostly Harmless

Turing’s landmark paper on computing machinery and intelligence is multifaceted and has an underemphasized ethical dimension. Turing’s notion of “intelligence” and “thinking” was far more encompassing than the common anthropocentric view may suggest. We discuss a number of open and underrated problems that the common interpretation of the Turing test as a test of machine intelligence entails. We suggest that a more meaningful question than “Can machines think?” is whether modern computing machinery can amplify human intelligence. We cite examples ranging from traditional silicon-based environments to carbon-based, living organisms in order to illustrate that this kind of intelligence amplification is indeed happening today. We conclude that in its interpretation as a test of machine intelligence, the Turing test may indeed be harmful for artificial intelligence (AI); in its wider interpretation, however, it remains an inspiring source for philosophy and AI alike.     

Structured Turing Machines

The concept of a structured Turing machine is introduced. Every Turing machine is demonstrated to be equivalent to some structured Turing machine. Various refinements of the problem of structurization are considered and, in particular, refinements in which any extension of the working alphabet being used is prohibited.     

Physical Hypercomputation and the Church–Turing Thesis

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.     

An improved simulation of space and reversal bounded deterministic turing machines by width and depth bounded uniform circuits

We present an improved simulation of space and reversal bounded Turing machines by width and depth bounded uniform circuits. (All resource bounds hold simultaneously.) An S(n) space, R(n) reversal bounded deterministic k-tape Turing machine can be simulated by a uniform circuit of O(R(n)log²S(n)) depth and O(S(n)^k) width. Our proof is cleaner, and has slightly better resource bounds than the original proof due to Pippenger (1979). The improvement is resource bounds comes primarily from the use of a shared-memory machine instead of an oblivious Turing machine, and the concept of a ‘special situation’.