Article #2
Subject: 2008 MAS talk
Author: Andrew W. Harrell
Posted: 8/20/2008 05:59:12 PM

CAN MATHEMATICS, COMPUTER SCIENCE,
AND STATISTICS HELP US UNDERSTAND
WHETHER FAITH AND REASON CAN INTERACT

In this talk we will look at a part of the recent discussion
of theologians about science and religion. This part concerns how
mathematics, computer science, and statistics might be able to
present arguments that explain how faith and reason interact. In
the book by William Demski, “No Free Lunch (NFL)” some of
the mathematics and computer science in the two earlier papers
by Wolpert and Macready have been used to support the authors\'
philosophical, statistical arguments for the necessity of what is
called “The intelligent design of the Universe”. The question
then comes down to whether there is an intelligent designer of
our genome? However, in a later paper by the same two authors,
they have given a mathematical counterexample to the key
statement in Chapter 4 of the NFL book that the mathematical
arguments there can deal with “the coevolving fitness schemes of
Dr. Kaufmann”. Does this mathematical result then invalidate Dr.
Demski’s philosophical/statistical conclusions?


Slide 1

Elements of a Theory of Intelligent Design

H(a sub i) = Sum sub i (- p sub i * I(a sub i)

I(a sub i) = (- log base 2 p sub i)

Sub i means subscript i



Definition of Contingency, Complexity and Specification
– Information theory terminology
– Contingency is a form of probability
– Specification is determined from
– 1) a reference class of possible events
– 2) a pattern that restricts the reference class and warrants a
design inference
– 3) a precise event that has occurred.
A theory of explanation requires
– Bayesian statistics
– Necessity versus contingency
– Law versus intelligent agency
• Evolutionary Algorithm
– Blind search versus goal-directed search

In algorithmic information theory complexity is defined in terms of the
compressibility of 0,1 bit strings.
Given 2 (or n) distinct characters a sub i with probabilities of occurrence
p sub i the average complexity (information or entropy) is defined to be H(a
sub i) where I(a sub i) is the information in any given character.
Given this definition of complexity, intelligent design can be detected by

The methodology of statistical hypothesis testing.
This is done by computing the Bayesian (or after the fact) probability that
a given level of information (complexity)
Occurred from a chance hypothesis (a sequence of random events).


Slide 2

No Free Lunch Theorem

• Assuming the search space is ergodic, and made up of a single set of
states, for any two, black box, genetic search algorithms (strategies which
can be deterministic or random) and given cost function, their performance
(in the average over the whole search space) is the same.
Ergodic is a term from the theory of mathematical dynamical systems. It
means, roughly speaking, that a time dependent function from state space to
that same state space (the search algorithm in this case mapping from the
set of state possibilities into the set of state possibilities as it search
them) covers the whole state space as it maps over all of time.

Black box search algorithms do not rely on partial path solutions to compute
the next step

Slide 3

Philosophic Implications of the NFL Theorem for the Intelligent Design
Hypothesis

• When computing the a posteriori probability of our current genome
occuring from random chance we can take a simple fractional ratio of the
total number of possibilities (which are all equal by the NFL Theorem) to a
seemingly impossibly small number of actualities in which intelligent life
flourishes.

Slide 4

Coevolutionary Counterexamples to the Free Lunch Theorem
• If in our genetic cost optimization search functions we include the
possibility of two interacting players as a set of ordered state pairs in
the search space of the algorithm, then there are examples in which the
performance of one search strategy (averaged over the whole search space) is
better than the others.

Slide 5

Description of a search procedure or algorithm such as that needed for
coevolutionary genetics in order to keep track of partial paths.

• Step 1: Form a queue of partial paths. Let the initial queue consist
of the zero-length,
• Zero-step path from the start node to nowhere.
• Step 2: Until the queue is empty or the goal has been reached,
determine if the first in the queue reaches the goal node.
• 2a: If the first path reaches the goal node, do nothing.
• 2b: If the first path does not reach the goal node:
• 2b1: Remove the first path from the queue.
• 2b2: Form new paths from the removed path by
extending them one step.
• 2b3: Add the new paths to the queue.
• 2b4 Sort the queue by cost accumulated so far,
• with least cost paths placed in front.
• Step 3: If the goal node has been found, announce success; otherwise
announce failure.
This algorithm is discussed in the book Artificial Intelligence, 2nd edition
by Winston (1984) where it is called a branch and bound search. It can also
be modified slightly to do a complete network search from a starting set of
source nodes to an ending set of sink nodes in a directed or undirected
network. Harrell used it in Evaluating the Effect of Off-Road Obstacles on
Unit Movement, WES report GL-89-4 (1984). There he has listed the code to do
it in Prolog and Pascal. The code is also available in C from Harrell. It
terminates when the shortest incomplete path is longer than the shortest
complete path. That is, when all partial paths to goal nodes are as long or
longer than complete paths.


Slide 6

Implications of the Coevolutionary Counterexamples of Wolpert and Macready
to Philosophic Inferences Drawn by Dembski from the NFL Theorem


• There exist genetic search algorithms which self-organize and adapt
from less complex to more complex systems. Hence, when computing the
Bayesian a posteriori probability of the occurrence of our current genome,
statistics does supply an argument that it is necessary to hypothesize an
intelligent agency outside of the system itself (which creates it and
sustains it).

Slide 7


References


No Free Lunch, Why Specified Complexity Cannot be Purchased without
Intelligence, William A Dembski, Roman and Littlefield 2002
See the internet site www.nofreelunch.org for many more references to recent
work in this area
The Origins of Order, Self-Organization and Selection in Evolution, Stuart
A. Kauffman, Oxford U. Press, 1999
Investigations, Stuart A. Kauffman, Oxford U. Press, 2000
No Free Lunch Theorems for Optimization, David H. Wolpert and William G.
Macready, IEEE Transactions on Evolutionary Compuation, Vol. 1, no. 1, 1997
Coevolutionary Free Lunches, David H. Wolpert and William G. Macready, IEEE
Transactions on Evolutionary Compuation, Vol. 9, no. 6, 2005