7

II

Algorithmic Specified
Complexity

WINSTON EWERT, WILLIAM A. DEMBSKI, AND
ROBERT J . MARKS II
Baylor University
Discovery Institute

Abstract
Engineers like to think that they produce something different from that of a chaotic
system. The Eiffel tower is fundamentally different from the same components lying
in a heap on the ground. Mt . Rushmore is fundamentally different from a random
mountainside. But engineers lack a good method for quantifying this idea. This
has led some to reject the idea that engineered or designed systems can be detected.
Various methods have been proposed, each of which has various faults . Some havetrouble distinguishing noise from data, some are subjective, etc. For this study, conditional Kolmogorov complexity is used to measure the degree of specification of an
object. The Kolmogorov complexity of an object is the length of the shortest computer program required to describe that object. Conditional Kolmogorov complexity
is Kolmogorov complexity with access to a context. The program can extract information from the context in a variety of ways allowing more compression . The
more compressible an object is , the greater the evidence that the object is specified . Random noise is incompressible, and so compression indicates that the object
is not simply random noise . This model is intended to launch further dialog on useof conditional Kolmogorov complexity in the measurement of specified complexity.

1

Introduction

Intuitively, humans identify objects such as the carved faces at Mount Rushmore as
qualitatively different from that of a random mountainside. However , quantifying this
131

132

Algorithmic Specified Complexity

Figure 7.1: T he faces of Mount Rushmore- P ublic Domain

concept in an objective manner has proved difficult. Both mountainsides are madeup of the same material components. T hey are both subject to the same physicalforces and will react the same to almost all physical tests. Yet, there does appear tobe something quite different about Mount Rushmore. There is a special something
about carved faces that separat es it from the rock it is carved in.
This "special something" is information. Information is what distinguishes
an empty hard disk from a full one. Information is t he difference between random
scribbling and carefully printed prose. Information is the difference between car partsstrewn over a lawn and a working truck.
While humans operate using an intuitive concept of information , attempts todevelop a theory of information have thus far fallen short of the intuitive concept.
Claude Shannon developed what its today known as Shannon information theory(Shannon et al. , 1950) . Shannon's concern was studying the problem of communication, that of sending information from one point to another. However, Shannon
explicitly avoided t he question of the meaningfulness of the information being transmitted, thus not quite capturing the concept of information as defined in this paper.
In fact , under Shannon's model a random signal has the highest amount of information, the precise opposit e of the intuitive concept .
Another model of information is that of algorithmic information theory(Chaitin, 1966; Solomonoff, 1960; Kolmogorov, 1968b). Techniques such as Kolmogorov complexity measure the complexity of an object as t he minimum length
computer program required to recreate the object; Chaitin refers to such minimum
length programs as elegant (Chaitin, 2002). As with Shannon information, random
noise is the most complex because it requires a long computer program t o describe.

Introduction

133

In contrast, simple patterns are not complex because a short computer program candescribe the pattern. But neither simple patterns nor random noise are considered
conceptual information. As with Shannon information, there is a disconnect between
Kolmogorov complexity and conceptual information.
Other models are based on algorithmic information theory, but also take into
account the computational resources required for the programs being run. Levincomplexity adds the log of the execution time to the complexity of the problem(Levin, 1976) . Logical depth, on the other hand, is concerned with the execution
time of the shortest program (Bennett , 1988) . T here is a class of objects which areeasy to describe but expensive to actually produce. It is argued (Bennett , 1988) that
objects in this class must have been produced over a long history. Such objects areinteresting, but do not seem to capture the intuitive concept of information in its
ent irety. English text or Mount Rushmore correspond to what is usually considered
as information, but it is not clear that they can be most efficiently described as longrunnmg programs .
One approach to information is specified complexity as expressed by Dembski(Dembski , 1998) . Dembski's concern is that of detecting design , the separation ofthat which can be explained by chance or necessity from that which is the product ofintelligence. In order to infer design , an object must be both complex and specified.
Complexity refers, essentially, to improbability. The probability of any given object
depends on the chance hypothesis proposed to explain it . Improbability is a necessary
but not sufficient condition for rejecting a chance hypothesis. Events which have ahigh probability under a given chance hypothesis do not give a reason to reject that
hypothesis .
Specification is defined as conforming to an independently given pattern. The
requirement for the pattern to be independent of t he object being investigated isfundamental. Given absolute freedom of pattern selection, any object can be madeto seem specified by selecting that object as the pattern. It is not impressive to hit abullseye if the bullseye is painted on after the arrow has hit the wall. It is impressive
to hit the bullseye if the bullseye was painted before the arrow was fired .
Investigators are often not able to choose the target prior to investigat ing the
obj ect. For example, life is a self-replicating process, and it would seem that an
appropriate specification would be self-replication. Self-replication is what makes life
such a fascinating area of investigation as compared to rocks. Human beings know
about self-replication because of their knowledge of life, not as an independent fact.
Therefore, it does not qualify as an independent specification.
The same is true of almost any specification in biology. It is tempting toconsider flight a specification , but the pattern of flight would only be defined because
flying animals have been observed. As with life in general, specific features in biology
cannot be specified independently of the objects themselves.
The concept of specification has been criticized for being imprecisely definedand unquantifiable. It has also been charged that maintaining the independence

