Output concepts for accelerated Turing machines

The accelerated Turing machine (ATM) is the work-horse of hypercomputation. In certain cases, a machine having run through a countably infinite number of steps is supposed to have decided some interesting question such as the Twin Prime conjecture. One is, however, careful to avoid unnecessary discussion of either the possible actual use by such a machine of an infinite amount of space, or the difficulty (even if only a finite amount of space is used) of defining an outcome for machines acting like Thomson’s lamp. It is the authors’ impression that insufficient attention has been paid to introducing a clearly defined counterpart for ATMs of the halting/non-halting dichotomy for classical Turing computation. This paper tackles the problem of defining the output, or final message, of a machine which has run for a countably infinite number of steps. Non-standard integers appear quite useful in this regard and we describe several models of computation using filters.     

On Effective Procedures

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines.     

The computational status of physics

According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical systems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models’ physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first principles, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as ‘computing something’ in the standard computational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.     

Philosophy of Mind Is (in Part) Philosophy of Computer Science

In this paper I argue that whether or not a computer can be built that passes the Turing test is a central question in the philosophy of mind. Then I show that the possibility of building such a computer depends on open questions in the philosophy of computer science: the physical Church-Turing thesis and the extended Church-Turing thesis. I use the link between the issues identified in philosophy of mind and philosophy of computer science to respond to a prominent argument against the possibility of building a machine that passes the Turing test. Finally, I respond to objections against the proposed link between questions in the philosophy of mind and philosophy of computer science.     

Quantum Hypercomputation

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.     

The computational power of interactive recurrent neural networks

In classical computation, rational- and real-weighted recurrent neural networks were shown to be respectively equivalent to and strictly more powerful than the standard Turing machine model. Here, we study the computational power of recurrent neural networks in a more biologically oriented computational framework, capturing the aspects of sequential interactivity and persistence of memory. In this context, we prove that so-called interactive rational- and real-weighted neural networks show the same computational powers as interactive Turing machines and interactive Turing machines with advice, respectively. A mathematical characterization of each of these computational powers is also provided. It follows from these results that interactive real-weighted neural networks can perform uncountably many more translations of information than interactive Turing machines, making them capable of super-Turing capabilities.     

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.     

Consequences of nonclassical measurement for the algorithmic description of continuous dynamical systems

Abstract

Continuous dynamical systems intuitively seem capable of more complex behavior than discrete systems. If analyzed in the framework of the traditional theory of computation, a.continuous dynamical system with countably many quasistable states has at least the computational power of a universal Turing machine. Such an analysis assumes, however, the classical notion of measurement. If measurement is viewed nonclassically, a continuous dynamical system cannot, even in principle, exhibit behavior that cannot be simulated by a universal Turing machine.     

Packing问题的计算复杂性

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。     

Effective Computation by Humans and Machines

There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation.     

基于受限生成过程模型的计算涌现分析

涌现描述了特定系统在超过某阂值时突然出现的现象,中间没有明显的过渡过程。提出了图灵机计算模型在时空复杂度上所表现出的计算涌现现象,引入了受限生成过程(Constrained Venerating Procedure, CGP)模型来描述图灵机的计算过程,通过CGP模型刻画了机制参与次数、参与深度和平均参与度等3个涌现数字特征,提出了计算涌现的CGP分析方法并在3类典型图灵机计算过程中进行了验证分析。     

Physical constraints on hypercomputation

Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability.     

Effective procedures and computable functions

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers.     

X-machines and the halting problem: Building a super-turing machine

We describe a novel machine model of computation, and prove that this model is capable of performing calculations beyond the capability of the standard Turing machine model. In particular, we demonstrate the ability of our model to solve the Halting problem for Turing machines. We discuss the issues involved in implementing the model as a physical device, and offer some tentative suggestions.     

Theory of one-tape linear-time Turing machines

A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.     

What if computers could think?

The question whether or not computers can think was first asked in print by Alan Turing in his seminal 1950 article. In order to avoid defining what a computer is or what thinking is, Turing resorts to the imitation game which is a test that allows us to determine whether or not a machine can think. That is, if an interrogator is unable to tell whether responses to his questions come from a human being or from a machine, the machine is imitating a human being so well that it has to be acknowledged that these responses result from its thinking. However, then as now, it is not an indisputable claim that machines could think, and an unceasing stream of papers discussing the validity of the test proves this point. There are many arguments in favour of, as well as against, the claims borne by the test, and Turing himself discusses some of them. In his view, there are mice possible objections to the concept of a thinking machine, which he eventually dismisses as weak, irrelevant, or plain false. However, as he admits, he can present no very convincing arguments of a positive nature to support my views. If I had I should not have taken such pains to point out the fallacies in contrary views.     

Classical AI linguistic understanding and the insoluble Cartesian problem

This paper examines an insoluble Cartesian problem for classical AI, namely, how linguistic understanding involves knowledge and awareness of u’s meaning, a cognitive process that is irreducible to algorithms. As analyzed, Descartes’ view about reason and intelligence has paradoxically encouraged certain classical AI researchers to suppose that linguistic understanding suffices for machine intelligence. Several advocates of the Turing Test, for example, assume that linguistic understanding only comprises computational processes which can be recursively decomposed into algorithmic mechanisms. Against this background, in the first section, I explain Descartes’ view about language and mind. To show that Turing bites the bullet with his imitation game and in the second section I analyze this method to assess intelligence. Then, in the third section, I elaborate on Schank and Abelsons’ Script Applier Mechanism (SAM, hereby), which supposedly casts doubt on Descartes’ denial that machines can think. Finally, in the fourth section, I explore a challenge that any algorithmic decomposition of linguistic understanding faces. This challenge, I argue, is the core of the Cartesian problem: knowledge and awareness of meaning require a first-person viewpoint which is irreducible to the decomposition of algorithmic mechanisms.

     

The Swapping Constraint

Triviality arguments against the computational theory of mind claim that computational implementation is trivial and thus does not serve as an adequate metaphysical basis for mental states. It is common to take computational implementation to consist in a mapping from physical states to abstract computational states. In this paper, I propose a novel constraint on the kinds of physical states that can implement computational states, which helps to specify what it is for two physical states to non-trivially implement the same computational state.     

Some properties of four-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: a storage tape and an input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 7 years or so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM), and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers.     

基于量子逻辑的图灵机及其通用性

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.