The complexity of theorem-proving procedures

By Stephen A. Cook

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be "reduced" to the problem of determining whether a given propositional formula is a tautology. Here "reduced" means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.

In Proceedings of the 3rd ACM Symposium on Theory of Computing, pages 151--158, 1971
Author's link (a compressed pdf file of a scanned version)
Other link

Posted by Tony Marmo at 18:37 BST

Share This Post

Post Comment | Permalink

The Concept of Mathematical Elucidation:
theory and problems

By José Seoane

There is a contrast between concepts which may be treated in accordance with the criteria of mathematical rigor and concepts which are not susceptible of such a treatment. We will call theoretical concepts to the former and pre-theoretical to the latter. In mathematical world, sentences which relate theoretical and pre-theoretical concepts (in a determinated way) are denominated thesis; sentences which relate only theoretical concepts (in a determinated way) are denominated theorems. Elucidatory processes in mathematics have thesis as their principal output. I intend to establish in this paper that the introduction of the concept of mathematical elucidation has an important theoretical value to the effects of studying a certain special type of intended conceptual relation and a certain type of justificatory argumentation for it. The analysis of the contrast between thesis and theorems will allow us to construct a context where the interest for those conceptual relations and their supporting justificatory mechanisms arises naturally. Then, I will attempt to offer some structural features of mathematical elucidation qua conceptual relation and their impact on the strategies of elucidatory justification. This is what I grandiloquently call theory in the heading. I will suggest also a classification of the problems which a theoretical reflexion as the one proposed may contribute to clarify and I will make some brief observations on some paradigmatic examples of each one of the categories of the classification constructed. This work should be considered as a modest definition of a sort of research program.

Source: CLE e-prints

Posted by Tony Marmo at 18:27 BST

Share This Post

Post Comment | Permalink

Semantic computations of truth, based on associations already learned 

By Patrick Suppes & Jean-Yves Beziau

In this article we try to give an account of how one determines the truth or falsity of sentences like: Paris is the capital of France, Paris is not the capital of France, Rome is the capital of France. We want to describe the computations underlying the answers given, taking into account, at least in a qualitative way, the time factor what psychologists call the latency of a response. Our theory should be able to explain the data gathered by experimentation, for example, why it takes more time to give a negative answer than a positive one, be it true or false. But the important theoretical question is what is the actual method of computation, a problem not ordinarily considered in philosophical theories of truth, but also not subject to direct empirical observation.

Posted by Tony Marmo at 04:01 BST

Updated: Thursday, 24 August 2006 04:06 BST

Share This Post

Post Comment | Permalink

Intensional Models for the Theory of Types

By Reinhard Muskens

In this paper we define intensional models for the classical theory of types, thus arriving at an intensional type logic ITL. Intensional models generalize Henkin's general models and have a natural definition. As a class they do not validate the axiom of Extensionality. We give a cut-free sequent calculus for type theory and show completeness of this calculus with respect to the class of intensional models via a model existence theorem. After this we turn our attention to applications. Firstly, it is argued that, since ITL is truly intensional, it can be used to model ascriptions of propositional attitude without predicting logical omniscience. In order to illustrate this a small fragment of English is defined and provided with an ITL semantics. Secondly, it is shown that ITL models contain certain objects that can be identified with possible worlds. Essential elements of modal logic become available within classical type theory once the axiom of Extensionality is given up.

Source: Semantics Archive, To appear in the The Journal of Symbolic Logic

Posted by Tony Marmo at 18:08 BST

Updated: Thursday, 24 August 2006 04:07 BST

Share This Post

Post Comment | Permalink

Information and knowledge: an evolutionary framework for information Science

By Marcia J Bates

Background. Many definitions of information, knowledge, and data have been suggested throughout the history of information science. In this article, the objective is to provide definitions that are usable for the physical, biological, and social meanings of the terms, covering the various senses important to our field.

Argument. Information 1 is defined as the pattern of organization of matter and energy. Information 2 is defined as some pattern of organization of matter and energy that has been given meaning by a living being. Knowledge is defined as information given meaning and integrated with other contents of understanding.