Algorithmic Specified Complexity

134of the patterns is difficult. But specification has been defined in a mathematicallyrigorous manner in several different ways (Dembski, 1998, 2002, 2005) . Kolmogorov
complexity, or a similar concept, is a persistent method used in these definitions.
The goal of this paper is to present and defend a simple measure of specificationthat clearly alleviates these concerns. Towards this end, the authors propose touse conditional K olmogorov complexity to quantify t he degree of specification in an
object. Conditional Kolmogorov complexity can then be combined with complexity
as a measurement of specified complexity. This approach to measuring specifiedcomplexity is called algorithmic specified complexity.
As noted, Kolmogorov complexity has been suggested as a method for measuring specification. The novelty in the method presented here is the use of conditional
Kolmogorov complexity. However, this paper also elucidates a number of examples ofalgorithmic compressibility demonstrating wider applicability than is often realized.

2

Method

2.1

Kolmogorov

Kolmogorov complexity is a method of measuring information. It is defined as t heminimum length computer program, in bits, required to produce a binary string.
K(X) =

min

U(p,)=XIpEP

IPI

(7.1)

where
• K (X ) is the Kolmogorov complexity of X

• P is the set of all possible computer programs• U(p , ) is the output of program p run without input
T he definition is given for producing binary strings.
Kolmogorov complexity measures the degree to which a given bitstring follows
a pattern. The more a bitstring follows a pattern, t he shorter the program required
to reproduce it. In contrast , if a bitstring exhibits no patt erns, it is simply random,
and a much longer program will be required to produce it.
Consider the example of a random binary string, 100100000010100000001010.
It can be produced by the following Python program:print '100100000010100000001010 'Figure 7.2: A Python program to produce an unpatterned
bitstringMethod135

In contrast, the string 000000000000000000000000 can be produced byprint ' 0'

* 24

Figure 7.3: A Python program to produce a patterned bitstring

Both strings are of the same length, but the string following a pattern requiresa shorter program to produce; thus, a technique exists for measuring the degree towhich a binary string follows a pattern.
Specification is defined as following an independently given pattern. Kolmogorov complexity provides the ability to precisely define and quantify the degree
to which a binary string follows a pattern. T herefore, it seems plausible that a specification can be measured using Kolmogorov complexity. The more compressible a
bitstring, the more specified it is.
However, Kolmogorov complexity seems unable to capture the entirety of what
is intended by specification. Natural language text is not reducible to a simple pattern;
however, it is an example of specification. The design of an electronic circuit should
also be specified, but it is not reducible to a simple pattern. In fact , the cases of
specification t hat Kolmogorov complexity seems able to capture are limited to objects
which exhibit some very simple pattern. But these are not t he objects of most interestin t erms of specification.
There is also an extension of Kolmogorov complexity known as conditional
Ko lmogorov complexity which can be used (Kolmogorov, 1968a). With conditional
Kolmogorov complexity, the program now has access to additional data as its input.

K(X IY ) =min

U(p,Y) =XIpEP

