Beyond the Turing Test.
The main factor of intelligence is defined as the ability to  comprehend, formalising this ability with the help of new constructs  based on descriptional complexity. The result is a comprehension test,  or C-test, which is exclusively defined in computational terms. Due to  its absolute and non-anthropomorphic character, it is equally applicable  to both humans and non-humans. Moreover, it correlates with classical  psychometric tests, thus establishing the first firm connection between  information theoretical notions and traditional IQ tests. The Turing  Test is compared with the C-test and the combination of the two is  questioned. In consequence, the idea of using the Turing Test as a  practical test of intelligence should be surpassed, and substituted by  computational and factorial tests of different cognitive abilities, a  much more useful approach for artificial intelligence progress and for  many other intriguing questions that present themselves beyond the  Turing Test.
Introduction
iThe original question, 'Can machines think?' I believe to be too meaningless
to deserve discussionj (Turing 1950). Turing's intention was to leave behind
that question and motivate the endeavour for making machines intelligent.
Fifty years of philosophical discussions have shown that his goal has not
been fullled, mainly because the Turing Test (TT) has been usually misunderstood
as a test for intelligence and not simply as an imaginary test of
humanity (Fostel 1993), a philosophical exercise contrived to stop the sterile
debate that the advent of the rst computers were generating.
Turing cannot be reproached for these misunderstandings. The TT iwas
never intended as a test for intelligence, at least not by Turing himself, and
it should not be criticized for failing something that it was not supposed to
doj (Larsson 1993). In fact, there is no better way to state that intelligence
can be reasonably judged by observation than Turing's imitation game, and
that there is no reason to deny the intelligence of non-human beings.
Nonetheless, the overuse of the TT as a referent or even a test of AI
progress has had very negative consequences. AI has striven to imitate
human's behaviour in many tasks, under the slogan iArticial intelligence
is that thing that if made by humans would require intelligencej, which has
promoted the view that ihuman intelligence subsumes machine intelligencej
(Bradford and Wollowski 1995). Finally, the most negative result of the
c
Publishers. Printed in the Netherlands.
Jose Hernandez-Orallo
misinterpretation of the TT jointly with his celebrity is that there has not
been the necessary eoeort for designing new alternative intelligence tests. The
TT has even eclipsed such well-reputed proposals as Simon's early works
on the relation between IQ tests and AI (Simon and Kotovsky 1963), on
some heuristic approaches to solve analogy problems from IQ tests (Evans
1963), Chaitin's suggestion idevelop formal denitions of intelligence and
measures of its various componentsj (Chaitin 1982). Even Johnson's call
iNeeded: A New Test of Intelligencej (Johnson 1992) has been responded
by formalisations of the TT (Bradford and Wollowski 1995), once again.
From a practical point of view, it is vain to revive the little informative
question iCan Machines Think?j (Epstein 1992) which has generated many
words but few clues about how to progress in AI or how to understand
intelligence. As any other discipline, AI requires an eoeective measure of its
major issue, a gradual and detailed measure of intelligence. Concretely, a
scientic measure of intelligence should comply with some requirements:
intelligence is not an absolute attribute. From Darwin's imental
continuityj to infant psychology, there is an unquestionable certainty that
intelligence is a gradual aptitude. Any gradation of the TT as a function of the
time of the test or the score of the judges shows the inappropriateness of the
TT to measure intelligence in a gradual way, i.e., to give a continuous value of
intelligence. The reason is obvious: the TT is a test of humanity (Fostel 1993),
and the idea of being more or less human makes no sense.
intelligence is multi-dimensional. It is quite unbelievable that there is
a concrete ability that would be optimal for every context or world. Nonethe-
less, it is conceivable that a concrete ability would be almost optimal for
most contexts, and intelligence has sometimes been dened as isecond-best
in everythingj. This may justify that a wide context as everyday life, which
includes many other contexts, can distinguish a special kind of ability, the g
factor, the primitive concept found in everyday life.
Maybe the major problem of AI is that its reference
of intelligent behaviour is human intelligence. Recently, AI researchers have
paid attention to other 'intelligences': ants, rats, etc. in order to scale up
the problem. However, the reference or the goal is always human intelligence.
Nowadays the reason is not only pride and anthropocentrism but necessity,
because ithere is not yet a solid denition of intelligence that doesn't depend
on relating it to human intelligencej (McCarthy 1998).
ffl Computationally based : According to the Church-Turing thesis, there is no
reason to think that intelligent systems cannot be implemented in current
computers. The only question is whether they have the necessary speed and
memory for it. I share the opinion that icomputers of years ago were
fast enough if only we knew how to program themj (McCarthy 1998), and
the AI problem is just to discover what makes a program intelligent, or, in
other words, iWhat kind of Information Processing is Intelligence?j (Chan-
drasekaran 1990). Consequently, it is extremely signicant to be able to state
the problem computationally, namely, to give the specication of the problem
Beyond the Turing Test
in computational terms, in order to solve the problem with AI means, which
are exclusively machines and programs.
intelligence is not an ethereal ability. It cannot be dened as
iintelligence is what is measured by intelligence testsj. Intelligence must be
expressed from its original meaning, the ability to comprehend, and this ability
is what should be measured.
Psychometrics has developed measurements of intelligence according to the
rst two requirements. Since Spearman founded the eld (Spearman 1904),
psychometrics has been more and more characterised by the scientic method:
systematic experimentation and statistical rigour. iDespite the many short-comings
of an IQ score, no other measure has been found to be related to
so many other behaviors of theoretical or practical signicancej (Zigler and
Seitz 1982). However, psychometrics has neglected, or failed, to incorporate
the last three requirements, which, in fact, are highly related. Psychometrics
is anthropomorphic by denition since it is the science of measuring
human intelligence. Although there have been adaptations and essays with
chimpanzees, dolphins and other animals, the reference is always the Homo
Sapiens Sapiens. The frequently demanded theoretical foundation of psychometrics
depends on the change of the point of reference, closely connected
to the last three requirements.
On the contrary, Computational Learning Theory is non-anthropomor-
phic and computational. The question iWhat is to learn?j has been assimilated
to the formal notion of identication in the limit (Gold 1967). After
some discouraging results on the learnability of very simple languages, the
complexity of learning has been studied for other paradigms, mainly PAC
learning (Valiant 1984) and Query Learning (Angluin 1988).
However, these theoretical results have not been used to develop rigorous
measurements of learning ability. Contrarily, some contests and comparisons
have been held for practical systems, but as collections of arbitrary examples
extracted from the literature, without many justications of the theoretical
complexity of each of them. The reason is that it is diOEcult to establish the
complexity of an instance, when the results of computational learning theory
apply to classes of concepts, and most results are asymptotical. Actually, the
paradigm of identication in the limit is not applicable for nite instances,
because they can be identied by themselves.
Moreover, the philosophical problem of any measurement of learning ability
is the same as the philosophical problem of prediction: given any nite set
of examples, there are innite many concepts which are consistent with them
and diverge in their predictions. This is exactly the 'subjectivity objection'
of IQ tests: there may be controversy about the correct answer.
In the following we adopt an information-theoretic approach to solve
these problems in order to give a denition and a measure of intelligence
according to the ve prerequisites mentioned above, exclusively based on
4 Jose Hernandez-Orallo
concepts derived from the notion of Turing machine. Despite the title of this
paper, the result is a veritable tribute to Alan Turing on the 50th anniversary
of his celebrated paper.
The paper is organised as follows. The following section introduces the
necessary denitions and tools for the rest of the paper, as well as some
technical diOEculties which are solved in the subsequent sections. In par-
ticular, section 3 formalises the initially vague notion of comprehension in
information-theoretical terms and relates it with the ontology that only intelligent
systems are able to construct. Once settled on a computational setting
for comprehension, Section 4 deals with its measurement by solving the 'sub-
jectivity objection' under the notion of unquestionability, and by ordering
the diOEculty of instances. This allows the construction of a comprehension
test (C-test). Section 5 presents the results of applying it to humans and
compares it with psychometrical tests. The applicability to AI is discussed.
Section 6 studies the measurement of other factors (knowledge applicability,
contextualisation, knowledge construction) under the same conditions that
the C-test has been devised with.
After the previous results and auspices, the TT is re-examined in section
7 and reduced to its original philosophical and even metaphorical character.
Compared with the C-Test, the signicance of the TT is recognised, as well
as the acute deciencies of its misinterpretation and incarnations, like the
Loebner Prize. The nal section concludes with the proposal of a radical
change of paradigm; a science of intelligence that would make it feasible to
answer many new and fascinating questions.
2. Preliminaries and Technical Problems
We choose any nite alphabet \Sigma composed of symbols (if not specied,
f0; 1g). A string or object is any element from \Sigma   , being \Delta the composition
operator, usually omitted or represented by ha; b. The empty string
or empty object is denoted by ". The term l(x) denotes the length or size of
x in bits and log n will always denote the binary logarithm of n. For every
string y, we denote with y n::m , being n  m, the symbols from position n to
position m. For every natural number n,
we denote y 0::m , y n::l(y) , and y k::k+1 , respectively. A string x is a substring
of y ioe there exist two strings z, w such that what is equivalent,
string x is a prex of y ioe
exists a string z such that what is equivalent, being
Given any string x, we denote by x 0::l(x)\Gammad the prex of x
with length d, i.e. the string x without its last d elements.
Under the Church-Turing thesis, any description of any object of reality
can be converted into a description in a universal computational machine
(e.g. a universal Turing machine), so our idea of 'object' is, in this sense,
Beyond the Turing Test
universal. Given a universal descriptional machine OE, and a program p, we
denote by OE(p) the result of executing p on OE. Two descriptions p and p 0 are
extensionally equivalent (denoted It is easy to see
that any description has innite equivalent descriptions.
Denition 1. A k-projectible description for a string x is a program p
on a descriptional mechanism OE such that 9y 2 \Sigma   y, and 9w
known as the prediction of p.
The compression ratio of a program p is given by: CR OE
The compression ratio of an innite projectible description is always innite.
The relative compression ratio of a projectible description p for a nite string
x is dened as CR OE
The complexity of an object can be measured in many ways, one of them
being its degree of randomness (Kolmogorov 1965), which turns out to be
equal to the shortest description of it. Descriptional Complexity, Algorithmic
Complexity or Kolmogorov Complexity was independently introduced
by Solomonooe, Kolmogorov and Chaitin to formalise this idea, and it has
been gradually recognised as a key issue in statistics, computer science, AI,
epistemology and cognitive science (see e.g. Li and Vit#nyi 1997).
Denition 2. The Kolmogorov Complexity of an object x given y on a
descriptional mechanism (or bias) fi is dened as:
where p denotes any iprex-freej fi-program, and OE fi (hp; yi) denotes the
result of executing p using input y.
The complexity of an object x is denoted by K fi It can be
seen elsewhere (e.g. Li and Vit#nyi 1997) that Kolmogorov Complexity is an
absolute and objective criterion of complexity, and it is independent (up to
a constant term) of the descriptional mechanism fi. In other words, there is
an invariance theorem that states that any universal machine can emulate
another. For this reason many properties are proven just in an asymptotic
way and fi is usually omitted. Throughout the paper we will use the relation
as the asymptotical extension of !, namely a there exists an
independent positive constant k such that a k. We will denote x   as
the rst (in lexicographical order) program for x such that
K(x) also represents the idea of simplicity, deeply involved in the philosophy
of inductive reasoning and learning theory. It is not surprising that learning
and recognition were soon re-understood under this context. Solomonooe
1 It is obvious to see that 8x 2 \Sigma   there is always a program of
constant size of the form iprint the inputj. It is also easy to see that 8x 2 \Sigma
because there is always a program of size less than l(x) plus a constant value of the form
iprint xj. In the case that K(x)  l(x) (i.e. l(x   )  l(x)) we say that x is random. It is
obvious that K(xjx   since K(\Deltaj\Delta) is not computable, it is shown elsewhere
(e.g. Li and Vit\Deltaanyi 1997) that the other way is just K(x
6 Jose Hernandez-Orallo
proposed the view of unsupervised learning as information compression (Solo-
monooe 1964) and Watanabe considered ipattern recognition as information
compressionj (Watanabe 1972). The classical Occam's razor of the scien-
tic method: igiven two alternative explanations, choose the simplest onej
was formalised by Rissanen in 1978 under the name iMinimum Description
nally re-formulated in its current one part code
(Rissanen 1996).
According to the MDL principle, given any sequence x, the optimal model
in OE for it is x   . If x   is projectible, i.e. it allows the prediction of the
subsequent symbols of the sequence x, then OE(x   ) n+1 will be the most plausible
prediction according to Occam's razor. In order to ensure that x   is
projectible we need to introduce a projectible variant of K:
Denition 3. The k-Projectible Kolmogorov Complexity of an object
x given y on a descriptional mechanism (or bias) fi is dened as: K 0
any iprex-freej fi-program.
The literature has used Kolmogorov Complexity and not its projectible
variant for prediction due to the following theorem:
Theorem 1. For every string x, K 0
Proof. Every non-projectible program p can be transformed into a projectible
program us denote by c the length
of this extra coding of iand then print 1 foreverj. Hence, there exists a constant
This can be extended to the
denitions of K 0 and K, thus the theorem is proven.
The contrary relationship does not hold. Consider the
string nj. The projectible program iprint the natural
numbers, orderedj has constant size, say l(p On the contrary, the
non-projectible program iprint the rst n natural numbers, orderedj is,
in the general case, not smaller than c
Thus, the ideal MDL principle is represented by the rst (in lexicographical
projectible description for x, denoted by x + , such that
From here, a compression/prediction test based on Chaitin's
proposal (Chaitin 1982) seems to be easily applicable. However, there are
many technical reasons that explain that such an intriguing proposal has
not been addressed yet
1. K(x) is not computable, so x + cannot be eoeectively computed. If a compression
test is constructed, how do we know whether the subject's answer is a hit?
2. There are dioeerent equally alternative plausible descriptions: x + is just the rst
one in lexicographic order of all the shortest descriptions.
At least to the author's knowledge and as Chaitin himself has recognised (Chaitin
1998, personal communication).
Beyond the Turing Test
3. Despite the invariance theorem that states that x + depends on OE only up to
a constant, this constant is relevant if l(x) is small, and there is no reason to
prefer one descriptional system over another.
4. The test intends to measure the ability of compression, but this does not match
exactly 3 with the ability of comprehension, i.e., intelligence.
The rst problem can be solved by incorporating time into the denition of
K. The most appropriate way 4 to weigh space and time of a program, the
log Cost fi (p x ), was introduced by Levin in the
seventies (see e.g. Levin 1973). Then the next variant comes directly:
Denition 4. The Levin's Length-Time Complexity of an object x
given y on a descriptional mechanism fi:
Kt
where LT fi log Cost fi (hp; yi)
This is a very practical alternative of Kolmogorov Complexity, because as
well as avoiding intractable descriptions, it is computable. Moreover, it accounts
better for the idea of simplicity, and Occam's razor should be better
formalised under this variant.
To extend LT-Complexity to projectible descriptions, we must measure
Cost fi (p) in an asymptotical way. Consider a machine OE such that the output
tape cannot be rectied. Cost fi (p)[::n] is dened as the time or machine steps
such that the rst n symbols of the denite output are placed at the beginning
of the output tape and Cost fi
From here we only need LT fi (p x log Cost fi (p x )[n::m] and
log Cost fi (p x )[::n] for the following denition:
Denition 5. The k-Projectible Length-Time Complexity of an object
x given y on a descriptional mechanism fi is dened as: Kt 0
This denition will serve as a start point to face the other three unsolved
problems (2,3,4). In fact, they require rst to distinguish what is to comprehend
(problem 4), which is addressed in the following section, and later on
to solve how to measure it (problems 2 and 3).
3. Formalising Comprehension
To comprehend is to understand either the inner mechanism or the plausible
model of some evidence. In some way, comprehension is stricter than
learning in terms of justication, because comprehension usually entails
3 iI just see how Kolmogorov Complexity and Intelligence could be well related but I
don't think it would be `exactly' so.j (Hofstadter 1997, personal communication).
4 Intuitively, every algorithm must invest some eoeort either in time or demand-
ing/essaying new information, in a relation which approximates the function LT .
8 Jose Hernandez-Orallo
that the subject is able to explain the concept to others. In the case of
innite concepts, this explanation is only possible if the subject has a nite
description of the concept. Consequently, comprehension can be understood
in terms of identication. However, if a concept is nite, like most everyday
concepts, both notions diverge signicantly. A nite concept can be easily
identied by the extensional description of the concept, which has no insight
and surely has not identied any mechanism or pattern from it, if the
evidence ever had one. This question is old in logic, where comprehension
means the connotation of a term, opposed to its denotation or extension.
Hence, an extensional description (by enumeration) has no connotation and
consequently entails no comprehension at all. On the contrary, an intensional
description (by comprehension) may have not discovered the right meaning
or real mechanism of the evidence, but still has a chance of discovering it.
There is a fundamental feature that determines this dioeerence: iThe
Dened Thing CANNOT Appear in the Denitionj, which is known as
Comprehension Requirement. It is also one of the four laws of denition,
according to methodology (Bochenski 1965). It is frequently used as a criterion
by teachers when asking their pupils whether they have comprehended
a concept. In fact, the pioneer of the psychometric approach, Binet, designed
his rst tests to avoid this irote learningj.
Traditional use in mathematics also distinguishes informally an extensional
denition from an intensional denition (or by comprehension). For
innite sets, frequent in mathematics, every denition must be intensional
(or by comprehension). Nonetheless, for nite sets there is still no formal
dioeerence between an intensional description and an extensional one.
At rst sight, Kolmogorov or Descriptional Complexity seems suOEcient
to distinguish extensional descriptions from intensional ones. However, the
MDL principle, which chooses the shortest description for a given concept
x, does not ensure that the description is intensional. In the vast majority
of cases, the data is not compressible, and the MDL principle will give the
data itself, being the most extensional description, which does not give any
hint about the comprehension of that data. Even in the rare cases where
the data is compressible, a short description does not ensure that all the
data is described intensionally; there could be a part that could be highly
compressed and another part that could be quoted as an exception.
The question is then more conspicuous: is there any way to distinguish
pattern from exceptions, program from data?
Koppel introduced the notion of sophistication with the goal of distinguishing
the structural part of an object (Koppel 1988) from its data (or
non-compressible part of it). Logical Depth, as dened by Bennett (Bennett
1988), is shown to be equivalent to sophistication up to a constant (Kop-
pel 1987). Both, however, can 'disguise' a general eoeective interpreter as
ctitious pattern and leave a great amount of real pattern as data.
Beyond the Turing Test 9
It is then required a dioeerent approach to distinguish whether a description
has exceptions (partially or totally extensional) or is composed
exclusively of pattern (it is all structure or totally intensional). The idea is
to compare the part which is used for all the data to the limit (the structure),
with the part which is only used in some portion of the data (the exception).
Denition 6. A description p 0 is (n; k)-equivalent in the limit to a
description p ioe 9n 2 IN; n ? 0 and 9k 2 ZZ such that OE(p 0
Informally, two descriptions are equivalent in the limit if there is a point from
which their predictions always match. If both descriptions are k-projectible
with k nite they are always equivalent in the limit. If only one of both is 1-
projectible then they cannot be equivalent in the limit. Hence, the denition
applies when both descriptions are 1-projectible descriptions.
Denition 7. A description p is a Fully Projectible Description of x
given y ioe hp; yi is an 1-projectible description of x and :9p 0 s.t. hp
hp; yi but (n; k)-equivalent in the limit to hp; yi and LT (p
The rst condition that p 0 is not extensionally equivalent to p (p 0 6j p) is to
avoid that given two or more equivalent descriptions, only the shortest one
would be projectible. The second condition measures that this p 0 is simpler
than p. Note that LT (and only applied to the rst chunk of length l(x)
begin to be equivalent) is used instead of l.
Example 1. Given the evidence i3, 12, 21, 30, 102, 111, 120j, we can consider
several projectible descriptions. For instance,
and 1 foreverj is not fully projectible because there exists a shorter description
i1 foreverj which is equivalent in the limit. In the same way, D
number 3. The following three numbers are obtained by adding 9 to the preceding
one. Continue with number 102. The following numbers are obtained by adding 9 to
the preceding onej is not fully projectible because there exists a shorter description
iStart with number 3. The following numbers are obtained by adding 9 to the
preceding onej which is equivalent in the limit. On the contrary, the description D 3
inumbers whose digits in decimal representation amounts to 3 orderedj is fully
projectible. Similarly, the description D
everj is fully projectible. Finally, the following description is also fully projectible
values of a polynomial polynomial such that
D 4 and D 5 may seem counterintuitive but it should be realised that a fully
projectible description just formalises the idea of explanation (and not yet the
comprehension describes the evidence, it accounts for all of it (there
are no exceptions because it is fully projectible) and it can be related (explained) to
others (because of the use of LT , descriptions which are extremely time consuming
are avoided). Hence, D 4 , whether we like it or not, is an explanation for the evidence.
For the moment, we can dene a new variant of descriptional complexity:
Jose Hernandez-Orallo
Denition 8. The Explanatory Complexity of an object x given y on
a descriptional mechanism fi is dened as:
fully projectible g
The string y, which we have supposed empty in the previous example, represents
the context or previous knowledge where the explanation must be
applied. In the same way it is done with K and the MDL principle, we can
denote with SED(xjy) the Shortest (in LT terms) Explanatory Description
for x given y, i.e. the rst shorstest fully projectible (in lexicographic order)
description for x given y. Logically,
However, we still have that for most strings, SED(x) will be just the
rote description irepeat x foreverj which does not follow the comprehension
requirement. A rst idea to avoid this phenomenon is to force the description
to be shorter than the data and to say that the data has no comprehensive
explanation if this is not the case 5 . However, most of everyday data is not
compressible and it is still comprehended.
Another approach is the idea of reinforcement or cross-validation (Her-
n#ndez-Orallo 1999a). For instance, if we remove the last element of the
previous series, i.e. i3, 12, 21, 30, 102, 111j, it is not much expectable that
4 and D 0
5 would be produced but D 0
3 can still be generated. In general,
Denition 9. Stability. A string x is m-stable on the right in the descriptional
system
In other words, a string x is m-stable on the right if taking m elements from
the right, it still has the same best explanation. These m elements, if given
a posteriori, are considered reinforcement or conrmation, and, if given a
priori, are considered redundancy or hints to help to nd the explanation.
Consequently, although rote learning can be trickily used to make an extensional
description fully projectible, stability (like reinforcement or cross-
validation) is a methodological criterion to avoid this phenomenon. This
nally gives suOEcient characterisation to state that a description entails
that the learner who has generated it has comprehended the data.
There is still another reason to support the previous notion of comprehension
as an ontological principle. Why must we avoid rote learning? Why
must we anticipate? Why do children nd more complex patterns? (Marcus
et al. 1999) Why are we genetically programmed to open any black box we
are presented? This search for more informative hypotheses instead of the
easiest ones may lead to fantasy, but this is not dangerous provided that the
system can interact with the world in order to refute some of them.
This informativeness or investment in the hypotheses was advocated by
Popper for the scientic method, and as we have seen, it is equally applicable
5 A dioeerent approach is the notion of exception, studied and formalised in (Hern\Deltaandez-
Orallo and Minaya-Collado 1998) and (Hern\Deltaandez-Orallo and Garc\Deltaa-Varea 1998).
Beyond the Turing Test
for cognition. Even if we make the very strong assumption of Occam's razor,
i.e., things in nature are not complex unnecessarily, the previous rationale is
justied by the fact that, just as every incompressible string has compressible
substrings, most compressible strings have incompressible substrings,
because the shorter the less worthy that is to compress. If the evidence is
presented incrementally, it is better to invest in more informative or general
hypotheses instead of nding the optimal one for each chunk, which will
nally turn out not to be part of the whole description of the whole evidence.
This rationale leads to the next theorem:
Theorem 2. For every descriptional mechanism fi, there exists a constant
c which depends exclusively on fi such that for every string x of length n
with partition
then SED(y) is not equivalent in the limit with s.
Proof. Consider any string x and
any prex y such that It has a fully projectible description p
iprint y for everj with l(p y being the
space which is required for coding iprint . for everj. Since the computational cost
of p y is linear, say k is suOEcient to choose c  c 0 to ensure that
the description p y is shorter than s, and LT fi (p y
log log l(x). Moreover, p y and s cannot be equivalent in the limit
because s is fully projectible and, by denition, there does not exist a description
with less LT equivalent in the limit.
It is clear that the idea of stability or cross-validation is supported by the previous
theorem. In fact, it is an innate aesthetic preference in the explanations
that human beings generate. Why is it more pleasant the answer 23 to the
series i3,7,11,15,19, .j than the answer 3? In Hofstadter words, iit would
be nice if we could dene intelligence in some other way than ithat which
gets the same meaning out of a sequence of symbols as we dojj (Hofstadter
1979). Theorem 2 simply states why we do in that way.
As a result of this section, stable objects give SED descriptions where
comprehension has taken place, i.e., comprehensive descriptions. The following
section is devoted to ensure that the descriptions would give the same
meaning out of a sequence, and how to measure their complexity.
4. Testing Comprehesion Ability
Theoretically, there are two ways to know whether a system's operation is
compliant with some requirements: by inspecting its code (or program) or by
testing its behaviour. In general, for complex systems, as it has been nally
recognised in software engineering, verication must be experimental, by
means of sets of tests. It is an open and hard problem to devise a complete
specication of intelligence, mainly because it depends on a consensus on
the abilities that an intelligent system must have. However, it is possible to
Jose Hernandez-Orallo
distinguish some abilities that are fundamental for intelligence. A verication
of intelligence behaviour should begin with these fundamental traits, and
gradually add more diverse test cases in order to make the test set more ro-
bust. Comprehending is the most important trait of intelligence, and we have
formalised it in a computational framework. This allows the construction of
exercises for a test which are not selected experimentally but theoretically,
so, nally, we know what is to be measured, quite unlike psychometrics.
However, if we intend to measure comprehensibility there are still two
questions to solve. First, we must design unquestionable exercises, in order
to avoid the 'subjectivity objection' of IQ tests. Secondly, we require an
absolute referent of comprehension diOEculty in order to give a non-Boolean
score independent to the mean ability of the subjects or society who have
made the test before.
Psychometrics has striven to show that it is not absurd to talk about the
'correct' solution. Its rationale is that if the great majority matches with
some solution is because there are not alternative solutions of similar com-
plexity, and, consequently, it is the most plausible. However, this assertion
is made from a very subjective and informal point of view.
Let us make formal and objective this idea. At rst sight it seems that
stability avoids this but, if we restrict to stable descriptions, we can still
modify any explanation p with the addendum iExecute p but print a '1'
every hundred symbols that are printedj which would be comprehensive for
the data but would dioeer from p in the limit, and would be only a little
longer. For this reason, we must introduce the notion of plausibility:
Denition 10. Plausibility. A fully projectible description p for a string
x is (c; m)-plausible on the right in the descriptional system fi ioe 8d; 0  d
Intuitively, a description is (c; m)-plausible if it is at most c bits longer (in LT
terms) then the best explanation for x and this holds even if we remove up
to m elements from the right of x. From here, we can face unquestionability
in the following way:
Denition 11. Unquestionability. A fully projectible description p for x
is (c; m)-unquestionable in the descriptional system fi ioe it is (c; m)-plausible
and there does not exist another (c; m)-plausible description p 0 for x.
This is a more restrictive condition as c and m are greater. In order to still
obtain some unquestionable descriptions we must make the strings larger.
However, as we will see later, if c and m are tuned conveniently for a concrete
descriptional mechanism, the tests can still be composed of short strings x
such that their SED fi (x) is (c; m)-unquestionable. 6
6 This restriction to unquestionable descriptions not only preserves the goal of the test
but even strengthens it, in ontological terms. It has been frequently argued in philosophy of
Beyond the Turing Test
Once we are able to obtain strings whose SED fi is (c; m)-unquestionable,
we should ascertain the diOEculty of each problem, in order to be able to give
a test set of exercises of dioeerent comprehensibility. The idea is to relate
this diOEculty with explanatory complexity (Et) and the explicitness of the
description wrt. the data:
Denition 12. A string x is k-incomprehensible given y, denoted by
incomp(xjy), in a descriptional system fi ioe k is the least positive integer
number such that: Et fi (xjy) \Delta G(SED(xjy)jhx; yi)  k \Delta log l(x).
The use of the factor logl(x) is to compensate the fact that x must be printed
and, therefore, for all x Et(x)  log l(x). Consequently, for all x; k  1.
As an example, consider a string x of length 256, with 50. The
comprehensibility of x is k= 7.
The function G corrects the degree of explicitness of the description wrt.
the data and it is dened as follows (Hern#ndez-Orallo 1999b):
Denition 13. The information gain of an object x wrt. an object y in
a descriptional system fi is given by: G fi
Denition 12 nally measures the real diOEculty of nding SED(x) from x,
because descriptions of the form irepeat x for everj which have Et high (to
quote x) are corrected by G, but the length of x is still important.
Now we are prepared to construct a generic test of the ability of comprehension
by generating a series of strings of gradual comprehensibility.
However, as we have said, it is important that the answer is unquestionable,
because if not, the answer would be an arbitrary choice from the examiner. A
way is to provide redundant information to make the answer unquestionable,
with some limitations, obviously, because if not, the problems would be much
too long. For instance, given the series ia, c, c, a, c, c, c, a, c, c, c, c, a, .j
it seems logical to expect that it would follow ic, c, c, c, c, a, c, .j, so it is
redundant to present more than the necessary symbols.
The measurement that is to be presented below requires the collaboration
of the subject, which must employ all its resources to perform the test. It is
not necessary that the subject understands the aim of the test but at least
it should be programmed to do it.
We can nally obtain the degree of intelligence of a given system as the
value which results from applying the following test:
Denition 14. C-Test. Let us select a descriptional system fi suOEciently
expressive and impartial, composed of an alphabet of
symbols\Omega fi and a set of
science and induction that the plausibility and unquestionability of a theory or explanation
not only depends on the intrinsic characteristics of the explanation but also on the ability of
nding alternative explanations. In this sense we can see intelligence as the most important
means to augment the plausibility and condence of explanations, and, consequently, the
ontology of an 'intelligent' system.
14 Jose Hernandez-Orallo
operations \Theta fi to manipulate these symbols, and their corresponding cost (or
length). We provide (or programme) to S the alphabet, operations and cost.
Depending on the expected intelligence of a system we select a suOEciently
wide range 1::K of diOEculty. For each choose randomly p
sequences x k;p , being k-incomprehensible, c-plausible, (c,m)-unquestionable
and d-stable with d  r, r being the number of redundant symbols (or hints)
of each exercise. The questions are the K \Delta p sequences without their
elements
\Gamma(d+r)
We give them to S and we ask for the following element
according to the best explanation that is able to construct
with\Omega fi and \Theta fi .
We leave S a xed time t and we record its answers: guess(S; x k
\Gammad+r+1 ). The
result of this test of comprehensibility or (C-test) is measured as:
\Gammad+r+1
the function hit is usually measured as hit(a;
(negative values can be used to penalise errors). The value e is simply for
weighting the diOEcult questions means that all have the same value).
In an informal way, ithe test measures the ability of nding the best explanation
for sequences of increasing comprehensibility in a xed timej. 7
5. Measurement of Pretended Intelligent Systems
The preceding test is applicable to any system whose degree of intelligence
is questioned. Selecting appropriately the descriptional system and the rest
of parameters of the test, it can be used for humans, animals, computers,
extraterrestrial beings and any collection of the preceding working jointly.
Although Denition 14 evaluates a single ability, there are still many ways
to realise a specic test. In (Hern#ndez-Orallo and Minaya-Collado 1998) the
test was implemented by using an abstract machine quite similar to a state
machine. From here, a variety of strings of dioeerent comprehensibility in that
machine were generated. Although the set of k-potent numbers of length at
most n can be computed in polynomial time in n (see a proof in (Li and
Vit#nyi 1997)), the cost of O(n k ), forces to use some heuristics for this. In
the same way, G was approximated. Finally, a sieve was applied for obtaining
only c-plausible, (c,m)-unquestionable and d-stable sequences.
The same work presents the results of applying the test to subjects
from species Homo Sapiens Sapiens aged between 14 and jointly
7 One relevant feature of the test is that, although the subject is supposed to be a
particular universal descriptional system OE s
with a particular background knowledge (life
experience) Bs , it is given a descriptional system fi over it, which highly minimises the
inAEuence of the dioeerence between the computations performed by OE s and other subject
i.e. the dioeerence between Ets(xjhBs ; fii) and Et t (xjhB t ; fii). This makes it possible for
the notions of plausibility and unquestionability to be similar for both subjects.
Beyond the Turing Test
with a classic test of intelligence, the European IQ Test. The correlation between
both tests was 0.77. This value only justies a further more exhaustive
study over greater groups and several variations derived from Denition 14.
Another remarkable experimental result shown in Fig. 1 is that the relation
between hit ratio and k-uncomprehensibility is straight, which suggests that
comprehensibility really estimates the diOEculty of each string.

Figure

Hit
s
@
l
Logically, it is not expectable (for the moment) that contrasted and widely
used IQ tests would be substituted by these C-tests. Nonetheless, this could
be a startpoint towards a theoretical foundation of psychometrics free from
the Homo Sapiens as a reference.
However, it is not human intelligence but non-human what is urgent to
be measured. A formal declaration of what is expected from an intelligent
system should allow two important things: to derive more intelligent systems
from a more concrete specication and, secondly, to evaluate them. Denition
14 provides a rst step for both things, a detailed scale for measuring the
progress (in one intelligence factor) of generic systems in AI. As any other
eld of science, a great advance in a discipline happens when one of its topics
can be measured in an eoeective and justied way. AI, as a science, requires
measurements of intelligence and its dioeerent factors.
Modern AI systems are much more functional than systems from the
sixties or the seventies. They solve problems in an automated way that
before required human intervention. However, these complex problems are
solved because a methodical solution is found by the system's designers, not
because current systems are more intelligent than preceding ones. We share
the opinion that iit is time to begin to distinguish between general, intelligent
programs and the special performance systemsj (Nilsson 1995).
This initial aim of being more general is nowadays still represented by
two subelds of AI: automated reasoning and machine learning. Automated
theorem provers are able to solve complex problems from dioeerent elds of
mathematics. The great advance of the last two decades is mainly caused
by the existence of sets of problems to compare dioeerent systems. Even
these sets have evolved and grown to huge and complete libraries of theorem
proving problems, like TPTP (Suttner and Sutclioee 1996). Machine learning
Jose Hernandez-Orallo
is also taking a more experimental character and dioeerent systems (from
dioeerent paradigms) are evaluated according to classical problems in the
literature. However, as we said in the introduction, there is no theoretical
(nor empirical) measurement about the complexity of the problems which
compose these test sets. This complexity could be obtained by adapting
comprehensibility to several representational languages.
6. Factorisation
During this century, psychometrics have striven for dioeerentiating between
background knowledge (either evolutionary-acquired or life-acquired) and
'liquid intelligence' (or individual adaptability). Accordingly, exercises from
IQ tests are strictly selected to avoid the inAEuence of background knowledge
to be foolproof to 'idiots savants'. However, there are many knowledge-
independent abilities (or factors) to measure. Some factors usually found
in psychological tests are 'verbal ability', `visual ability', 'calculation / deductive
ability', etc.
The C-test measures one factor, which could empirically be identied
with the g factor or liquid intelligence. There are more independent factors
which could be measured by using extensions of the framework presented in
the previous section. For instance, knowledge applicability, contextualisation
and knowledge construction ability can be measured in the following way:
Knowledge Applicability (or 'crystallized intelligence'): we provide a background
knowledge B and we give a set of sequences x i such that incomp(x i
are unquestionable with
or without B. We can compare the dioeerence of performance between cases
with B and without B. This test would actually measure the application of
the background knowledge depending on two parameters: the complexity of B
(i.e. Kt(B)) and the necessity or usefulness of B, measured by u.
Contextualisation: it is measured in a similar way as knowledge applicability
but providing dioeerent contexts dioeerent sequences
x i;t such that incomp(x i;t jB t This multiplicity of background
knowledge (a new parameter T ) dioeerentiates this factor from the
previous one. Analogy tests generally resemble this type of exercises, as it
was shown in (Hern#ndez-Orallo and Minaya-Collado 1998) where a denition
(and measurement) of analogy was discussed.
Knowledge Construction: we provide a set of sequences x i such that exists a
common knowledge or context B and a constant u such that for incomp(x i jB)
signicant increase of performance must take place between
the rst sequence and the later sequences. The parameters are the same as
the rst case, the complexity of B and the constant u. This learning from
precedents has also been studied in AI (see e.g. Winston 1982).
Knowledge Applicability may also be correlated with deductive abilities and
these may also correlate with the idea of congruence or coherence, since
Beyond the Turing Test
it can be measured as constraint satisfaction (Thagard 1989). Other factors
are more related with intentionality than intensionality and general
intelligence. These are reactivity, pro-activity, interactivity and the recently
elsewhere vindicated emotional abilities, that can be measured adopting
notions from Query Learning paradigms (Angluin 1988), possibly formalised
using interactive Turing machines.
However, not every factor is meaningful for intelligence. Factors like iplay-
ing chess wellj are much too specic to be robust to background knowledge.
Other factors will result in being highly correlated (experimentally or the-
oretically) to other more distinct factors. The inAEuence of the descriptional
mechanism should also be studied for each factor.
In the end, the matter at issue is to rene and extend all the previous
ideas in order to make dioeerent and founded tests of intelligence, knowing
exactly what is measured. This is an urgent and fascinating task for AI.
7. The C-test and The Turing Test
The imitation game was conceived by Turing to dissipate the doubts about
possibly non-human intelligent beings. He left no place for human's ex-
clusivity: intelligence can be evaluated by an exclusively behavioural test.
Unfortunately, instead of recognising this his most important contribution,
the test is still understood as 'a goal' in AI. Nonetheless, this view has been
responded by many authors, which criticise that the TT does provide little
information about what intelligence is; it is just a test of humanity (Fostel
1993), that, in fact, if applied to human beings, yields many paradoxes. The
result of applying it to ourselves is a recursive trap which is unable to answer
the question of how intelligent the Homo Sapiens is.
There have been unsuccessful attempts to correct the two main problems
of the Turing Test for measuring intelligence: its informal character and its
anthropocentrism. 8 There is still a third problem, which is the necessity of
several intelligent 'judges' and a `referent' to make the test. The self-reference
question arises again: Who is the rst intelligent being to start the game?
These and other problems are incarnated in the Loebner Prize, which usually
awards the participant who has devised the system more able to cheat the
judge, because ihumans are surprisingly bad at distinguishing humans from
computersj (Johnson 1992). Furthermore, there is no way of knowing who
is cheating, the system or its designer.
However, if fairly played, the imitation game is a hard examination for
any pretended intelligent system. It is extremely diOEcult to behave like an
In some cases, this has led to disparate proposals, as the so-called formalisation of the
TT (Bradford and Wollowski 1995), sustained from the assumption that we are able to
solve NP-complete problems in polynomial time. As (McCarthy 1998) claries: ihumans
often solve problems in NP-complete domains in times much shorter than is guaranteed by
the general algorithms, but can't solve them quickly in generalj.
Jose Hernandez-Orallo
average human being of this epoch (it is even diOEcult for some average
human beings). For a non-human-contextualised being, it would be required
to comprehend the complex behaviour of human beings of these times, their
evolution-acquired traits, their language, their culture, their limitations, etc.
It is much easier then to try to cheat the judges. In fact, the judges iare
especially fooled into reading structure into chaos, reading meaning into non-
sense.) Sensitivity to subtle patterns in our environment is extremely
important to our ability to perceive, learn and communicatej (Shieber 1994).
Curiously, it is precisely this 'lack' of the judges what the C-tests measure.
However, the C-tests, as they have been presented, are necessary (at least to
obtain a minimum value of I(S)) but not suOEcient (other important factors
should be measured as well). It has been already suggested that both kind of
tests (TT and factorial) could be combined in order to give a more accurate
test of intelligence: iit is this posing of puzzles in arbitrary domains that
is the hardest part of the Turing Test, and a part that no program has yet
passedj (Shapiro 1992). This idea, however, would ultimately turn the TT
into a lightweight and less rigorous version of a factorial C-Test.
In our opinion, the TT should be celebrated as an extremely valuable
philosophical exercise about the behavioural character of intelligence. How-
ever, in practice, it should be substituted by progressively more accurate
computational tests of dioeerent cognitive abilities.
8. Conclusions
Turing devised a way for identifying intelligent beings from non-intelligent
ones without solving the problem of what intelligence is. In fact, an imitation
game is the only way to make sense from such an apparent paradox. However,
the approach has shown numerous limitations and troubles which make it
useless for AI in practice. With current theoretical and technical tools of
computer science, it is diOEcult to develop non-human intelligence without a
computational formalisation of the problem we are trying to solve.
It is high time to address the fundamental problem: what intelligence is.
This paper presents an important step in this line. A formalisation of one of
the main factors of intelligence, the g factor or liquid intelligence is dened
computationally. This denition has been used to develop an intelligence test,
very dioeerent from the TT and in compliance with classical IQ tests. Like
the latter it distinguishes acquired knowledge from liquid intelligence. More
importantly, the C-Test, unlike the TT and IQ tests, is not anthropomorphic.
The factor is dened as the ability of nding comprehensive explanations,
and thus is meaningful. This makes it philosophically acceptable: intelligence
is what allows us to comprehend the world.
Sooner or later we will need to face the fact that computers will be
closer and closer to human intelligence. Once arrived to this hallmark of
Beyond the Turing Test 19
AI, the misunderstood goal of the TT, it will be indispensable to have an
objective measure of intelligence, in order to solve the incipient technical and
ethical problems that could be derived from here. The paradigm presented
in this paper, since it is theoretically justied, allows the projection of the
measurement of intelligence beyond human intelligence.
There are many more interesting questions beyond the TT. How many
independent computational factors does human intelligence have? How intelligent
does the Homo Sapiens result in the end? Which main factors make a
chimpanzee signicantly dioeerent from us? How intelligent might machines
be with the current computational power? Psychometrics, Anthropology,
Zoology and AI have only partially dealt with some of these problems.
All these questions require new theoretical tools for a radical change of
paradigm: a science of intelligence grounded in theoretical computer science
and information theory.
To construct this science, Turing's call is now more compelling then ever:
iWe can only see a short distance ahead, but we can see plenty there that
needs to be donej.

Acknowledgements

I am much obliged to the main inspirers of this work, G. Chaitin and D. Hofstadter, for
their encouraging comments, especially during 1997, when the main ideas were taking
shape. Since then, the work has matured with the help of numerous collaborations and
suggestions: R. Beneyto and J.M. Lorente from the Dep. of Logic and Phil. of Science of
the U. of Valencia, P. Thagard from the Dep. of Phil. of the U. of Waterloo, O. Pellicer
from the Dep. of Psychobiology of the U. of Valencia and N.T. Crook from the Oxford
Brookes U. Finally, I am especially grateful for the comments from K. Araque, R. Barreiro,
E. Fueyo, I. Garc#a, E. Hern#ndez, N. Minaya and I. Soto on several drafts of this paper.



--R

Machine Learning
The Economist
Logical depth and physical complexity.
The Methods of Contemporary Thought.
A Formalization of the Turing Test (The Turing Test as an Interactive Proof System).

What kind of Information Processing is Intelligence?
Programs in the Search for Intelligent Machines: The Mistaken Foundations of AI.
Can Machines Think?
A Heuristic Program to Solve Geometric Analogy Problems.
The Structure and Measurement of Intelligence.

Language Identication in the Limit.
The inference to the best explanation.
The Turing Test Is Not a Trick: Turing Indistinguishability Is A Scientic Criterion.
The universal Turing machine: a half-century survey




of Intelligent Systems (EIS'98)

A New Test of Intelligence.



In (Herken
The Turing Test Misunderstood.
Universal search problems.



Machines and Thought.

Knowns and Unknowns.
Eye on the Prize.

Fisher information and stochastic complexity.
What is AI
The Turing Test and The Economist.
Lessons from a Restricted Turing Test.
Human acquisition of concepts for sequential patterns.
A formal theory of inductive inference.
'General Intelligence' objectively determined and measured.

Beyond Information.
The TPTP Problem Library.
On computable numbers with an application to the Entscheidungsproblem.

Computing Machinery and Intelligence.
A theory of the learnable.
Pattern Recognition as Information Compression.
Thinking Machines: Can There Be?
Learning New Principles from Precedents and Exercises.
Thinking Machines: Can There Be?

--TR

--CTR
Shane Legg , Marcus Hutter, Universal Intelligence: A Definition of Machine Intelligence, Minds and Machines, v.17 n.4, p.391-444, December  2007
comprehension;measurement of intelligence;descriptional complexity;AI's anthropomorphism;inductive Inference;turing test;psychometrics