Elaboration. The approach is rooted in an evolutionary framework; that is, modes of information perception, processing, transmission, and storage are seen to have developed as a part of the general evolution of members of the animal kingdom. Brains are expensive for animals to support; consequently, efficient storage, including, particularly, storage at emergent levels-for example, storing the concept of chair, rather than specific memories of all chairs ever seen, is powerful and effective for animals. Conclusion. Thus, rather than being reductionist, the approach taken demonstrates the fundamentally emergent nature of most of what higher animals and human beings, in particular, experience as information.

Keywords: IMMUNE INFORMATION; SELF-ORGANIZATION; PSYCHOLOGY; RETRIEVAL; SEEKING; CYBERSEMIOTICS; COMMUNICATION; LIBRARIANSHIP; TESTOSTERONE; METATHEORY

Appeared at INFORMATION RESEARCH-AN INTERNATIONAL ELECTRONIC JOURNAL 10 (4): Art. No. 239 JUL 2005
Source: Philoinfo group

Posted by Tony Marmo at 17:53 GMT

Updated: Friday, 31 March 2006 17:59 GMT

Share This Post

Post Comment | Permalink

A Paradox:
WE ARE ALL PHILOSOPHICALLY SIGNIFICANT

Posted by Tony Marmo at 16:12 GMT

Updated: Friday, 24 March 2006 16:15 GMT

Share This Post

Post Comment | Permalink

The Truth According to James

By Andre Fuhrmann

In this paper I shall be mainly concerned with James’s thesis that pragmatist truth is absolute. James tried to safeguard this aspect of pragmatist truth by means of a particular version of the convergence thesis. But before turning to this aspect of his theory, I shall begin by briefly reviewing James’s view of how the three theses are to be integrated into a pragmatist theory of truth. I shall then discuss in some detail James’s theory of absolute truth as it emerges in a discussion of a supposed problem case for any evidence-constraint theory of truth such as James’s. This is the case of past events that have left no evidential traces. James’s theory of absolute truth, so I shall argue, is a close cousin to Crispin Wright’s theory of superassertibility.

Appeared in Pragmatism Today, ed. A. Fuhrmann and E. Olsson

Posted by Tony Marmo at 20:25 GMT

Share This Post

Post Comment | Permalink

On Linking Dispositions with Conditionals

By Ryan Wasserman and David Manley

We introduce a dilemma that faces any analysis of dispositional ascriptions in terms of subjunctive conditionals. However carefully the relevant conditionals are formulated, the analysis will founder either on the problem of accidental closeness or on the problem of Achilles’ heels. The dilemma arises even for sophisticated versions of the conditional analysis that are designed to avoid the familiar problems of finks and masks. We conclude by evaluating the prospects for an analysis and offering a proposal of our own.

Source: Online Papers in Philosophy

Posted by Tony Marmo at 00:01 GMT

Share This Post

Post Comment | Permalink

MERRY CHRISTMAS SEASON AND HAPPY NEW YEAR
FOR EVERYONE

Going Back to our Roots: Second Generation Biocomputing

By Jon Timmis, Martyn Amos, Wolfgang Bazhaf & Andy Tyrrell

Researchers in the field of biocomputing have, for many years, successfully harvested and exploited the natural world for inspiration in developing systems that are robust, adaptable and capable ? solutions to humandefined problems. However, in this position paper we argue that the time has now come for a reassessment of how we exploit biology to generate new computational systems. Previous solutions (the first generation of biocomputing techniques), whilst reasonably effective, are crude analogues of actual biological systems.
We believe that a new, inherently interdisciplinary approach is needed for the development of the emerging second generation of bio-inspired methods. This new modus operandi will require much closer interaction between the engineering and life sciences communities, as well as a bidirectional flow of concepts, applications and expertise. We support our argument by examining, in this new light, three existing areas of biocomputing (genetic programming, artificial immune systems and evolvable hardware), as well as an emerging area (natural genetic engineering) which may provide useful pointers as to the way forward.

Key words: bio-inspired computing, genetic programming, artificial immune systems, evolvable hardware, natural genetic engineering, biological plausibility

Source: Philoinfo

Posted by Tony Marmo at 16:42 GMT

Updated: Friday, 30 December 2005 16:48 GMT

Share This Post

