Computational Complexity and Philosophical Dualism :: Dualism Essays

Computational Complexity and Philosophical Dualism ABSTRACT: I examine some recent controversies involving the possibility of mechanical simulation of mathematical intuition. The first part is concerned with a presentation of the Lucas-Penrose position and recapitulates some basic logical conceptual machinery (GÃ ¶del's proof, Hilbert's Tenth Problem and Turing's Halting Problem). The second part is devoted to a presentation of the main outlines of Complexity Theory as well as to the introduction of Bremermann's notion of transcomputability and fundamental limit. The third part attempts to draw a connection/relationship between Complexity Theory and undecidability focusing on a new revised version of the Lucas-Penrose position in light of physical a priori limitations of computing machines. Finally, the last part derives some epistemological/philosophical implications of the relationship between GÃ ¶del's incompleteness theorem and Complexity Theory for the mind/brain problem in Artificial Intelligence and discusses the compatibili ty of functionalism with a materialist theory of the mind. This paper purports to re-examine the Lucas-Penrose argument against Artificial Intelligence in the light of Complexity Theory. Arguments against strong AI based on some philosophical consequences derived from an interpretation of GÃ ¶del's proof have been around for many years since their initial formulation by Lucas (1961) and their recent revival by Penrose (1989,1994). For one thing, Penrose is right in sustaining that mental activity cannot be modeled as a Turing Machine. However, such a view does not have to follow from the uncomputable nature of some human cognitive capabilities such as mathematical intuition. In what follows I intend to show that even if mathematical intuition were mechanizable (as part of a conception of mental activity understood as the realization of an algorithm) the Turing Machine model of the human mind becomes self-refuting. Our contention will start from the notion of transcomputability. Such a notion will allow us to draw a pathway between formal and physical limitations of symbol-based artificial intelligence by bridging up computational complexity and undecidability. Furthermore, linking complexity and undecidability will reveal that functionalism is incompatible with a materialist theory of the mind and that adherents of functionalism have systematically overlooked implementational issues. 1 - The Lucas-Penrose argument — Lucas-Penrose argument runs as follows: GÃ ¶del's incompleteness theorem shows that computational systems are limited in a way that humans are not. In any consistent formal system powerful enough to do a certain sort of arithmetic there will be a true sentence — a GÃ ¶del sentence (G) — that the system cannot prove.