IPI

(7.2)

where U (p , Y) is the output of running program p with input Y.
In this calculation, the input provides additional data to the program. As aresult, the program is no longer restricted to exploiting patterns in the desired output
but can take advantage of the information provided by the input. Henceforth , t his
input is referred to as the context.
The use of context allows the measure to capture a broader range of specifications. It is possible to describe many bitstrings by combining a short program alongwith the contextual information. A useful range of specifications can be captured
using this t echnique.

2.2

Algorithmic Specified Complexity

The following formula for algorithmic specified complexity (ASC) combines the measurement of specification and complexity.

A(X, C,p) = - logp(X) - K (X IC)(7.3)

Examples

137

counter = 0
f or each possible building design
if building won't fall overcounter += 1
i f counter == X
return bui l ding design
Figure 7.4: A pseudocode program which uses a functional
test to compress the specification of an object by its functionality

T his program will output the design for a specific building based on a given
value for X . Different values of X will produce different buildings. But any buildingthat will not fall over can be expressed by t his program. It may take a considerable
amount of space to encode this number. However, if few designs are stable, t henumber will take much less space than what would be required to actually specify thebuilding plans. Thus, t he stability of the building plan enables compression, which
in turn indicates specification .
Kolmogorov complexity is not limited to exploiting what humans perceive as
simple patterns. It can also capture other aspects such as functionality. Functionality
can be described as passing a test. As a result , functional objects are compressible.

3

Examples

3.1

Natural Language

Consider the sentence: "The quick brown fox jumps over the lazy dog." T his sentence
can be encoded as UTF-32, a system for encoding that allows the encoding of symbols
from almost any alphabet. Since each character takes 32 bits, the message will be
encoded as a total of 1,376 bits. In this example, t he context will be taken to be theEnglish alphabet along with a space. This is a minimal level of information about
the English language.
To specify one of the 27 characters requires log 2 27 bits. To specify the 43
characters in the sentence will thus take 43log 2 27 bits. The number of characters
are recorded at 2 log2 43 ~ 10.85 bits.1 Altogether, t he specification of the message
requires 43log2 27 + 2log2 43 ~ 215.32 bits.
However, in order to actually give a bound for Kolmogorov complexity, thelength of the computer program which interprets the bits must also be included. Hereis an example computer program in Python which could interpret the message
1 A more compact representation for numbers is available. See the log* method in Cover &T homas (2006).

A lgorithmic Specified Complexity

138

pr i nt ' ' . join(alphabet[index] fo r i ndex i n encoded_message)
F igure 7.5: An example Python program to interpret theencoded message

T his assumes that t he alphabet and encoded message are readily available andin a form amenable to processing within the language. It may be t hat t he input has
t o be preprocessed, which would make t he program longer. Additionally, the lengthof t he program will vary heavily depending on which programming language is used.
However, t he dist ances between different computers and languages only differ by aconst ant (Cover & T homas, 2006). As a result, it is common practice in algorithmic
information t heory t o discount any actual program length and merely include t hat
length as a constant , c. Consequently, the conditional Kolmogorov complexity canbe expressed as
K (X IC) :::; 215.32 bits+ c.
(7.4)
T he expression is less than rather than equal to because it is possible that an evenmore efficient way of expressing the sentence exists. However, at least t his efficiency
is possible.
T he encoded version of the sent ence requires 32 bits for each character, givinga total of 1,376 bits. Using a simplistic probability model, supposing that each bit isgenerated by t he equivalent of a coin flip, the complexity, -log P(X ), would be 1376
bits. Using equation 7.3,
A (X, C,p) = -log(p) - K(XIC) ~ 1376 bits - 215.32 bits- c = 1160.68 bits - c.
(7.5)
This shows 1,166 bits of algorithmic specified complexity by equation 7.3. Those 1166
bits are a measure of t he confidence in rejecting t he hypothesis t hat the sentence was
generat ed by random coin flips. The large number of bits gives a good indication t hat
it is highly unlikely that t his sentence was generated by randomly choosing bits.
T he hypothesis t hat the sentence was generated by choosing random English
letters can also be analyzed. In t his case the probability of this sentence can becalculated asP(X ) =