Post Comment | Permalink

Language use in a branching Universe

By David Wallace

I investigate the consequences for semantics, and in particular for the semantics of tense, if time is assumed to have a branching structure not out of metaphysical necessity (to solve some philosophical problem) but just as a contingent physical fact, as is suggested by a currently-popular approach to the interpretation of quantum mechanics.

Source: Online Papers in Philosophy

Posted by Tony Marmo at 00:01 GMT

Updated: Friday, 30 December 2005 16:31 GMT

Share This Post

Post Comment | Permalink

COMPUTING AND PHILOSOPHY

IV European Meeting
E-CAP 2006@NTNU Norway

Norwegian University of Science and Technology Dragvoll Campus, Trondheim, Norway, June 22-24, 2006

Conference Co-Chairs:
Charles Ess (Drury University / NTNU)
May Thorseth (NTNU)

E-CAP 2006 is generously supported by the Programme for Applied Ethics and the Globalization Programme, NTNU.

E-CAP is the European conference on Computing and Philosophy, the European affiliate of the International Association for Computers and Philosophy (IACAP).

---

IMPORTANT DATES

January 27, 2006 Submission of extended abstracts
March 1, 2006 Notification of acceptance
May 5, 2006 Early registration deadline
June 22-24, 2006 Conference

GENERAL INFORMATION
From Thursday 22 to Saturday 24 June 2006 the Fourth International European Conference on COMPUTING AND PHILOSOPHY will be held on the Dragvoll

Campus of the Norwegian University of Science and Technology, Trondheim, Norway.

PROGRAM
Continuing the foci of the E-CAP conferences (beginning in Glasgow, 2002), ECAP'06 will deal with all aspects of the computational turn that has emerged over the past several decades, and continues to expand and develop as a result of the multiple interactions between philosophy and computing.

KEYNOTE SPEAKERS
Dr. Lucas Introna, Centre for the Study of Technology & Organisation, Lancaster University, UK
Dr. Raymond Turner, Department of Computer Science, University of Essex, UK
Dr. Vincent Hendricks, Department of Philosophy and Science Studies, Roskilde University, Denmark

RELEVANT RESEARCH AREAS
We invite papers that address all topics related to computing and philosophy, including cross- and interdisciplinary work that explores the computational turn in new ways. Hence, the following is intended to be suggestive, but not exclusive:

- Philosophy of Computer Science (see here.)
- Ontology (Distributed Processing, Emergent Properties, Formal
Ontology, Network Structures, etc)
- Computational Linguistics
- Global Information Infrastructures
- Philosophy of Information and Information Technology (Including: Information as structure; Semantic information)
- Interdisciplinary Approaches to the Problem of Consciousness and Cognition
- Computer-based Learning and Teaching Strategies and Resources & The Impact of Distance Learning on the Teaching of Philosophy and Computing
- IT and Gender Research, Feminist Technoscience Studies
- Information and Computing Ethics
- Biological Information, Artificial Life, Biocomputation
- New Models of Logic Software
- "Intersections" - e.g., work at the crossroads of logic, epistemology,
philosophy of science and ICT/Computing, such as Philosophy of AI
- Ethical and Political Dimensions of ICTs in Globalization.

SUBMISSION OF PAPERS
Authors should submit an electronic version of an extended abstract (total word count approximately 1000 words). The file should also contain a 300 word abstract that will be used for the conference web site/booklet. Final papers must not exceed a total word count of 3500 words and an abstract of not more than 500 words. The submissions should be made electronically, either as PDF, rtf ,or Word format.

To submit papers click here.
The extended abstract submission deadline is Friday 27th January 2006.

For information about paper submission and the program that is not available on the conference web site, please contact the Conference Co-Chairs.

REGISTRATION AND FEES

Registration will take place through the conference web site. The registration fee includes the conference reception, conference lunches and coffee and tea breaks, and one ticket to the conference banquet.

Discounted ("earlybird") registration fee (prior to May 5, 2006): € 200
Discounted registration fee - PhD students: € 100 Euro

Regular registration fee (after May 5, 2006): € 250
Regular registration fee - PhD students: € 150 Euro

