Turing's (1950) article on the Turing test is often interpreted as supporting the behaviouristic view that human intelligence can be represented in terms of input/output functions, and thus emulated by a machine. We show that the properties of functions are not decidable in practice by the behaviour they exhibit, a result, we argue, of which Turing was likely aware. Given that the concept of a function is strictly a Platonic ideal, the question of whether or not the mind is a program is a pointless one, because it has no demonstrable implications. Instead, the interesting question is what intelligence means in practice. We suggest that Turing was introducing the novel idea that intelligence can be reliably evidenced in practice by finite interactions. In other words, although intelligence is not decidable in practice, it is testable in practice. We explore the connections between Turing's idea of testability and subsequent developments in computational complexity theory.
The Turing test
We will show that, in fact, the properties of functions
cannot be decided in practice by the behaviour they exhibit.
Hence, the observation that all physical actions are
computable is a useless one. Physical action is finite, meaning
that any such action will always have the potential of
having been produced by trivial mechanical means. This
article could, in principle, have been written by chance by an
algorithm selecting random characters. It’s possible.
Alternatively, you could chat for an hour with somebody over
video link and only later find out that what you thought was
a live link was nothing more than a historical recording
being played back. The scenario is unlikely, yet it remains a
possible explanation for any observation of finite behaviour.
According to
We suggest that Turing’s idea was not about machines
emulating intelligence, but about the possibility of intelligence
being evidenced in practice. His point was that, although
intelligence is a Platonic ideal (i.e. cannot be decided in
practice), it is somehow manifested in finite objects, meaning that
finite tests can detect it with high confidence.
The first argument we will make is that, as regards the mind-program debate, Turing supported the mathematical objection and held the intuitive view that the mind could not be a program.
The second argument we will make is that
“There are a number of results of mathematical logic which can be used to show that there are limitations to the powers of discrete-state machines...The short answer to this argument is that although it is established that there are limitations to the powers of any particular machine, it has only been stated, without any sort of proof, that no such limitations apply to the human intellect.”
One requirement for Lucas’s argument to succeed is that
human minds are consistent, the explicit assertion of which
would seem to be ruled out by Go¨del’s second incompleteness
theorem.
Another assumption in Penrose’s (1994) use of Turing’s
theorem is that Church and Turing’s conception of effective
method (i.e. computation) is genuinely universal. This
assumption, known as the Church-Turing thesis, does not
appear to be something that can be proved in the traditional
sense. Nevertheless, Church considered his description of
computation as a definition, and even Turing was convinced
of its veracity. According to
As one of the founders of the discipline of computer science, Turing was in a good position to evaluate the mindprogram debate. Although he notes in 1950 that assertions of the mind’s superiority are “without any sort of proof”, adherence to the mathematical objection is a consistent theme of his writings. In his 1938 PhD thesis, carried out under the supervision of Church, Turing makes clear that the mind has an intuitive power for performing uncomputable steps beyond the scope of a Turing machine:
“Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two faculties, which we may call intuition and ingenuity. The activity of the intuition consists in making spontaneous judgments which are not the result of conscious trains of reasoning...In consequence of the impossibility of finding a formal logic which wholly eliminates the necessity of using intuition, we naturally turn to non-constructive systems of logic with which not all the steps in a proof are mechanical, some being intuitive.”
After the Second World War, Turing’s view on the role of intuition in reasoning appears unchanged. In a 1948 report to the National Physical Laboratory, Turing again clarifies that mathematicians’ ability to decide the truth of certain theorems appears to transcend the methods available to any Turing machine:
“Recently the theorem of Go¨del and related results...have shown that if one tries to use machines for such purposes as determining the truth or falsity of mathematical theorems and one is not willing to tolerate an occasional wrong result, then any given machine will in some cases be unable to give an answer at all. On the other hand the human intelligence seems to be able to find methods of ever-increasing power for dealing with such problems, ‘transcending’ the methods available to machines”.
In his last article published before his death in 1954, Turing again emphasises the role of intuition beyond effective method. He argues that Go¨del’s theorem shows that ‘common sense’ is needed in interpreting axioms, something a Turing machine can never demonstrate:
“The results which have been described in this article are mainly of a negative character, setting certain bounds to what we can hope to achieve purely by reasoning. These and some other results of mathematical logic may be regarded as going some way towards a demonstration, within mathematics itself, of the inadequacy of ‘reason’ unsupported by common sense.”
Turing’s writings reveal him to be a consistent proponent of the mathematical objection. Nevertheless, it was not something he ever attempted to prove. Instead, in 1950 he made a surprising statement: “I do not think too much importance should be attached to it”.
As we will show, the question of whether the mind is a
program is unrelated to the question of whether physical
machines can demonstrate intelligent behaviour. A problem with
the associated philosophical debate is that it confuses Platonic
ideals, such as ‘function’ and ‘program’, with concepts that
can be manifested in practice through finite means, such as
mechanical machines. For example,
To be clear, when
In his 1950 article, Turing is referring, not to Turing machines, but to finite physical machines. He is wondering about the practical implications of the Platonic theory of computation. For example, can the mathematical objection be demonstrated to have any observable practical implications?
Below, we provide a modification of the use theorem (see
Oddifreddi, 1992) to show that no finite set of interactions
is sufficient for checking the behaviour of a black-box
system: properties of functions cannot be decided in practice.
No matter how many questions we are allowed to ask, it is
not possible to deduce that the black-box system is capable
of solving a given problem. As stated informally by
More formally, let O be an observer, A a set of strings, and f : S ! f0; 1g be a Boolean function. O can adaptively ask finitely many queries f (x) =? (O has access to A), after which O decides whether f computes the set A, i.e. f (x) = A(x) for every x. The following standard argument shows every observer is wrong on some function.
Formal argument For any observer O, and any set A, there is a function f : S ! f0; 1g such that O is wrong on f . Proof. Let O be as above, A be a set. If O rejects all functions (i.e. thinks all functions do not compute A) then O is wrong on f , where f (x) = A(x) for every x. So let g be accepted by O. O queries g on finitely many strings x1; x2; : : : ; xn. On all the strings x1; x2; : : : ; xn, g is equal to A, otherwise O is wrong about g. Choose y different from x1; x2; : : : ; xn, and construct f : S ! f0; 1g, by letting g(x) = f (x) for all x 6= y, and f (y) = 1 A(y). f does not compute A, because f is different from A on input y. Because f equals g on inputs x1; x2; : : : ; xn (the ones queried by O), O will make the same decision about f than about g, i.e. O decides that f can compute A. By construction of f , O is wrong.
In summary, not only is a Turing-style test not capable of deciding intelligence, a finite sequence of input/output is not even sufficient for deciding the program that computed it. Accordingly, we can see that, while Searle’s (1980) Chinese room argument presents a valid observation of the limitations of Turing-style tests for deciding the origins of strings, it cannot possibly say anything about the mind-program debate. The separation, or lack of, between minds and programs has no practical implications that could be exposed by a Chinese room scenario.
Because our argument uses a similar diagonal proof to
Turing’s (1936) theorem, it seems likely that he was aware of the
general idea. If the properties of functions cannot be decided
in practice, it is clear that the relevant real-world question is
not about establishing once and for all whether the mind is a
program, but about what intelligence means in practice. This
is the issue that, we believe,
Turing seeks merely to establish the possibility of
“satisfactory performance” at the imitation game over a finite
period; not perfect performance, nor the idea that satisfactory
performance is a reliable indicator of subsequent perfect
performance. He never goes beyond claims for the finite
simulation of intelligence: “My contention is that machines can be
constructed which will simulate the behaviour of the human
mind very closely”
One source of misunderstanding is that Searle and Turing use different meanings for the word ‘thinking’. For Searle, a machine can be described as thinking when it is capable of emulating human performance. For Turing, a machine can be described as thinking when it successfully simulates a finite set of human performance. While Searle treats ‘thinking’ as a Platonic ideal, Turing identifies that, in practice, there can be nothing to thinking beyond acting indistinguishably from the way a thinker acts.
Whereas Turing’s 1936 article established the Platonic concept of computation, his 1950 paper investigates the practical implications of this concept. There are two components to his conjecture. The first is that the mathematical objection (i.e. a possible separation between programs and minds) has no implications in the finite, physical world. The second is that intelligence does have certain practical implications, which are somehow testable.
Dealing with the first component,
“This...raises the question ‘Can a machine play chess?’ It could fairly easily be made to play a rather bad game. It would be bad because chess requires intelligence. We stated... that the machine should be treated as entirely without intelligence. There are indications however that it is possible to make the machine display intelligence at the risk of its making occasional serious mistakes. By following up this aspect the machine could probably be made to play very good chess.”
Rather than dismissing the mathematical objection,
“There would be no question of triumphing simultaneously over all machines. In short, then, there might be men cleverer than any given machine, but then again there might be other machines cleverer again, and so on.”
At first blush, this withdrawal of the mathematical objection appears to eliminate the possibility of evidencing intelligence in practice. For instance, if stupid machines can simulate any finite set of behaviour, and pass any test, then it can be argued that behaviour alone is never sufficient for establishing intelligence. Nothing we can do in the real world, no behaviour we can perform, can offer conclusive evidence of non-trivial origin. Could it be that intelligence is useless?
This is exactly the attitude adopted by Professor Jefferson
in his 1949 Lister Oration, whom
Here, Jefferson is arguing that finite behaviour alone is not sufficient for establishing intelligence. Instead, we must ‘know’ what strings mean and ‘feel’ emotions. Because such properties can never be represented symbolically, there is no possibility of any system, human or otherwise, evidencing its intelligence in practice. But this doesn’t seem right. Intuitively, our intelligence is something useful. It lets us achieve things in the real world that less intelligent systems cannot. The big question is whether there is there any reliable test that can somehow validate this intuition regarding the practical utility of intelligence.
What
Indeed, all the communication we have ever had with
other human beings can be summarized as a finite string of
symbols. If intelligence could not be evidenced in practice
through finite interactions, it would preclude humans from
identifying each other as intelligent, reducing us to solipsists.
According to
It seems that in order for the concept of intelligence to be
meaningful, there must be some practical means of
identifying and engaging with intelligent systems in the real world.
Having realised this,
Professor Jefferson does not wish to adopt the extreme and solipsist point of view. Probably he would be quite willing to accept the imitation game as a test.”
Some have interpreted
Let us consider the question of “what is a test”? A test is of finite duration. Applying it to an object yields results that enable inferences to be drawn about that object. Somehow, the results hold significance for other aspects of the object, beyond those which have been directly tested. One could say that the test succeeds in succinctly ‘characterising’ the object through a finite set of responses.
For example, students are asked to sit tests to reveal how much they know about a particular subject. Because of the short duration, it is not possible to ask them every question that could possibly be asked. Instead, questions are chosen cleverly so that responses can be relied on to draw inferences about students’ ability to answer all the other potential questions which haven’t been asked.
Of course, a particular student might get lucky on a test. They might fortuitously have learned off the answers to the exact questions which came up, but no others. Thus, as we have already shown, a test can never decide whether a student understands a subject. What a cleverly crafted test can do is offer a very high level of confidence that the student would have answered other questions correctly.
What are the properties of a good test that would lead us to have such confidence? In short, a good test is one for which there is no easy strategy for passing it, other than full mastery of the subject. For a start, there should be no way for the student to get a copy of the test in advance, or predict what will be on it so that they can just learn off the relevant responses. In addition, the test should be well diversified, bringing together material from many different areas of the subject. For instance, the answers should draw on different aspects of understanding and not betray a simple pattern which allow them to all be derived using the same technique. Furthermore, to be as hard to compute as possible, successive answers should be integrated with each other, rather than addressing totally separate chunks of knowledge.
The next question is whether testing for a property can continue to yield dividends in terms of raising confidence closer to certainty. For example, it seems intuitive that a short twohour test can provide a clear picture of a student’s ability in a subject. But what if we extended the length of the test to three hours? Can a test be designed such that it continues to build confidence continually higher? Is it conceivable that there are some properties, such as intelligence, that would support continuous testing of this nature to any level of confidence? Such a mechanism could ‘bridge’ the gap between the Platonic and physical worlds and render the concept of intelligence meaningful in practice. We propose that this is the fundamental premise underlying Turing’s (1950) conjecture.
An important implication of Turing’s testability is that it paves the way for machines to display intelligent behaviour. Tests are finite. The ability to pass hard tests can therefore be encoded in finite machines, which are themselves hard to construct and hard to understand, yet still feasible in practice.
In a BBC radio debate in 1952, Turing connects the idea of ‘thinking’ with this capacity to do things which are reliably difficult. Even when the mechanics of a machine are exposed, it can still retain the ability to do ‘interesting things’, which are not rendered trivial by the overt mechanisation. In other words, explicitly finite objects can still pass hard tests: “As soon as one can see the cause and effect working themselves out in the brain, one regards it as not being thinking, but a sort of unimaginative donkey-work. From this point of view one might be tempted to define thinking as consisting of ‘those mental processes that we don’t understand’. If this is right then to make a thinking machine is to make one which does interesting things without our really understanding quite how it is done.”
When Jefferson confuses this concept of hardness with the difficulty of identifying the implementation, Turing immediately corrects him:
“No, that isn’t at all what I mean. We know the wiring of our machine, but it already happens there in a limited sort of way. Sometimes a computing machine does do something rather weird that we hadn’t expected. In principle one could have predicted it, but in practice it’s usually too much trouble. Obviously if one were to predict everything a computer was going to do one might just as well do without it.”
What
What this implies is that hard tests may actually be hard to find. When we put forward what appears to be a challenging test for AI, such as chess, we cannot know for sure how hard it is. As soon as a machine succeeds in defeating the test, the associated limitations become apparent. At that point we go back to the drawing board to develop a harder test. Yet the process never ends. In the same way that it is not possible to decide intelligence, it is not possible to decide the reliability of a test for intelligence. Tests must themselves be tested.
This explains why
In 1956 Go¨del wrote a letter to the dying von Neumann,
echoing Turing’s remarks on a potential gap between the
Platonic theory of computation and its practical
implications. In the letter Go¨del identified a finite analogue of
the Entscheidungsproblem which
These novel ideas that Turing and Go¨del struggled to express have since developed into a field known as computational complexity theory. This discipline now provides a framework that can be used to formally define concepts such as ‘smart questions’ and ‘high confidence’, which are integral to the Turing test. Smart questions are, for example, those that involve solving instances of an NP-hard problem (e.g. computing a Hamiltonian path or a subset-sum solution).
In 1950 Turing didn’t have the formal tools needed to
express these ideas, he was relying on his intuition. What is
interesting is that many of the key questions in computational
complexity theory, such as that raised by Go¨del in 1956,
continue to lie unresolved. For example, it not yet known if there
are problems whose solutions can be easily verified, yet are
hard to compute. Do smart questions really exist? Can hard
tests be created that engender high confidence from finite
responses? This is known as the P versus NP problem, which
remains the biggest unsolved problem in computer science
today. While computational complexity theory has succeeded
in formalising the key components in Turing’s conjecture,
which concern the interaction between the Platonic and
practical domains, it has not yet succeeded in answering the
difficult questions that ensue.
Interpretations of Turing’s (1950) work have focused strongly
on the idea of running the test. The article has often been
interpreted either as being supportive of functionalism
In this article we have argued that
Philosophers such as
Because it was not possible for Turing in 1950 to present
his conjecture mathematically, he instead chose to publish
these ideas as a philosophical article in the journal Mind. An
unfortunate outcome of this choice is that Turing’s (1950)
article seems whimsical. Reading it quickly, one might almost
imagine that Turing was playing the gender-based imitation
game at a party and stumbled by chance upon the idea of
using it as a test for intelligence.
Turing’s trite presentation betrays the sophisticated theory
behind the concept. From his extended writings we can see
that he was concerned with, not the idea of a psychological
standard for AI, but the more general concept of how
intelligence can be evidenced in practice. In particular,
In conclusion, we have proposed that the Turing test does not aim to decide a yes/no answer to the question of whether or not a system is intelligent. It does not address, and was never intended to address, the question of whether the mind is a program. The Turing test is the observation that finite interactions can result in very high confidence in a system’s ability to exhibit intelligent behaviour. Hence, intelligent ‘thinking’ machinery is feasible in practice.