More on this book
Community
Kindle Notes & Highlights
Read between
January 7 - January 20, 2019
Chess-playing computers probably provide the best examples of machines exhibiting what might be thought of as ‘intelligent behaviour’. In fact, some machines have now (in 1989) reached an extremely respectable level of performance in relation to human players – approaching that of ‘International Master’.
Chess-playing machines rely a lot on ‘book knowledge’ in addition to accurate calculational power. It is worth remarking that chess-playing machines fare better on the whole, relative to a comparable human player, when it is required that the moves are made very quickly; the human players perform relatively better in relation to the machines when a good measure of time is allowed for each move.
One of the claims of AI is that it provides a route towards some sort of understanding of mental qualities, such as happiness, pain, hunger.
The idea is that mental activity is simply the carrying out of some well-defined sequence of operations, frequently referred to as an algorithm.
An algorithm purporting to match what is presumed to be operating in a human brain would need to be a stupendous thing. But if an algorithm of this kind exists for the brain – and the supporters of strong AI would certainly claim that it does – then it could in principle be run on a computer.
Indeed it could be run on any modern general-purpose electronic computer, were it not for limitations of storage space and speed of operation.
It is anticipated that any such limitations would be overcome for the large fast computers of the not-too-distant future. In that eventuality, such an algorithm, if it could be found, would presumably pass the Turing test. The supporters of strong AI would claim that whenever the algorithm were run it would, in itself: experience feelings; have a consciousness; be a mind.
Dualism is a philosophical viewpoint espoused by the highly influential seventeenth century philosopher and mathematician René Descartes, and it asserts that there are two separate kinds of substance: ‘mind-stuff’ and ordinary matter.
The point is that the mind-stuff is not supposed to be composed of matter, and is able to exist independently of it. The mind-stuff of strong AI is the logical structure of an algorithm.
This dilemma lies behind the scenes of an argument put forward by Douglas Hofstadter (1981) – himself a major proponent of the strong-AI view – in a dialogue entitled ‘A Conversation with Einstein’s Brain’. Hofstadter envisages a book, of absurdly monstrous proportions, which is supposed to contain a complete description of the brain of Albert Einstein.
But his claim is that in principle the book is completely equivalent, in the operational sense of a Turing test, to a ridiculously slowed-down version of the actual Einstein.
In fact, I do not regard the idea as intrinsically an absurd one – mainly just wrong!
In effect, all modern general purpose computers are universal Turing machines. Thus, all general purpose computers are equivalent to one another in the above sense: the differences between them can be entirely subsumed in the software, provided that we are not concerned about differences in the resulting speed of operation and possible limitations on storage size.
What is it that gives a particular person his individual identity? Is it, to some extent, the very atoms that compose his body? Is his identity dependent upon the particular choice of electrons, protons, and other particles that compose those atoms? There are at least two reasons why this cannot be so.
In the first place, there is a continual turnover in the material of any living person’s body. This applies in particular to the cells in a person’s brain, despite the fact that no new actual brain cells are produced after birth. The vast majority of atoms in each living cell (including each brain cell) – and, indeed, virtually the entire material of our bodies – has been replaced many times since birth.
If an electron in a person’s brain were to be exchanged with an electron in a brick, then the state of the system would be exactly11 the same state as it was before, not merely indistinguishable from it!
What distinguishes the person from his house is the pattern of how his constituents are arranged, not the individuality of the constituents themselves.
Let us accept that a person’s individuality has nothing to do with any individuality that one might try to assign to his material constituents. Instead, it must have to do with the configuration, in some sense, of those constituents – let us say the configuration in space or in space-time.
Is there anything in the laws of physics which could render teleportation in principle impossible?
ALGORITHMS AND TURING MACHINES
WHAT PRECISELY IS an algorithm, or a Turing machine, or a universal Turing machine? Why should these concepts be so central to the modern view of what could constitute a ‘thinking device’? Are there any absolute limitations to what an algorithm could in principle achieve?
The problem of Hilbert’s that concerned Turing (the Entscheidungsproblem) went beyond any particular formulation of mathematics in terms of axiomatic systems. The question was: is there some general mechanical procedure which could, in principle, solve all the problems of mathematics (belonging to some suitably well-defined class) one after the other?
The numbers that can be generated in this way are called computable (Turing 1937). Those that cannot (actually the vast majority!) are non-computable.
Fermat was the finest mathematician of his time. He claimed to have ‘a truly wonderful proof of his assertion, which the margin was too small to contain; but to this day no-one has been able to reconstruct such a proof nor, on the other hand, to find any counter-example to Fermat’s assertion!
I feel that it is worth while to give a brief description of Church’s scheme not only because it emphasizes that computability is a mathematical idea, independent of any particular concept of computing machine, but also because it illustrates the power of abstract ideas in mathematics.
MATHEMATICS AND REALITY
The quantity i cannot, of course, be a real number since the product of a real number with itself is always positive (or zero, if the number is itself zero). For this reason the term imaginary has been conventionally applied to numbers whose squares are negative. However, it is important to stress the fact that these ‘imaginary’ numbers are no less real than the ‘real’ numbers that we have become accustomed to.
CONSTRUCTION OF THE MANDELBROT SET
PLATONIC REALITY OF MATHEMATICAL CONCEPTS?
The Mandelbrot set is not an invention of the human mind: it was a discovery. Like Mount Everest, the Mandelbrot set is just there!
Is mathematics invention or discovery? When mathematicians come upon their results are they just producing elaborate mental constructions which have no actual reality, but whose power and elegance is sufficient simply to fool even their inventors into believing that these mere mental constructions are ‘real’? Or are mathematicians really uncovering truths which are, in fact, already ‘there’ – truths whose existence is quite independent of the mathematicians’ activities? I think that, by now, it must be quite clear to the reader that I am an adherent of the second, rather than the first, view,
...more
WHAT IS TRUTH? How do we form our judgements as to what is true and what is untrue about the world? Are we simply following some algorithm – no doubt favoured over other less effective possible algorithms by the powerful process of natural selection? Or might there be some other, possibly non-algorithmic, route -perhaps intuition, instinct, or insight – to the divining of truth? This seems a difficult question.
The great mathematician David Hilbert, whom we first encountered in Chapter 2, embarked upon a much more workable and comprehensive scheme. All correct mathematical types of reasoning, for any particular mathematical area, were to be included. Moreover, Hilbert intended that it would be possible to prove that the scheme was free from contradiction.
However, the hopes of Hilbert and his followers were dashed when, in 1931, the brilliant 25-year-old Austrian mathematical logician Kurt Gödel produced a startling theorem which effectively destroyed the Hilbert programme.
What Gödel showed was that any such precise (‘formal’) mathematical system of axioms and rules of procedure whatever, provided that it is broad enough to contain descriptions of simple arithmetical propositions (such as ‘Fermat’s last theorem’, considered in Chapter 2) and provided that it is free from contradiction, must contain some statements which are neither provable nor disprovable by the means allowed within the system.
We shall see why Gödel’s argument cut to the very core of the Hilbert programme. We shall also see how Gödel’s argument enables us, by the use of insight, to go beyond the limitations of any particular formalized mathematical system under consideration.
Notice that something very remarkable has happened here. People often think of Gödel’s theorem as something negative -showing the necessary limitations of formalized mathematical reasoning. No matter how comprehensive we think we have been, there will always be some propositions which escape the net.
Real mathematical truth goes beyond mere man-made constructions.
but to show that a specific Gödel proposition – neither provable nor disprovable using the axioms and rules of the formal system under consideration – is clearly seen, using our insights into the meanings of the operations in question, to be a true proposition!
Fig. 4.5. The set defined by the exponential relation y ≥ ex should also count as ‘recursive’.
SOME EXAMPLES OF NON-RECURSIVE MATHEMATICS
There are very many areas of mathematics where problems arise which are not recursive. Thus, we may be presented with a class of problems to which the answer in each case is either ‘yes’ or ‘no’, but for which no general algorithm exists for deciding which of these two is actually the case. Some of these classes of problem are remarkably simple-looking.
Thus this particular word problem by itself is an example of non-recursive mathematics, in the sense that using this particular initial list we cannot algorithmically decide whether or not two given words are ‘equal’.
It is perhaps remarkable that such an apparently ‘trivial’ area of mathematics – namely covering the plane with congruent shapes – which seems almost like ‘child’s play’ should in fact be part of non-recursive mathematics.
Even for problems where it is clear that algorithms exist and how such algorithms can be constructed, it may require much ingenuity and hard work to develop such algorithms into something usable. Sometimes a little insight and ingenuity will lead to considerable reductions in the complexity of an algorithm and sometimes to absolutely enormous improvements in its speed.
There are many examples of (classes of) problems which are not in P. For example, in order to perform the operation of computing 22r from the natural number r we would need about 2n steps even just to write down the answer, let alone to perform the calculation, n being the number of binary digits in the binary representation of r.
In a general way, problems which are in P are regarded as being ‘tractable’ (i.e. ‘soluble in an acceptable length of time’), for reasonably large n, on a fast modern computer, while problems in NP which are not in P are regarded as being ‘intractable’ (i.e. though soluble in principle, they are ‘insoluble in practice’) for reasonably large n – no matter what increases in operational computer speed, of any foreseeable kind, are envisaged.
(The actual time that would be taken, for large n, rapidly becomes longer than the age of the universe for an NP problem not in P, which is not much use for a practical problem!)
Any clever algorithm for solving the Hamiltonian circuit problem in polynomial time could be converted into an algorithm for solving any other ...
This highlight has been truncated due to consecutive passage length restrictions.
It is commonly believed by the experts that it is actually impossible, with any Turing machine-like device, to solve an NP-complete problem in polynomial time, and that, consequently, P and NP are not the same. Very likely this belief is correct, but as yet no-one has been able to prove it. This remains the most important unsolved problem of complexity theory.
