One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

The original proof of the four-color theorem by Appel and Haken sparked a controversy when Tymoczko used it to argue that the justification provided by unsurveyable proofs carried out by computers cannot be a priori. It also created a lingering impression to the effect that such proofs depend heavily for their soundness on large amounts of computation-intensive custom-built software. Contra Tymoczko, we argue that the justification provided by certain computerized mathematical proofs is not fundamentally different from that provided by surveyable (...) proofs, and can be sensibly regarded as a priori. We also show that the aforementioned impression is mistaken because it fails to distinguish between proof search (the context of discovery) and proof checking (the context of justification). By using mechanized proof assistants capable of producing certificates that can be independently checked, it is possible to carry out complex proofs without the need to trust arbitrary custom-written code. We only need to trust one fixed, small, and simple piece of software: the proof checker. This is not only possible in principle, but is in fact becoming a viable methodology for performing complicated mathematical reasoning. This is evinced by a new proof of the four-color theorem that appeared in 2005, and which was developed and checked in its entirety by a mechanical proof system. (shrink)

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents the state (...) of the art in the area. (shrink)

This important book, which results from a series of presentations at American Philosophical Association conferences, explores the major ways in which computers ...

Cognitive science has been dominated by the computational conception that cogniton is computation across representations. To the extent to which cognition is supposed to be a purposive, meaningful, algorithmic, problem-solving activity, however, computers appear to be incapable of cognition. They are devices that can facilitate computations on the basis of semantic grounding relations as special kinds of signs. Even their algorithmic, problem-solving character arises from ther interpretation by human users. Strictly speaking, computers as such–apart from human users–are not only incapable (...) of cognition but even incapable of computation, properly construed. If we want to understand the nature of thought, we are going to have to study thinking, not computing, because they are not the same thing. (shrink)

Computational neuroscientists not only employ computer models and simulations in studying brain functions. They also view the modeled nervous system itself as computing. What does it mean to say that the brain computes? And what is the utility of the ‘brain-as-computer’ assumption in studying brain functions? In previous work, I have argued that a structural conception of computation is not adequate to address these questions. Here I outline an alternative conception of computation, which I call the analog-model. The term ‘analog-model’ (...) does not mean continuous, non-discrete or non-digital. It means that the functional performance of the system simulates mathematical relations in some other system, between what is being represented. The brain-as-computer view is invoked to demonstrate that the internal cellular activity is appropriate for the pertinent information-processing task.Keywords: Computation; Computational neuroscience; Analog computers; Representation; Simulation. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Astrology, Computers, and the VolksgeistDenis DuttonCarroll Righter is not a name you will recognize, unless, perhaps, you’re old enough and you grew up reading the Los Angeles Times. Righter was the Times’s astrologer, and encountering his name recently brought back a couple of memories from the early 1950s. I remember finding it strange that a man (he was pictured alongside his column) was called Carroll, though he didn’t spell (...) it like the girl who lived across the street. But especially I recall the fun we had when my father would read the horoscopes out loud and we’d compare them with the day’s events. Ours was a tough family for an astrologer to please, with rather different things happening to too many Aquarians, and a robust skepticism about anything of the sort later to be called “New Age.”How could I know that while we laughed and debated, somewhere else out there in the urban sprawl, Righter’s prognostications were being subjected to subtle and portentous analysis by that kingpin of the Frankfurt School, Theodor W. Adorno? Mirabile dictu, Adorno was living in L.A. at the time, and we now have his examination of Righter in The Stars Down to Earth, and Other Essays on the Irrational in Culture, edited with an excellent introduction by Stephen Crook (Routledge, $16.95). The result seems, now in the fullness of time, of mixed value and relevance. Adorno has produced an admirably accessible rhetoric of astrology, what he terms “content analysis.” In this, he is finding out for himself about the so-called cold-reading techniques of psychic consultation, practices long known to magicians and astrologers and only really understood by psychologists since Bertram Forer’s work in the 1940s. But beyond that, Adorno uses astrology to support and exemplify his theory of authoritarian irrationalism. As you might expect, this is more questionable. [End Page 424]To be sure, there are many intriguing observations throughout this mostly readable essay. In a passage perhaps even more true today than when it was written, Adorno says that a “climate of semi-erudition is the fertile breeding ground for astrology.” He refers to people who have gone just beyond the naive acceptance of the authority of science, but who don’t know enough, or who have not sufficiently developed “the power of thinking,” that they can replace such acceptance with anything better: “The semi-erudite vaguely wants to understand and is also driven by the narcissistic wish to prove superior to the plain people but he is not in a position to carry through complicated and detached intellectual operations.” In other words, quantum mechanics is pretty tough, but astrology offers sophisticated understanding of all reality in a few easy steps. Besides, astronomy is about those remote stars and planets out there—rather cold and impersonal. In Adorno’s apt title phrase, astrology brings it all down to earth, because it’s about the single most important thing in the universe: me. In an analogy that isn’t too far-fetched, he says that to the semi-erudite individual “astrology, just as other irrational creeds like racism, provides a short-cut by bringing the complex to a handy formula and offering at the same time the pleasant gratification that he who feels excluded from educational privileges nevertheless belongs to the minority of those who are ‘in the know.’” Someone once remarked that Scientology boosts self-esteem largely by giving semi-educated, degreeless persons impressive certificates to hang on their walls, and Adorno is right that there’s a similar syndrome at work with most New Age esoterica, including astrology. (In literary theory, there are no certificates, of course—you just have to learn the jargon.)Much to his credit, Adorno independently identifies many of the features of cold reading described by Forer and later writers, such as the persistent tendency of the client to personalize the general message. Of Righter’s “Follow up that intuition of yours,” or “Display that keen mind of yours,” Adorno says, “People who have any affinity at all to occultism are usually prepared to react to the information they are craving in such a way... (shrink)

