Narrow Results

We argue that dynamical systems involving discrete and continuous data can be modelled by Turing machines with oracles that are physical processes. Using the theory introduced in Beggs et al. [2,3], we consider the scope and limits of polynomial time computations by such systems. We propose a general polynomial time Church-Turing Thesis for feasible computations by analogue-digital systems, having the non-uniform complexity class BPP//log* as theoretical upper bound. We show why BPP//log* should be replace P/poly, which was proposed by Siegelmann for neural nets [23,24]. Then we examine whether other sources of hypercomputation can be found in analogue-digital systems besides the oracle itself. We prove that the higher polytime limit P/poly can be attained via non-computable analogue-digital interface protocols.

We consider the experimenter (e.g. the experimental physicist) as a Turing machine — the digital component — and the experiment of measurement — the analog component — as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. In this paper we prove that the central analogue-digital complexity classes $P$, $P/poly$ and $P/poly\cap REC$ can be characterized in terms of protocols to perform measurements controlled by standard Turing machines.

Hypercomputation is about the feasibility of machines and systems that are either more expressive or computationally more powerful than the Turing machine. A number of researchers and thinkers have put forth a number of supposedly knock-out arguments against hypercomputation. Nevertheless, these arguments are not unwavering as they seem to be and here I explain why.

The universal Turing Machine (TM) is a model for Von Neumann computers — general-purpose computers. A human brain, linked with its biological body, can inside-skull-autonomously learn a universal TM so that he acts as a general-purpose computer and writes a computer program for any practical purposes. It is unknown whether a robot can accomplish the same. This theoretical work shows how the Developmental Network (DN), linked with its robot body, can accomplish this. Unlike a traditional TM, the TM learned by DN is a super TM — Grounded, Emergent, Natural, Incremental, Skulled, Attentive, Motivated, and Abstractive (GENISAMA). A DN is free of any central controller (e.g., Master Map, convolution, or error back-propagation). Its learning from a teacher TM is one transition observation at a time, immediate, and error-free until all its neurons have been initialized by early observed teacher transitions. From that point on, the DN is no longer error-free but is always optimal at every time instance in the sense of maximal likelihood, conditioned on its limited computational resources and the learning experience. This paper extends the Church–Turing thesis to a stronger version — a GENISAMA TM is capable of Autonomous Programming for General Purposes (APFGP) — and proves both the Church–Turing thesis and its stronger version.

Even though simulation models are the dominant paradigm in cognitive science, it has been argued that Galilean models might fare better on both the description and explanation of real cognitive phenomena. The main goal of this paper is to show that the actual construction of Galilean models is clearly feasible, and well suited, for a special class of cognitive phenomena, namely, those of human computation. I will argue in particular that Turing's original formulation of the Church-Turing thesis can naturally be viewed as the core hypothesis of a new empirical theory of human computation. This theory relies on bidimensional Turing machines, a generalization of ordinary machines with one-dimensional tape to two-dimensional paper. Finally, I will suggest that this theory might become a first paradigm for a general approach to the study of cognition, an approach entirely based on Galilean models of cognitive phenomena.