(2\)

(7.6)

43

T he complexity is t hen
1- log P(X) = - log ( 27

)43 = 43 log 27 204.46 bits,
~

(7.7)

in which case the algorithmic specified complexity becomes
A (X, C,p) = - logp(X)- K(X IC) ~ 204.46 bits - 215.32 bits- c = - 10.85 bits - c.
(7.8)

Examples

139

The negative bound suggests no reason to suppose that this sentence could not havebeen generated by a random choice of English letters. The bound is negative as aresult of two factors . In the specification , 10.85 bit s were required to encode thelength. On the other hand , the probability model assumes a length. Hence, thenegative bits indicate information which t he probability model had , but was notprovided in the context . Since the only provided context is that of English letters,
this is not a surprising result. No pattern beyond that explained by the probability
model is identified.
T he context can also be expanded. Instead of providing the English alphabet
as the context , the word list of the Oxford English Dictwnary can be used (OED
Online, 201 2). In the second edition of that dictionary there were 615,100 word forms
defined or illustrated. For the purpose of the alphabet context, each letter is encoded
as a number corresponding to that character. In this case, a number corresponding
to words in the dictionary is chosen. Thus the number of bits required to encode themessage using this context can be calculated:
K (X jC ) ::::; 9 log 2 615, 100 + 2 log 2 9 + c;::::; 179.41 + c.

(7.9)

Access to the cont ext of the English dictionary allows much better compression t han
simply the English alphabet as comparing equations 7.4 and 7.9 shows.
Using equation 7.3 yields
A (X , C, p) = -logp(X ) - K (X jC ) 2': 204.46 bits - 179.41 bits - c = 25.05 bits- c.
(7.10)
This provides confidence to say this sentence was not generated by randomly choosing
letters fr om the English alphabet .
It is possible to adopt a probability model that selected random words fromthe English language. Such a probability model would explain all of the specificationin the sentence. It is also possible to include more information about the English
language such that the specification would increase.
This technique depends on the fact that the numbers of words in the English language is much smaller then the number of possible combinations of letters.
If the dictionary contained every possible combination of letters up to some finite
length, it would not allow compression , and thus be of no help to finding evidence ofspecification . A language where all possible combinations of lett ers were valid words
could still show specification, but another technique would have to be used to allow
com pressiOn.
But one could also use a much smaller dictionary. A dictionary of 10 words
would be sufficient to include all the words in t his sentence. The ASC formula would
give a much smaller compressed bound:
K (X jC ) ::::; 9 log 2 10 + 2 log 2 9;::::; 36.24 bits.

(7.11)

This is a reduction of over 100 bits from equation 7.9. Because the sentence is much
more closely related to the context , it takes about 16 bits less to encode each word

Algorithmic Specified Comp lexity

140

when the dictionary is this small. In other words , it requires much less additional
information to use the context when it is closely related to the message.
But it is possible to include words not included in the dictionary. The program
would have to fall back on spelling the word one letter at a time. Only the boundsof the ASC can be computed. It is always possible a better compression exists, i.e.,the object could be more specified than first realized.

3 .2

Random Noise

While natural language is an example of something that should be specified, random
noise is an example of something which should not . Consider a random bitstring
containing 1,000 bits , where each bit is assigned with equal probability 1 or 0. Since
randomness is incompressible, calculating the Kolmogorov complexity is easy. The
only way of reproducing a random bitstring is to describe the whole bitstring.
K(X) ::; 2log 2 1000 + 1000 + c ~ 1020 bits+ c(7.12)The probability of each bitstring is 2- 1000 , and thus the complexity will be 1000 bits .
Calculating the ASC:
A(X, C,p) = -logp(X) - K(XIC):::: 1000 bits-1020 bits-c = - 20 bits-c. (7.13)

As expected, the ASC is negative , and there is therefore no evidence of patterns inthe string that are not explained by the probability model.
However, consider also the case of a biased distribution. That is, 1 and 0 are
not equally likely. Instead, a given bit will be 1 two thirds of the time , while 0 only
one third of the time. The entropy of each bit can be expressed as
1
1
2
2
H(Xi) = - 3 log 2 3 - 3 1og 2 3 ~ 0.6365 bits