Why do the big philosophical questions so often strike us as far-fetched and little to with everyday life? Mary Midgley shows that it need not be that way; she shows that there is a need for philosophy in the real world. Her popularity as one of our foremost philosophers is based on a no-nonsense, down-to-earth approach to fundamental human problems, philosphical or otherwise. In _Utopias, Dolphins and Computers_ she makes her case for philosophy as a difficult but necessary tool for (...) solving some of the most pressing issues facing contemporary society. How should we treat animals? Why are we so confused about the value of education? What is at stake in feminism? Why should we sustain our environment? Why do we think intelligent computers will save us? Mary Midgley argues that philosophy not only can, but should be used in thinking about these questions. _Utopias, Dolphins and Computers_ will make fascinating reading for philosophers, educationalists, feminists, environmentalists and indeed anyone interested in the questions of philosophy, ethics and life. (shrink)

_Minds, Brains, Computers_ serves as both an historical and interdisciplinary introduction to the foundations of cognitive science.

In this reply to James H. Fetzer’s “Minds and Machines: Limits to Simulations of Thought and Action”, I argue that computationalism should not be the view that (human) cognition is computation, but that it should be the view that cognition (simpliciter) is computable. It follows that computationalism can be true even if (human) cognition is not the result of computations in the brain. I also argue that, if semiotic systems are systems that interpret signs, then both humans and computers are (...) semiotic systems. Finally, I suggest that minds can be considered as virtual machines implemented in certain semiotic systems, primarily the brain, but also AI computers. In doing so, I take issue with Fetzer’s arguments to the contrary. (shrink)

