Computation and Hypercomputation

Minds and Machines - Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present...     

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.     

Physical Computation: How General are Gandy’s Principles for Mechanisms?

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable.     

Reflections on Gödel's and Gandy's Reflections on Turing's Thesis

We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.     

Thinking Machines: Some Fundamental Confusions

This paper explores Church's Thesis and related claims madeby Turing. Church's Thesis concerns computable numerical functions, whileTuring's claims concern both procedures for manipulating uninterpreted marksand machines that generate the results that these procedures would yield. Itis argued that Turing's claims are true, and that they support (the truth of)Church's Thesis. It is further argued that the truth of Turing's and Church'sTheses has no interesting consequences for human cognition or cognitiveabilities. The Theses don't even mean that computers can do as much as peoplecan when it comes to carrying out effective procedures. For carrying out aprocedure is a purposive, intentional activity. No actual machine does, orcan do, as much.     

Zeno machines and hypercomputation

This paper reviews the Church–Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of “hypercomputation”, concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines with accelerating clock). The halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. It is suggested that claims to have “broken the Turing barrier” could be toned down and that the important and well-founded rôle of Turing computability in the mathematical sciences stands unchallenged.     

The Scope of Turing's Analysis of Effective Procedures

Turing's (1936) analysis of effective symbolic procedures is a model of conceptual clarity that plays an essential role in the philosophy of mathematics. Yet appeal is often made to the effectiveness of human procedures in other areas of philosophy. This paper addresses the question of whether Turing's analysis can be applied to a broader class of effective human procedures. We use Sieg's (1994) presentation of Turing's Thesis to argue against Cleland's (1995) objections to Turing machines and we evaluate her proposal to understand the effectiveness of procedures in terms of their reliability and precision. A number of conditions for effectiveness are identified and these are used to provide a general argument against the possibility of a Leibnizian decision procedure.     

Accelerating Turing Machines

Minds and Machines - Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine...     

On mind &; Turing’s machines

Turing’s notion of human computability is exactly right not only for obtaining a negative solution of Hilbert’s Entscheidungsproblem that is conclusive, but also for achieving a precise characterization of formal systems that is needed for the general formulation of the incompleteness theorems. The broad intellectual context reaches back to Leibniz and requires a focus on mechanical procedures; these procedures are to be carried out by human computers without invoking higher cognitive capacities. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I address this question not in any general way, but rather by focusing on aspects of mathematical reasoning that transcend mechanical procedures.Section 1 discusses Gödel’s perspective on mechanical computability as articulated in his [193?], where he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathematicians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951; Gödel argues there in greater detail that the human mind infinitely surpasses the powers of any finite machine. An analysis of the argument is presented in Section 2 under the heading Beyond calculation. Section 3 is entitled Beyond discipline and gives Turing’s view of intelligent machinery; it is devoted to the seemingly sharp conflict between Gödel’s and Turing’s views on mind. Their deeper disagreement really concerns the nature of machines, and I’ll end with some brief remarks on (supra-) mechanical devices in Section 4.     

Computation and Dynamical Models of Mind

Van Gelder (1995) has recently spearheaded a movement to challenge the dominance of connectionist and classicist models in cognitive science. The dynamical conception of cognition is van Gelder's replacement for the computation bound paradigms provided by connectionism and classicism. He relies on the Watt governor to fulfill the role of a dynamicist Turing machine and claims that the Motivational Oscillatory Theory (MOT) provides a sound empirical basis for dynamicism. In other words, the Watt governor is to be the theoretical exemplar of the class of systems necessary for cognition and MOT is an empirical instantiation of that class. However, I shall argue that neither the Watt governor nor MOT successfully fulfill these prescribed roles. This failure, along with van Gelder's peculiar use of the concept of computation and his struggle with representationalism, prevent him from providing a convincing alternative to current cognitive theories.     

Effective Fitness as an Alternative Paradigm for Evolutionary Computation I: General Formalism