(7.14)

for any i . The entropy of a bit is the number of bits required in an optimal encoding
to encode each bit . This means the whole sequence can be described as
K(X) ::; 2 log 2 1000 + 1000 * H(Xi) + c ~ 656.5 bits + c.

(7.15)

Using the uniform probability model, the complexity is still 1,000 bits andA(X, C ,p) = -logp(X)- K(XIC) :::: 1000 bits- 656.5 bits - c = 343.3 bits- c.

(7.16)
This random sequence has a high bound of algorithmic specified complexity. It is
important to remember that the ASC bound only serves to measure the plausibilityof the random model. It does not exclude the existence of another more accurate
model that explains the data. In this case, using the actual probability model used
to generate the message yields- log 2 (p) = H(Xi) * 1000 ~ 636.5 bits

(7.17)Examples141

and the resulting ASC :A (X , C,p) = - logp(X) - K (X IC ) 2 636.5 bits- 656.5 bits - c = - 20 bits- c.
(7.18)The bound of ASC provides reason to reject a uniform noise explanation for this data,
but not the biased coin distribution.
Dembski (Dembski, 1998) has considered the example of ballot rigging wherea political party is almost always given the top billing on the ballot listing candidat es.
Since the selection is supposed to be chosen on the basis of a fair coin toss, this issuspicious. ASC can quantify this situation. T he outcome can be described by giving
the numbers of heads and tails, followed by the same representation as for the biased
coin distribution.