From the initial analysis of John Morris in 1976 about if computers can lie, I have presented my own treatment of the problem using what can be called a computational lying procedure. One that uses two Turing Machines. From there, I have argued that such a procedure cannot be implemented in a Turing Machine alone. A fundamental difficulty arises, concerning the computational representation of the self-knowledge a machine should have about the fact that it is lying. Contrary to Morris’ claim, (...) I have thus suggested that computers – as far as they are Turing Machines – cannot lie. Consequently, I have claimed that moral agency attribution to a robot or any other automated AI system, cannot be made, strictly grounded on imitating behaviors. Self-awareness as an ontological grounding for moral attribution must be evoked. This can pose a recognition problem from our part, should the sentient system be the only agent capable of acknowledging its own sentience. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Astrology, Computers, and the VolksgeistDenis DuttonCarroll Righter is not a name you will recognize, unless, perhaps, you’re old enough and you grew up reading the Los Angeles Times. Righter was the Times’s astrologer, and encountering his name recently brought back a couple of memories from the early 1950s. I remember finding it strange that a man (he was pictured alongside his column) was called Carroll, though he didn’t spell (...) it like the girl who lived across the street. But especially I recall the fun we had when my father would read the horoscopes out loud and we’d compare them with the day’s events. Ours was a tough family for an astrologer to please, with rather different things happening to too many Aquarians, and a robust skepticism about anything of the sort later to be called “New Age.”How could I know that while we laughed and debated, somewhere else out there in the urban sprawl, Righter’s prognostications were being subjected to subtle and portentous analysis by that kingpin of the Frankfurt School, Theodor W. Adorno? Mirabile dictu, Adorno was living in L.A. at the time, and we now have his examination of Righter in The Stars Down to Earth, and Other Essays on the Irrational in Culture, edited with an excellent introduction by Stephen Crook (Routledge, $16.95). The result seems, now in the fullness of time, of mixed value and relevance. Adorno has produced an admirably accessible rhetoric of astrology, what he terms “content analysis.” In this, he is finding out for himself about the so-called cold-reading techniques of psychic consultation, practices long known to magicians and astrologers and only really understood by psychologists since Bertram Forer’s work in the 1940s. But beyond that, Adorno uses astrology to support and exemplify his theory of authoritarian irrationalism. As you might expect, this is more questionable. [End Page 424]To be sure, there are many intriguing observations throughout this mostly readable essay. In a passage perhaps even more true today than when it was written, Adorno says that a “climate of semi-erudition is the fertile breeding ground for astrology.” He refers to people who have gone just beyond the naive acceptance of the authority of science, but who don’t know enough, or who have not sufficiently developed “the power of thinking,” that they can replace such acceptance with anything better: “The semi-erudite vaguely wants to understand and is also driven by the narcissistic wish to prove superior to the plain people but he is not in a position to carry through complicated and detached intellectual operations.” In other words, quantum mechanics is pretty tough, but astrology offers sophisticated understanding of all reality in a few easy steps. Besides, astronomy is about those remote stars and planets out there—rather cold and impersonal. In Adorno’s apt title phrase, astrology brings it all down to earth, because it’s about the single most important thing in the universe: me. In an analogy that isn’t too far-fetched, he says that to the semi-erudite individual “astrology, just as other irrational creeds like racism, provides a short-cut by bringing the complex to a handy formula and offering at the same time the pleasant gratification that he who feels excluded from educational privileges nevertheless belongs to the minority of those who are ‘in the know.’” Someone once remarked that Scientology boosts self-esteem largely by giving semi-educated, degreeless persons impressive certificates to hang on their walls, and Adorno is right that there’s a similar syndrome at work with most New Age esoterica, including astrology. (In literary theory, there are no certificates, of course—you just have to learn the jargon.)Much to his credit, Adorno independently identifies many of the features of cold reading described by Forer and later writers, such as the persistent tendency of the client to personalize the general message. Of Righter’s “Follow up that intuition of yours,” or “Display that keen mind of yours,” Adorno says, “People who have any affinity at all to occultism are usually prepared to react to the information they are craving in such a way... (shrink)

This paper is a review of 39 years of SIGCAS publications in Computers and Society, the newsletter of ACM SIGCAS. The publication is archived in the ACM Digital Library [12]. I set out to examine SIGCAS through its publications.

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously enough-and this is (...) the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

This important book, which results from a series of presentations at American Philosophical Association conferences, explores the major ways in which computers ...

A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar ("close") to (...) our world. But curiously enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation (e.g. intuitive, finitely programmed, limited in computational capability), a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

