Philosophical Logic and Computational ConstraintsJohn
L. Taylor (Humboldt State University) 2002
Abstract:
Formal methods are central to philosophical logic.
Insofar as philosophical logic relies upon formal methods to
characterize rational thought and its contents, it is subject to computational
constraints: computability and tractability.
Moreover, when modeling human (or other finite beings) thought,
computational issues become decisive. Computability and complexity are explained
and applied to two-dimensional semantics (as presented by David Chalmers). Finally, a few ways to work within these constraints
are briefly considered.
1.
Introduction
2.
Formal Systems
2.1
Introduction to Formal systems
2.2
Church-Turing Thesis and Computers
3
Computational Constraints
3.1
Computability
3.2
Tractability
4
Philosophical Logic
4.1
2-Dimensional Semantics
4.1.1
Purpose
4.1.2
Description
4.1.3
An example: water & Twin Earth
4.1.4
Problems
5
Ways Forward
5.1
Heuristics (Approximation Algorithms)
5.2
Making Ill-defined problems Well-defined
5.3
Idealization and refinement
6
Conclusion References
1
Introduction
Formal methods are central to philosophical logic and
other philosophical disciplines. Insofar
as philosophical logic relies upon formal methods to characterize rational
thought and its contents, it is subject to computational constraints:
computability and tractability. Moreover,
when modeling human (or other finite beings) thought, computational
issues become decisive. In the
following paper, computability and complexity are explained in the context
of computer science and then applied to two-dimensional semantics (as
presented by David Chalmers) for the purpose of illustrating the importance
of these constraints for philosophy at large.
Finally, a few ways to accommodate these constraints are considered.
2
Formal Systems
Formal methods and systems
have a long and prestigious history in philosophy—from Euclid to Leibniz
to Frege and the other founders of the modern analytic school of philosophy
and on to today. The inferential
and descriptive powers of formal systems have made them integral to
many philosophical disciplines: logic, philosophical logic, philosophy
of mathematics and language, to name a few.
What is a formal system, we may ask, and how do they apply to
philosophical disciplines?
2.1
Introduction to formal systems
A formal language consists of an alphabet and grammar. The alphabet is a set of uninterpreted
symbols (e.g.: {#, @, $}). The
grammar is a set of rules that determine which strings of symbols
from the alphabet will be acceptable (grammatically correct or well-formed)
in that language. For example:
1.
Any string
starting with # is a wff,
2.
Any string
ending with $ is a wff,
3.
Nothing else
is a wff.
The grammar may also be conceived as a set of functions
taking strings of symbols as input and returning either "yes"
or "no" as output. The rules of the grammar are also called
formation rules. A formal system consists of a formal language (alphabet and grammar) and
a deductive apparatus (axioms and rules of inference). Axioms are the starting points at which
the rules of inference are applied. For example, using the alphabet and grammar from the previous paragraph,
we may specify the following rules of inference:
1.
If P and Q
are theorems, then PQ is a theorem
2.
If PP is a
theorem, then P is a theorem
3.
If P is a theorem,
then P@P is a theorem
And the following axioms:
1.
$
2.
##
Using the axioms and rules of inference, theorems
may be derived (e.g. $@$ and $#). Formal systems may be specified graphically or symbolically. Graphically, automata, cellular automata and
Turing machines may represent them.
Symbolically, 5-7 tuples (formally specifying states, alphabets
etc.) recursive function theory, Markov systems, and the lambda calculus
specify them. The details of
these individual specifications are out of the scope of this paper,
though their applicability and properties are central to the concerns
presented here. The applicability of formal systems is informed
by a couple of important equivalences. Once these are established some important properties may be discussed.
2.2
Church-Turing Thesis and Computers
The first
important equivalence is known as the Church-Turing Thesis. Originally, the Church-Turing thesis
stated that all intuitively effective methods are generally recursive
(Sipser 1997). Currently, the
thesis is taken more broadly to be that all intuitively effective methods
are equivalent to any one of several formalizations, including recursive
function theory, Turing machines, Markov algorithms, Lambda calculus,
and so on. This calls for more explanation. An effective method is an algorithm
for solving problems in a given class of problems that satisfies a number
of conditions (a.k.a. algorithm or decision procedure):
1.
it is logically
bound (as opposed to physically bound) to give some answer (as opposed
to no answer),
2.
it is correct,
as opposed to incorrect,
3.
it terminates
in a finite number of steps, as opposed to an infinite number,
4.
it does the
above every time, or for all inputs, or for all problems in the class
(as opposed to selectively),
5.
as far as necessary,
as opposed to only as far as our resources permit,
6.
each step in
the process is "dumb" or "mechanical". (Suber 2002)
Effective methods, so defined, may solve problems on
formal systems. For instance,
we may want to know whether a particular string is a wff or whether
a set of strings are wffs.. Another important equivalence holds between
formal systems and computers. A
computer may be seen as an instantiation of a formal system, and a formal
system may be seen to be an idealization of a computer. Table 1 illustrates the mapping of formal systems
to computers: (from Suber 1997):
Table 1 Depending on how strong we take this equivalence to
be, what we say of formal systems we may say of computers.
3
Computational Constraints
Given the equivalence between intuitively
effective methods, formal systems and computers, the following constraints
are applicable to all of them. Furthermore,
if the computationalists are correct, these constraints apply to humans.
This, as we shall see, has a great impact on the constraints
on human cognition and thus any characterization of it for philosophical
purposes or otherwise.
3.1
Computability
In 1928 David Hilbert and Wilhelm Ackermann posed the Entscheidungsproblem
or decision problem: is there a mechanical method (i.e. effective
procedure or algorithm) that can be applied to any mathematical assertion
and (at least in principle) will eventually tell whether that assertion
is true or not (is decidable)? A
formal system is decidable when there is an effective method
(as defined in section 2.2) for determining whether any given wff is
a theorem, that is, a system in which the set of theorems is a decidable
set. Sets and functions may be said to be decidable
when In 1936 Alan Turing answered Hilbert’s Entscheidungsproblem
negatively: There is no mechanical method that can be applied to any
mathematical assertion and tell whether that assertion is decidable
(Turing 1936). Briefly and informally,
his evaluation is as follows. In
light of the Church-Turing Thesis, we may evaluate the decidability
of decision problems by figuring out whether or not a Turing machine
can compute it. A decision problem is a problem for which there
is a ``yes'' or ``no'' answer; it is decidable when the algorithm that
solves it halts on all inputs in a finite number of steps. By this reasoning Turing reduced the decision
problem to what is called the halting problem. He then proved, in a fashion similar to Gödel’s,
that no general algorithm can decide whether a given Turing machine
halts. Equivalently, no mechanical
method that can be applied to any mathematical assertion and tell whether
that assertion is decidable.
3.2 Tractability
Tractability is the subject matter of Complexity Theory. Complexity Theory is a thriving sub-discipline
of computer science that analyses the difficulty of formal procedures.
There are many competing definitions of complexity, however, there are
two widely recognized measures of complexity (for algorithms): time
complexity and memory complexity. Time
complexity concerns the running time (or number of operations) of
algorithms; memory complexity concerns the amount of space (memory)
needed for algorithms. Time
complexity is sufficient for the concerns of this paper. Time complexity typically involves determining the upper bound of an algorithm.
To start this determination, two things must be made clear:
1.
A set of instances
of some characteristic size n and
2.
A true/false
decision depending of whether the instance fulfils a certain
criteria.
The Traveling Salesman (TSM) problem is a classic graph-searching
problem. In practical terms
the problem can be thought of as that of a salesman who wishes to perform
a circular tour of N cities, calling at each city once only and traveling
the minimum total distance possible.
The TSM (decision) problem may be
characterized this way:
1.
Instances:
A set of n cities with the matrix of (integer) distances connecting
the cities.
2.
Decision: True
if there is a no possible non-repeating, circular tour p shorter than
a tour t, and false otherwise.
The
TSM problem may then be evaluated.
For a tour of n cities, the number of possible solutions is T(n)=N!/2N,
or equivalently ½(N-1)!. Each
one of these possible solutions p must be checked against each other
in cycles, which set the value of t to the smallest p generated.
Traditionally the time complexity of a problem is represented
in big-O notation. In big-O
notation only the highest order term of the expression is considered,
so the time complexity of the TSM problem would be expressed as T(n)
= (On!). Ideally, an algorithm is linear time complex (i.e.
T(n) = (On)) or easier. Typically
nontrivial problems are at least polynomial time complex. Formally, polynomial time complexity is T(n)
= (On^k ) where k is a constant. When
the execution time of a computation, T(n), is no more than a polynomial
function of the problem size n, it is considered to belong to P (Polynomial
time problems). P is considered
tractable. Not all problems
are so easy—some are intractable. A problem is said to be intractable
if there is no polynomial time algorithm for deciding it. This includes exponential time problems (i.e.
T(n) = (Ok^n ) where k is a constant ) and worse. Instances of the problem may be tractable,
but a general solution to the problem is quite out of reach. For instance, consider the TSM problem (the most famous example of an intractable problem). For just twenty-five cities the number
of possible journeys is so immense that a computer evaluating a million
possibilities per second would take 9.8 billion years (around two-thirds
of the age of the universe!) to search through them all. Table 2 outlines the primary orders of complexity:
4 Philosophical Logic
Philosophical logic may be characterized as “the philosophical
elucidation of those notions that are indispensable for the proper characterization
of rational thought and its contents” (Lowe 2001). It is important to note that philosophical
logic is not really concerned with thought insofar as thought is a psychological
process (which is the subject-matter of empirical psychology and the
philosophy of mind), rather it concerns thoughts insofar as they have
contents which are evaluable as true or false. (Lowe 2001)
Two-dimensional semantics falls under the heading of philosophical
logic and may act as a test case for then application of computational
constraints on philosophical methods.
4.1
2-Dimensional Semantics
Two-dimensional semantics has a distinguished list
of advocates: Kaplan, Stalnaker, Evans, Davies, Humberstone, Chalmers
and Jackson. Much of the debate
within this group involves interpretations of the components of two-dimensional
semantics—this is not at issue here.
Rather, the formal implementation of the two-dimensional scheme
for reasoning across possible worlds is at issue.
First, a brief history of two-dimensional semantics is needed
to set the stage for the exposition of its purpose, description and
problems. The story of Two-dimensional semantics starts with Frege. Frege’s view of reference (as construed by
Chalmers 1996) sees a concept as determining a function f : W® R, where W is the set of possible worlds and
R is the set of referents. This
function is referred to as an intension.
The intension coupled with the specification of a world w determines
an extension f(w). This is understood
by Chalmers as extending a bridge between reason, meaning and possibility. Unfortunately, this account has been seen as
insufficient for many reasons and the connections between reason, meaning
and possibility have been shattered.
This is where two-dimensional semantics comes in.
4.1.1 Purpose
The purpose of two-dimensional
semantics can be said to be “restore the golden triangle of reason,
meaning, and possibility” (Chalmers forthcoming).
In less grandiose terms two-dimensional semantics may be seen
to provide means to differentiate senses and, generally, reason across
possible worlds.
4.1.2 Description
The core idea of two-dimensional semantics is that
there are two different ways in which the extension of an expression
depends on possible states of the world.
First, the actual extension of an expression depends on
the character of the actual world in which an expression is uttered. Second, the counterfactual extension of an expression depends
on the character of the counterfactual world in which the expression
is evaluated. Corresponding
to these two sorts of dependence, expressions correspondingly have two
sorts of intensions, associating possible states of the world with extensions
in different ways. On the two-dimensional
framework, these two intensions can be seen as capturing two dimensions
of meaning. Instead of f : W® R, two-dimensional semantics uses F : W* ´ W® R, where W* is the space of
centered possible worlds, W is the space of ordinary possible worlds
and R is the set of referents. The
first dimensional intension (W*) is referred to as the 1-intension;
the second dimensional intension (W) is referred to as the 2-intension.
1-intension picks out roughly the substance
with those properties connected to the center of a given world. 2-intensions pick out their actual referents
in all worlds. It is important
to note that there is a dependence relationship between the 1-intension
and the 2-intension; the latter is a function of the former (Chalmers
forthcoming , 1996). The possibilities evaluated in the second dimension
can be thought of or referred to as maximal metaphysical possibilities,
possible worlds, subjunctive possibilities or counterfactual possibilities. For present purposes I will call them possible
worlds. Possible worlds are
what might have been the case. The
possibilities evaluated in the first dimension reflect the nature of
a world from the point of view of a speaker using an expression within
a world (what might be the case). These
possibilities may be called maximal epistemic possibilities, centered
worlds or scenarios—I will call them scenarios.
Scenarios are marked with a "center", which is an ordered
pair of an individual and a time (primarily, to deal with indexicals).
We can think of the center of the world as representing the perspective
of the speaker within the world. A scenario corresponds to a maximally specific epistemically
possible hypothesis, or (for short) a maximal hypothesis: a hypothesis
such that if one knew that it were true, one would be in a position
to know any truth by reasoning alone.
Formally, a hypothesis H1 leaves another hypothesis H2 open if
the conjunctions of H1 with both H2 and its negation are epistemically
possible (See Plenitude Principle below for a definition). A maximal hypothesis is one that leaves no possible hypothesis open.
To every scenario, there should correspond a maximal hypothesis,
and vice versa. (Chalmers forthcoming). These ideas are summarized in Table 3:
Table 3
A set of scenarios defines the 1st dimension
and, thus the 1-intension of an expression; a set of possible worlds
defines the 2nd dimension and, consequently, the 2-intension
of an expression. Taken together
(as a Cartesian product) they produce a matrix.
This matrix defines an expressions two-dimensional intension. An expression's two-dimensional intension is
a function from scenarios to 2-intensions, or equivalently as a function
from pairs of scenarios and possible worlds to truth-values. Given the association relation between scenarios
and worlds, one can define the diagonal intension of a sentence's
two-dimensional intension. The
diagonal intension is equivalent to the 1-intension through the process
of diagonalization There are two definitions that guide Chalmers’ conception of two-dimensional
semantics:
1.
Core Thesis: For any sentence S, S is a priori iff S has a necessary 1-intension.
2.
Plenitude Principle: S is epistemically possible if and only if there is a scenario that
verifies S.
Central to both definitions is the idea of a canonical description. A canonical description D an idealized language L is a complete, semantically neutral description of world or scenario. A semantically neutral term is one that involves no names, natural kind terms, or indexicals (including 'actual') either explicitly or implicitly. The core thesis can be restated as: a sentence S is a priori iff for all scenarios W with canonical description D, D implies S (If S is a priori, D implies S for any D). Applying canonical descriptions to the plenitude principle, a scenario W verifies sentence S when its epistemic intension is true. The epistemic intension of a sentence token is a function from a space of scenarios to the set of truth-values—it is defined as follows: the epistemic intension of a sentence token S is true at a scenario W iff D epistemically necessitates S, where D is a canonical description of W.
4.1.3 An example: Water & Twin Earth
To make two-dimensional semantics clearer we may take
the case of 'water is H2O'. Consider
table 4:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||