+ X h) + c
K(X)::; 2 logXh + 2 logXt +log ( Xt Xh(7.19)

where Xh is the number of heads, Xt is the number of tails Assuming a probability
model of a fair coin yields(7.20)
This results in the following:(7.21)
Figure 7.6 shows the result of plotting this equation for varying numbers of head
and tails given 20 coin tosses. As expected, for eit her high numbers of tails or highnumber of heads , the bound of ASC is high. However , for an instance which looks
like a random sequence, the ASC is minimized.

3.3

Playing Cards

Another pertinent case is that of playing cards in poker. In playing cards, if the distribution is not uniform, somebody is likely cheating. For the purpose of investigatingcard hands, a uniform random distribution over all five-card poker hands is assumed.
In the game of poker, a poker hand is made up of 5 cards. Some cat egories ofhands are rarer then others. Table 7.1 shows the frequency of t he different hands.
Given a uniform distribution , every poker hand has the same probability andthus the same complexity. There are 2,598,960 possible poker hands. For a single
hand, this yields a complexity of(7.22)

A lgorithmic Specifi ed Complexity

142

10,------~--~--~------,

-5

-10

- 15.;--o-----;--------;1:-;c-o-----;;15,..--------;20
number ot heads

Figure 7.6: ASC for varyingly biased coin sequences and 20
coin tosses

NameRoyal Flush
Straight FlushFour of a Kind
Full House
Flush
Straight
Three of a Kind
Two Pair
One PairNone

Frequency
4
36
624
3,744
5,108
10,20054,912
123,552
1,098,240
1,302,540

Table 7. 1: Poker hand frequency

Examples

143

Name
Royal Flush
Straight FlushFour of a Kind
Full House
Flush
Straight
Three of a Kind
Two pair
One pairNone

Frequency
4
36
624
3,744
5,108
10,20054,912
123,552
1,098,240
1,302,540

Complexity
21.31021.31021.31021. 31021.31021.31021.31021. 31021.31021.310Compressed Length
5.322
8.492
12.607
15. 192
15.64016.63819.06720.237
21. 31021.310ASC
15.98812.818
8.702
6.117
5.669
4.671
2.243
1.073
0.000
0.000

Table 7.2: The ASC of the various poker card hands
W hile the probability of every poker hand is the same, the Kolmogorov complexity
is not. To describe a royal flush requires specifying t hat it is a royal flush and which
suit it is in. However, describing a pair requires specifying the paired value as well
as both suits in addition to the three cards not involved in t he pair. In general,
describing a hand requires specifying the type of hand and which particular hand of
all the possible hands of that type. T his can be used t o calculate the conditional
Kolmogorov complexity for the hand.
(7.23)

where 10 is t he number of types of hands. H is the set of all hands of a particular
type, and Hi is a particular hand in that set.
T here are 1,098,240 possible pairs. P utting t his in Equation 7.23 gives:

K (Hi iC ) ::::; log2 10 + log2 IHI + c ~ 23.39 bits + c.

(7.24)On the other hand, describing a pair without using the context gives

K (Hi iC ) :S log2 2, 598,960 + c ~ 21.3 bits+ c.

(7.25)

Single pairs are so common that the space required to record that it was a pair is moret han the space required to record the duplicate card straightforwardly. Accordingly,
t he best approach is to t ake the minimum of t he two methods

K (Hi iC ) ::::; min(log 2 10 + log2 IHI,log 2 2, 598, 960) +c.

(7.26)

Table 7.2 shows the ASC for the various poker hands. Rare hands have highASC, but common hands have low ASC. T his parallels expectations, because with arare hand one might suspect cheating, but with a common hand one will not.

Algorithmic Specified Complexity

144

In other card games, a card is turned over after hands have been dealt todetermine trump . The suit of the card is taken to trump for that round of the game .
If the same suit is repeatedly chosen as trump , someone may ask what the odds arefor that to occur. This question can be difficult to answer because every possible
sequence of trump suits is equally likely. Yet, it is deemed unusual that the same suitis a trump repeatedly. Algorithmic specified complexity allows this to be modeled.
The suits are represented as a bit sequence using two bits for each suit ,K(X) = log 2 4 + log 2 H + c = 2 + log 2 H + c(7.27)

where 4 is the number of suits, and H is the number of hands played. The complexityof the sequence is-lXI-log P(X) = 4-2- = 2H.
(7.28 )The ASC is thenASC(X,p) = 2H- 2 -log 2 H - c.

(7.29)

Note that this equation becomes -c when H = 1. A pattern repeating once is nopattern at all and does not provide specification.

30.------------r----------~,-----------~----------~

25

20

10

5

5

10

15

hands
Figure 7.7: A plot of ASC for getting the same suit repeatedly

20

Examples

145

Figure 7.7 shows the ASC for increasing numbers of hands. The more times
the same suit is chosen as trump, the larger the number of bits of ASC. The same
trump for many rounds becomes less and less probable.

3.4

Folding Proteins

In biology, an important prerequisite to a protein being functional is that it folds. The
fraction of all possible protein sequences that fold has been estimated: "the overall
prevalence of sequences performing a specific function by any domain-sized fold may
be as low as 1 in 10 77 " (Axe, 2004) .
A program can be created which uses the laws of physics to output a particular
foldable protein.

for all proteins of length L
run protein in a phys i cs simulator
if protein folds
add to list of folding proteins
output the Xth protein from the list
Figure 7.8: A pseudocode program which uses a functional
specification to compress the specification of a protein
Given different choices of L and N , this program will output any particularfolding protein. This means that the protein can be described by providing those
two numbers. Thus, the conditional Kolmogorov complexity can be calculated using
these two numbers.
(7.30)
K(X/C) = 2 log 2 L + log2 FL + c
where Cis the context, in this case the law of physics, and FL is the number of folding
proteins of length L . Taking Axe's estimate (Axe, 2004) , and assuming simplisticallythat it applies for all lengths of proteins,(7.31)
log FL = -77log 10 + L log 4(7.32)

therefore

K (X /C ) = 2 log 2 L + log 2 FL + c = 2 log2 L + -77log 10 + L log 4.

(7.33)The probability model will be chosen by supposing that each base along the
DNA chain for the gene encoding the protein is uniformly chosen. It should beemphasized that according to the Darwinian model of evolution, the bases are notA lgorithmic Specifi ed Comp lexity

146

uniformly chosen. T his supposition only serves t o test a simplistic chance model ofprotein origin. T he probability can be calculat ed as(7.34)
Caution should be used in applying this formula . It assumes that the proportion offunctional proteins is applicable for all lengths and implies t hat a fr actional numberof prot eins fold .
Finally calculating the ASC ,AS C (X , p) = L log 4 - 2 log 2 L + 77 log 2 10 - L log 2 4 - c= - 2 log2 L + 77 log 2 10 - c.

(7.35)T he final bound for ASC depends little on t he lengt h of t he protein sequence which
only comes t o play in t he logarit hmic t erm . T he significant t erm is t he 77 log 2 10 ~255 .79 bits. T hus, there is good reason t o believe t hat folding sequences were notgenerated randomly from a uniform distribution .

3.5

Functional Sequence Complexity

Kirk Durst on et al. have defined the idea of fun cti on al sequ en ce complexity (Durst on,
Chiu, Abel, & Trevors, 2007). Functional sequence complexity is related to a special
case of algorithmic specified complexity.
A protein is made from a sequence of amino acids . Some sequences havefunctionality, and some do not . T he case considered in section 3.4 above of folding
is one particular case. Perhaps more interesting is considering t he case of various
proteins which perform useful biological functions.
Let D be the set of all prot eins. Let F be the set of all proteins which pass afunctionality t est . Let f( x ) be a probability distribution over F . Both F and f( x )can be produced by a simple algorithm using a functionality test on each element of
D. Consequently, F and f( x ) can be described using a constant program length.
Consider t he average for ASC over all elements in F .

L f (x )A (x , C,p) = L f( x )( - logp (x) - K (x iC ))= L - f( x ) log p(x )- L f (x )K (x iC ))