The most cursory examination of the history of artificial intelligence highlights numerous egregious claims of its researchers, especially in relation to a populist form of ‘strong’ computationalism which holds that any suitably programmed computer instantiates genuine conscious mental states purely in virtue of carrying out a specific series of computations. The argument presented herein is a simple development of that originally presented in Putnam’s (Representation & Reality, Bradford Books, Cambridge in 1988 ) monograph, “Representation & Reality”, which if correct, has (...) important implications for turing machine functionalism and the prospect of ‘conscious’ machines. In the paper, instead of seeking to develop Putnam’s claim that, “everything implements every finite state automata”, I will try to establish the weaker result that, “everything implements the specific machine Q on a particular input set ( x )”. Then, equating Q ( x ) to any putative AI program, I will show that conceding the ‘strong AI’ thesis for Q (crediting it with mental states and consciousness) opens the door to a vicious form of panpsychism whereby all open systems, (e.g. grass, rocks etc.), must instantiate conscious experience and hence that disembodied minds lurk everywhere. (shrink)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

In Utopias, Dolphins and Computers Mary Midgley brings philosophy into the real world by using it to consider environmental, educational and gender issues. From "Freedom, Feminism and War" to "Artificial Intelligence and Creativity," this book searches for what is distorting our judgement and helps us to see more clearly the dramas which are unfolding in the world around us. Utopias, Dolphins and Computers aims to counter today's anti-intellectualism, not to mention philosophy's twentieth-century view of itself as futile. Mary Midgley explains (...) the point of philosophy: how to do it, why it is needed, what difficulties confront it and what topics need its attention. (shrink)

The physical limitations, due to quantum mechanics, on the functioning of computers are analyzed.

Recently, Horsman et al. have proposed a new framework, Abstraction/Representation theory, for understanding and evaluating claims about unconventional or non-standard computation. Among its attractive features, the theory in particular implies a novel account of what is means to be a computer. After expounding on this account, I compare it with other accounts of concrete computation, finding that it does not quite fit in the standard categorization: while it is most similar to some semantic accounts, it is not itself a semantic (...) account. Then I evaluate it according to the six desiderata for accounts of concrete computation proposed by Piccinini. Finding that it does not clearly satisfy some of them, I propose a modification, which I call Agential AR theory, that does, yielding an account that could be a serious competitor to other leading account of concrete computation. (shrink)

Digital computers carry out algorithms coded in high level programs. These abstract entities determine what happens at the physical level: they control whether electrons flow through specific transistors at specific times or not, entailing downward causation in both the logical and implementation hierarchies. This paper explores how this is possible in the light of the alleged causal completeness of physics at the bottom level, and highlights the mechanism that enables strong emergence (the manifest causal effectiveness of application programs) to occur. (...) Although synchronic emergence of higher levels from lower levels is manifestly true, diachronic emergence is generically not the case; indeed we give specific examples where it cannot occur because of the causal effectiveness of higher level variables. (shrink)

I survey in this article the practical uses of computers in philosophy: except for logic, computers have not yet noticeably improved the quality of philosophizing, research, or pedagogy. They have made work easier. My main interest, however, is in the “substantive” impact that computers may have on philosophical problems, especially in metaphysics. I argue that logic, the notion of decidability, and the theory of computation all predated and did not require modern digital computers. In the philosophy of mind, there has (...) been a persistent conflation of computationalism and physicalism. The two theses can and should be separated. Finally, I suggest that we see glimpses of a new metaphysics based on information and information transformations that goes far beyond the well‐trodden mind‐brain debates. (shrink)

The most cursory examination of the history of artificial intelligence highlights numerous egregious claims of its researchers, especially in relation to a populist form of ‘strong’ computationalism which holds that any suitably programmed computer instantiates genuine conscious mental states purely in virtue of carrying out a specific series of computations. The argument presented herein is a simple development of that originally presented in Putnam’s monograph, “Representation & Reality”, which if correct, has important implications for turing machine functionalism and the prospect (...) of ‘conscious’ machines. In the paper, instead of seeking to develop Putnam’s claim that, “everything implements every finite state automata”, I will try to establish the weaker result that, “everything implements the specific machine Q on a particular input set ”. Then, equating Q to any putative AI program, I will show that conceding the ‘strong AI’ thesis for Q opens the door to a vicious form of panpsychism whereby all open systems,, must instantiate conscious experience and hence that disembodied minds lurk everywhere. (shrink)