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:
Table 4
The 1-intension as well as the diagonal of the matrix
picks out the dominant, clear, drinkable liquid in all possible scenarios,
thus capturing the sense of water across possible worlds. In scenario W*1, ‘water is H2O’ is true roughly
when the dominant, clear, drinkable liquid has a certain pattern of
chemical structure. In a possible
world, it is true when H2O is H2O.
The reference of 'water' is fixed roughly by picking out the
substance with certain properties and a certain connection to the speaker
in the actual world, so its 1-intension picks out roughly the substance
with those properties connected to the “center” of a given world.
Similarly, the 1-intension of 'H2O' picks out the substance with
the right sort of chemical structure in a centered world. The 2-intension pick out H2O in all worlds. Given W*2 'water is XYZ', the XYZ-world verifies a
metaphysically impossible statement ('water is XYZ'). This is not, presumably, a problem on a two-dimensional evaluation:
'water is XYZ' is true at the XYZ-world considered as actual, but false
at the XYZ-world considered as counterfactual. The metaphysical impossibility of 'water is XYZ' reflects the fact
that it is false at all worlds considered as counterfactual. This is compatible with its being true at some
worlds considered as actual.
4.1.4 Problems
There are many interesting objections to two-dimensional
semantics. Presently, I am concerned
only with a formal critique. Applying
computability and complexity notions to two-dimensional semantics, we
may ask and answer two important questions about its computational properties:
Is two-dimensional semantics decidable? Is it tractable? As will be shown, the answer to the former question is yes, the
latter, no. The first difficulty in applying computability and
complexity to any philosophical model is clarity. To analyze the computability and complexity of two-dimensional semantics
we must characterize its use algorithmically (or at least pseudoalgorithmically).
To do so, the questions must be made more specific: Can we use two-dimensional
semantics to determine if a sentence is a priori or determine what is
epistemically possible? Lets consider the first question. According
to the core thesis, for any sentence S, S is a priori iff S has a necessary
1-intension. To determine if
S has a necessary 1 intension
1.
Instances:
A set of scenarios which are the Cartesian product of W* ´ W represented as an infinite
matrix of truth-values.
2.
Decision: True
when all scenarios W with canonical description D, D implies S, or else
false.
A
problem is apparent right away—no instances can be made to evaluate
because to do so would require an infinite amount of time to make. This makes the determination of a prioricity
at least intractable. It is
not clear that it is incomputable, because the instances are so ill-defined
it is not clear how they could be evaluated in terms of equivalence
to the halting problem.
1.
Instances:
A set of scenarios which are the Cartesian product of W* ´ W represented as an infinite
matrix of truth values.
2.
Decision: True
when a canonical description D of a scenario W epistemically necessitates
S, or else false.
Again, no full instance can be made to evaluate. To be fair this instance does not need to be complete to be evaluated, rather it may constructed stepwise and checked for the decision condition. However a big problem crops up with the decision condition—it requires that permutations of canonical descriptions be made and checked for S being a theorem of D. For any D rich enough to support arithmetical statements, it is equivalent to the halting problem and the decision problem and is thus incomputable.
5
Ways Forward
There are three primary ways to
accommodate difficulties with incomputability and tractability: heuristics,
redefinition and idealization. The
central definitions of two-dimensional semantics and the model of two-dimensional
semantics itself may be salvageable by these means.
5.1
Heuristics (Approximation Algorithms)
When faced with intractable problems computer scientists have
turned to approximation algorithms.
Though incapable of solving problems to a deductive certainty,
heuristics are tractable. It
is doubtful that a “rule of thumb” approach to defining the concepts
of two-dimensional semantics would be appropriate to the philosophical
ends that it tries to serve. A better approach in line with heuristics would
be approximation algorithms. These
are algorithms that run in polynomial time and have a performance guarantee
within a specified factor of the optimal.
5.2
Making Ill-defined problems Well-defined
Another method is to redefine ones
problem so that it becomes tractable.
Computationally intractable
problems are
sometimes called ill-defined because the way in which the problem is
set up destroys all chance of answering it.
Problems may be made well-defined by being clearer on the relevant
search space. This is usually
done by adding constraints (or frames) to the search space or function. For example, epistemic possibility may be defined
in a computable manner if the process of generating scenarios wasn’t
so open. So, for instance, scenarios
may be generated within constraints defined by the S being evaluated
and, perhaps, even the purpose of the investigation.
5.3
Idealization and refinement
Finally, to salvage a model, one
may admit that it is idealized. Chalmers
admits as much at times, but seems to forget when making claims based
upon his highly idealized model. To
be constructive when taking this route it is necessary to account for
the discrepancies between the model and the modeled. In the case of two-dimensional semantics the discrepancies are great
and the accounting for them is virtually non-existent.
6
Conclusion
While it may be unfair to ask for
such a high level of formalization and thoroughness from the advocates
of two-dimensional semantics when they are (seemingly) more concerned
with consistent interpretations at this point, algorithmic explicitness
is necessary for it to be a usable and faithful model of our language. Moreover, once made more explicit, two-dimensional
semantics must negotiate the problems of incomputability and intractability.
The methods of two-dimensional semantics need revision insofar
as they are an attempt to model our language. Generally speaking, computational
constraints should concern any philosopher using formal methods.
Barring the possibility of humans transcending the abilities
of computers, when claims are made about human reasoning they must be
within the grasp of our finite mental resources.
As such, for the sake of being evaluable, we must be formally
(algorithmically) explicit and, at some point, prove our models to be
computable as well as tractable. Making our models computable and tractable
may cause us to loose some of the Platonistic purity of our models,
but doing so will keep us honest.
References
Chalmers,
D.J. 1994. A computational foundation for the study of cognition. Philosophy-Neuroscience- Psychology Technical Report 94-03, Washington University. http://www.u.arizona.edu/~chalmers/papers/computation.html. Chalmers,
D.J. 1996. “The Conscious Mind: In Search of a Fundamental Theory”
Oxford University Press. Press. Chalmers,
D. J. forthcoming. The foundations of two-dimensional semantics. http://consc.net/papers/foundations.html. Chalmers,
D. J. and Jackson, F. 2001. Conceptual analysis and reductive explanation.
Philosophical Review 110:315-61. http://www.u.arizona.edu/~chalmers/papers/analysis.html. Flake,
G.W. 2000. "The Computational Beauty of Nature" MIT
Press. USA. Hunter,
G. 1971. “Metalogic: an introduction to the metatheory of standard first
order logic” University of California Press, Lowe,
E. J. 2001 Philosophical
Logic http://www.dur.ac.uk/philosophy.department/modules/logic/PHILLOG.HTM Sipser,
M. "Introduction to the Theory of Computation", PWS
Publishing Company, 1997. Suber, Peter. 1997. Formal Systems and Machines: An Isomorphism
http://www.earlham.edu/~peters/courses/logsys/machines.htm Suber, Peter. 2002. Glossary of First-Order Logic http://www.earlham.edu/~peters/courses/logsys/glossary.htm Turing,
A.M. 1936. On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society, Series
2
42: 230-65. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||