xEF

xEF

xEF

(7.36)xEF

Any element x can be described given t he probability distribut ion andlog f( x ) bit s. Given that f( x ) and F can be calculat ed with a const ant program,the conditional Kolmogorov complexity can b e calculat ed as

K (x iC ) :::; log - f( x ) + c.

(7.37)

Obj ections

147

Place this into equation 7.36.

L

f(x)A(x , C,p) 2 L

xEF- f(x) logp(x)- L- f(x) log f(x) -

xEF

xEF

Lc

(7.38)xEF

The middle term is recognized as the Shannon entropy.

Lf(x)A(x , C,p) 2

xEF

L - f(x) logp(x )- H (f)- c L f( x )(7.39)

xEF

xEF

If the distribution p is uniform , p( x) = 1A1,

L f(x)A(x , C,p) 2 log IOI L f(x)- H(f ) - c L f(x) .
2

xEF

xEF

(7.40)xEF

The two summations over F are summations over a probability distribution and therefore 1.
(7.41)L f (x )A (x , C,p) 2 log2 IOI- H (f) - c
xEF

Equation 5 in Durston 's work , adjusting for notation islog 101- H(f ).

(7.42)

T his equation derives from making the same uniformity assumption made above.
Thus, for t he uniform probability distribution case,L (f( x )A (x , C,p)) + c 2 log 101- H(f) .

(7.43)xEF

T his establishes the relationship between ASC and FSC . The difference is that the
ASC is a lower bound and includes a const ant . T his is the same constant as elsewhere:
the length of the program required to describe t he specification.

4

Objections

4 .1

Natural Law

It has been argued in this paper that compressibility in the presence of context is anecessary condition for information. This is in contrast t o others who have argued
that lack of compressibility is a necessary condition for information (Ab el & Trevors,
2005) . But compressible objects lack complexity. Because a compressible object is
describable as some simple pattern, it is amenable to being produced by a simple
process. Many object s in the real world follow simple patterns. Water t ends t ocollect at lower elevations. Beaches follow a sloping pattern. Sparks fly upwards . But

A lgorithmic Specified Complexity

148