In evolutionary computation the concept of a fitness landscape has played an important role, evolution itself being portrayed as a hill-climbing process on a rugged landscape. In this article we review the recent development of an alternative paradigm for evolution on a fitness landscape—effective fitness. It is shown that in general, in the presence of other genetic operators such as mutation and recombination, hill-climbing is the exception rather than the rule; a discrepancy that has its origin in the different ways in which the concept of fitness appears—as a measure of the number of fit offspring, or as a measure of the probability to reach reproductive age. Effective fitness models the former not the latter and gives an intuitive way to understand population dynamics as flows on an effective fitness landscape when genetic operators other than reproductive selection play an important role. Additionally, we will show that when the genotype-phenotype map is degenerate, i.e. there exists a synonym symmetry, it can be used to quantify the degree of symmetry breaking of the map, thus allowing for a quantitative explanation of phenomena such as self-adaptation, bloat and evolutionary robustness.     

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.     

Alan Turing and the Mathematical Objection

This paper concerns Alan Turing's ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the ``mathematical objection' to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human mathematicians presumably do.     

Minds, Machines and Turing

Turing's celebrated 1950 paper proposes a very generalmethodological criterion for modelling mental function: total functionalequivalence and indistinguishability. His criterion gives rise to ahierarchy of Turing Tests, from subtotal (toy) fragments of ourfunctions (t1), to total symbolic (pen-pal) function (T2 – the standardTuring Test), to total external sensorimotor (robotic) function (T3), tototal internal microfunction (T4), to total indistinguishability inevery empirically discernible respect (T5). This is areverse-engineering hierarchy of (decreasing) empiricalunderdetermination of the theory by the data. Level t1 is clearly toounderdetermined, T2 is vulnerable to a counterexample (Searle's ChineseRoom Argument), and T4 and T5 are arbitrarily overdetermined. Hence T3is the appropriate target level for cognitive science. When it isreached, however, there will still remain more unanswerable questionsthan when Physics reaches its Grand Unified Theory of Everything (GUTE),because of the mind/body problem and the other-minds problem, both ofwhich are inherent in this empirical domain, even though Turing hardlymentions them.     

A Wheelchair Steered through Voice Commands and Assisted by a Reactive Fuzzy-Logic Controller

This paper describes new results with a Reactive Shared-Control system that enables a semi-autonomous navigation of a wheelchair in unknown and dynamic environments. The purpose of the reactive shared controller is to assist wheelchair users providing an easier and safer navigation. It is designed as a fuzzy-logic controller and follows a behaviour-based architecture. The implemented behaviours are three: intelligent obstacle avoidance, collision detection and contour following. Intelligent obstacle avoidance blends user commands, from voice or joystick, with an obstacle avoidance behaviour. Therefore, the user and the vehicle share the control of the wheelchair. The reactive shared control was tested on the RobChair powered wheelchair prototype [6] equipped with a set of ranging sensors. Experimental results are presented demonstrating the effectiveness of the controller.     

Mobile Robot Command by Man–Machine Co-Operation – Application to Disabled and Elderly People Assistance

Disabled people assistance is developing thanks to progress of new technologies. A manipulator arm mounted on a mobile robot can assist a disabled person for a partial restoration of the manipulative function. A user pilots the robot via a control station, using enhanced reality techniques. To be affordable such a system must be cost-effective. That constraint limits perception means: ultrasonic ring, dead reckoning, and low-cost camera. The development of the project has followed two stages. The first one consists of giving maximum autonomy capacities to the robot for planning, navigation, and localisation. The second stage is the study of the Man–Machine Co-operation (MMC) for the command of the robot system. Indeed, the aim is to perform a mission (mobile robot displacement), using the robot capacities and man possibilities. Users build their own strategies to carry out a mission successively. The strategy can be seen as a succession of control modes, which can be manual, automatic, or shared. In the latter case, the control of the robot is shared between a human operator and machine. The main problem is then task allocation between both intelligent entities. Each one has planification, navigation, and localisation abilities. The paper presents our approach for planning and navigation and develops a more specific study about robot localisation.