(Masters and undergraduate students may register for the conference at no cost: a fee will be assessed, however, to cover the costs of the lunches and catering.)

ACCOMMODATION
To book accommodation, please visit the conference web site.

VENUE
The dragvoll campus at NTNU offers excellent conference facilities as well a beautiful physical setting as it overlooks Trondheim and the Trondheim fjord. The city of Trondheim (Norway's ancient capital and home to theNidaros Cathedral, the largest Gothic cathedral north of the Rhine) is easily accessible by air and rail, and is itself more than worth the visit. Beyond city-related information provided on the conference website, see this.

Source: Philo Info group

Posted by Tony Marmo at 16:54 GMT

Updated: Wednesday, 7 December 2005 17:01 GMT

Share This Post

Post Comment | Permalink

WHAT AWARENESS ISN'T:

A SENTENTIAL VIEW OF IMPLICIT AND EXPLICIT BELIEF

By Kurt Konolige

In their attempt to model and reason about the beliefs of agents, artificial intelligence (AI) researchers have borrowed from two different philosophical traditions regarding the folk psychology of belief. In one tradition, belief is a relation between an agent and a proposition, that is, a propositional attitude. Formal analyses of propositional attitudes are often given in terms of a possible-worlds semantics. In the other tradition, belief is a relation between an agent and a sentence that expresses a proposition (the sentential approach). The arguments for and against these approaches are complicated, confusing, and often obscure and unintelligible (at least to this author). Nevertheless strong supporters exist for both sides, not only in the philosophical arena (where one would expect it), but also in AI.
In the latter field, some proponents of posslble-worlds analysis have attempted to remedy what appears to be its biggest drawback, namely the assumption that an agent believes all the logical consequences of his or her beliefs. Drawing on initial
work by Levesque, Fagin and Halpern define a logic of General awareness that superimposes elements of the sentential approach on a possible-worlds framework. The result, they claim, is an appropriate model for resource-limited believers.
We argue that this is a bad idea: it ends up being equivalent to a more complicated version of the sentential approach. In concluding we cannot refrain from adding to the debate about the utility of possible-worlds analyses of belief.

Source: THEORETICAL ASPECTS OF RATIONALITY AND KNOWLEDGE

Posted by Tony Marmo at 00:01 GMT

Updated: Tuesday, 8 November 2005 08:11 GMT

Share This Post

Post Comment | Permalink

Belief Liberation (and Retraction)

By Richard Booth, Samir Chopra, Aditya Ghose and Thomas Meyer

We provide a formal study of belief retraction operators that do not necessarily satisfy the (Inclusion) postulate. Our intuition is that a rational description of belief change must do justice to cases in which dropping a belief can lead to the inclusion, or 'liberation', of others in an agent's corpus. We provide a few possible weakenings of the (Inclusion) postulate and then provide two models of liberation via retraction operators, σ-liberation and linear liberation. We show that the class of σ-liberation operators is included in the class of linear ones and provide axiomatic characterisations for each class. We also show how any given retraction operator (including the liberation operators) can be 'converted' into either a withdrawal operator (i.e., satisfying (Inclusion)) or a revision operator via (a slight variant of) the Harper Identity and the Levi Identity respectively.

Source: TARK

Posted by Tony Marmo at 00:01 GMT

Updated: Tuesday, 8 November 2005 07:56 GMT

Share This Post

Post Comment | Permalink

Logical Form: Classical Conception and Recent Challenges

By Brendan Jackson

The term ‘logical form’ has been called on to serve a wide range of purposes in philosophy, and it would be too ambitious to try to survey all of them in a single essay. Instead, I will focus on just one conception of logical form that has occupied a central place in the philosophy of language, and in particular in the philosophical study of linguistic meaning. This is what I will call the classical conception of logical form. The classical conception, as I will present it in section 1, has (either explicitly or implicitly) shaped a great deal of important philosophical work in semantic theory. But it has come under fire in recent decades, and in sections 2 and 3 I will discuss two of the recent challenges that I take to be most interesting and significant.

Source: Online Papers in Philosophy

Posted by Tony Marmo at 06:23 BST

Updated: Thursday, 20 October 2005 06:27 BST

Share This Post

Post Comment | Permalink