these patterns are the result of the operation of simple law-like processes. Even if t he
explanations for these patterns were unknown , the simplicity of the pattern suggeststhat some simple explanation exist ed .
The premise behind this use of compressibility is t hat it identifies what humanwould see as simple patterns. Abel writes: "A sequence is compressible because it
contains redundant order and patterns" (Abel & Trevors, 2005).
The problem is t hat algorithms are very versatile and allow t he descriptionof many patterns beyond that which humans would see as patterns. As has beenshown by the various examples in t his paper, many object s which do not exhibit
what humans typically identify as redundant order and patterns are in fact compressible. Significant ly, funct ionality actually allows compressibility. Contrary to what
Abel st at es, functional sequences are compressible by virtue of the functionality they
exhibit. All of t he sequences that Abel holds to be mostly incompressible are actuallycompressible.
But are compressible object s amenable to explanation by simple processes?
Do all compressible objects lack complexity? If this were t rue, it would be problematic for algorithmic specified complexity because all specified object s would also not
be complex, and no object would ever be both specified and complex. But many
compressible objects do not appear amenable to explanation by a simple process.
As discussed, English text is compressible given a knowledge of t he English
language. T his does not somehow make it probable that English t ext will appear ona beach carved out by waves. Ninety degree angles are very compressible; yet , they
are not typically found in nature. The existence of an explanation from t he laws ofnature does not appear to follow from compressibility.
Kolmogorov complexity deliberately ignores how long a program takes to run.
It is only concerned wit h the length of t he program's description. A program may
be short but t ake an astronomical amount of time t o run. Many of the specifications
considered in this paper fall into that cat egory. These object s are compressible, butthat compression does not give a practical way t o reproduce the object. But if t here
is no practical way t o reproduce the object, t here is no reason to suggest law-likeprocesses as a plausible explanation.

4.2

Context is Subject ive

T he ASC of any object will depend on t he context chosen. Any object can be madeto have high ASC by using a specifically chosen context. But this appears to be theway t hat information works. If t he aut hors, who do not understand Arabic, lookat Arabic t ext, it appears to be no bett er then scribbling. T he problem is not t hat
Arabic lacks information content , but that the reader is unable t o ident ify it withoutt he necessary context . As a result, this subjectivity appears to capture something
about t he way information works in t he human experience.
As with specification, it is important t hat t he context be chosen that is in-Acknowledgements

149

dependent of the object under investigation. While a specification will rarely be
independent of the object under investigation, it is much easier t o maintain t his independence in the case of a context .

4.3

Incalculability

It is not possible to calculate the Kolmogorov complexity of an object . However,
it is possible to upper-bound the Kolmogorov complexity and thus lower-bound thealgorithmic specified complexity. This means that something can be determined to beat least this specified, although the possibility that it is even more specified cannot
be ruled out . T herefore , even though detecting a specification cannot be achieved
mechanically, it can be objectively identified when found.

Acknowledgements
T he approach of using compressibility as a measurement of specification was suggested
to the authors by Eric Holloway. The authors have attempted to extend the approach
to apply to many more types of specifications. T he authors are grateful for his initialsuggestion and answer to our initial objections to the idea.

Winston Ewert
Winston Ewert hails from Canada where he earned a Bachelor's degree in Computer Science from Trinity Western University. He continued his graduate career at Baylor University
where he earned a master's degree and is currently a Ph.D.
candidate. At Baylor he is currently working for t he Evolutionary Informatics Lab, with Robert J. Marks II and William
Dembski, dedicated to understanding t he role of informationin evolution. He has a number of publications in the areasof search , conservation of informat ion, artificial life, swarm
intelligence, and evolutionary modelling.

Robert J. Marks II
Robert J . Marks II is currently the Distinguished Professorof Electrical and Computer Engineering at Baylor University,
Waco, TX. He is a Fellow of both IEEE and the Optical Society of America. He served for 17 years as the Faculty Advisor
with the Campus Crusade for Christ, University of Washington chapter. His consulting activities include Microsoft Corporation , Pacific Gas & Electric, and Boeing Computer Services.
Eleven of his papers have been republished in collections of seminal works. He is
the author of Introduction to Shannon Samp ling and Interpolation Theory (SpringerVerlag) , Handbook of Fourier Analysis and Its Applications (Oxford University Press)
and is a co-author of Neural Smithing (MIT Press). His research has been fundedby organizations such as the National Science Foundation, General Electric, Southern
California Edison, Electric Power Research Institute, the Air Force Office of Scientific
Research , the Office of Naval Research , the Whitaker Foundation, Boeing Defense,
the National Institutes of Health, The Jet Propulsion Laboratory, the Army Research
Office, and the National Aeronautics and Space Administration (NASA) . His ErdosBacon number is five .