My first involvement with programming was using the computer housed on one of Bradford University’s upper floors. I remember an acquaintance, Eddie North, asserting in his authoritative Yorkshire accent, “Of course computers cannot think!” Over half century later the computer has shrunk from wholefloorofbuilding to pocketsize. And people are asking not whether computers think, but whether there is value in people thinking like computers. It this series of articles I explore the idea of computational thinking and its relationship to educational robots. We start with a fascinating history of tremendous ideas.
George Boole was born in Lincolnshire, England in 1815. His father, John Boole was a cobbler with a passion for education, particularly mathematics and science. George embraced this heritage and in 1854 he published a mathematical paper entitled, the Laws of Thought. This ambitious topic had historical ancestry dating back to Ancient Greece and became particularly frenetic at the end of the 19^{th} and the start of the 20^{th} centuries.
The Greeks believed that deductive reasoning followed patterns that could be defined by a set of rules. Hence the syllogisms of Aristotle.
All men are mortal.  Major Premise 
Socrates is a man.  Minor Premise 
Soctrates is mortal.  Logical Conclusion 
Aristotelian logic is called propositional logic; it dominated the Ancient European, Islamic and medieval worlds. But there was another school of thought in Ancient Greece, the Stoics. They investigated another type of logic calling it conditional logic. It is represented by the statements IF something THEN this.
In the 1650s English philosopher Thomas Hobbs proposed just as speaking or writing words is a process of playing around with symbols, so was thinking. The difference was thinking was an internal process. The great German philosopher and mathematician, Gottfried Leibniz (1646 – 1716) went further. He envisioned a mathematical language that could analyse arguments. His dream was that in the event of a dispute you would turn the arguments into mathematical formula and calculate the answer. Ironically he spent a lot of his professional life bitterly arguing with Sir Isaac Newton about which one of them invented calculus.
Boole was the first one to make a tangible contribution to Leibniz’s dream. He formulated an algebra which would develop into Boolean Algebra that could mathematically resolve Aristotle’s syllogistic arguments. Few computer operations do not use this Algebra. Every time you search the internet to find something – Boolean Algebra does its thing. Boolean Algebra is concerned with finding out if a proposition is TRUE or FALSE. Digital statements like IF A THEN B permeate computer processes. That is if proposition A is TRUE (e.g. the printer is on) then execute B (e.g. print the document). Effectively Boole showed that logical statements (thoughts) could be dealt with as a branch of mathematics.
There is another strand of human intellectual endeavour that will eventually converge on our story. It concerns some fundamental comparison of mathematical and scientific ways of thinking. The scientific method involves making careful observations and then developing a theory that explains our experience. British mathematician and philosopher Bertrand Russell pithily stated the problem with this approach: “The man who has fed the chicken every day throughout its life at last wrings its neck instead…” no doubt a shock for the scientifically trained chicken. In short we cannot be absolutely certain that our laws of science are immutable[2].
Science is an inductive process. Like logic, mathematics is deductive. Its foundation is proof. We can prove that there are an infinite number of Prime Numbers, not by observation, but through deductive argument. Mathematical proofs go beyond, culture, language, time, gender… Mathematical proofs are absolute. However, they are based on some assumptions – technically called axioms.
Axioms are things that seem obvious. Euclidian geometry has five axioms: for example parallel lines are always the same distance apart no matter how long the lines, they will never meet. No one has made the infinite journey confirm this, but common sense tells us its true.
Mathematics is a world of pure abstract thought. Numbers, for example, are ideas in the human mind. The fact that we can use them for practical purpose e.g. for counting how many children turned up for school today is a happy coincidence. It is interesting that several animals exhibit basic mathematical skills like counting, knowing the difference between one and two: big and small, or a sequence of events. My dog excitedly recognises that a sequence of my actions lead to him being fed and another sequence to him going for a walk. Animals do this type of thing without the need for proof (as did our prehistoric ancestors). Nevertheless, they cannot do advanced mathematics, which according to mathematician and author Keith Devlin we can do because of our ability to symbolise and speak. Nor can they build sophisticated arguments based on basic proofs. For millennia mathematicians used proofs to develop more proofs. School geometry is a inverted tower of proofs: one proof supporting other proofs all based on Euclid’s axioms. You can imagine the crisis if we found these assumptions were not correct. Well, that’s what happened to Euclid’s parallel axiom.
In 1829, Russian mathematician Nikolay Lobachevsky (1792 – 1856) developed a form of geometry where more than one line could be parallel. This ishyperbolic geometry. Soon the German Bernhard Riemann (1826 1866) discovered a third geometry. This is called spherical geometry – the geometry that exists on the surface of a sphere. Here there are no parallel lines, and the internal angles of a triangle added up to more than 180 degrees! This particular geometry found practical use in describing the curvedtimespace of Einstein’s theory of relativity.
You can imagine that these results were unsettling. Mathematicians started to be concerned about the very foundations of their subject. So the axiomatic movement was formed, whose broad aim was cleaning up the foundations of the subject.
German mathematician Georg Cantor (1845 – 1918) had singlehandily developed set theory. Squares in the Roamer MultiActivity Mat containing yellow shapes form a set of squares with yellow shapes. With or without Cantor’s efforts humans intuitively sort and order things. The mathematics here is very fundamental. How many squares contain animals? There are six – a set of six. There are also a set of six pools of water. This is the definition of cardinal number – it is the number of elements in the set – animals, pools of water – it does not matter what the object is the important characteristic of the set is its cardinal value: 6. The idea of set theory was to define such terms as cardinal number with mathematical rigour.
This is a complicated way of talking about the maths of early years education, the stress of doing it drove Cantor to a nervous breakdown. In part this was because many established mathematicians hated his ideas. The attacks were personal and vicious. His teacher Leopold Kronecker (1823 –1891) called him a corrupter of youth. The exceptional French mathematician Henri Poincare (1854 – 1912) stated that Cantor’s work was a disease infecting mathematics.
This enmity arose because Cantor’s work had led him to explore the idea of infinity. This had scared off at least two of the world’s greatest mathematicians fellow Germans Leibnitz and Friedrich Gauss (1777 –1855). They both warned against investigating infinity. Yet, infinity was a key concept in the calculus that caused the Leibnitz Newton squabble. At the heart of calculus, a mathematics which is crucial to a significant proportion physics and engineering science, is this dodgy idea that mathematicians did not really understand and were terrified of investigating.
Perhaps they were right to be worried, because it does lead to some very mind boggling discoveries. For example Cantor proved that there are infinities bigger than other infinities! For example the infinite set of all natural numbers, (that is the counting numbers 1, 2, 3, 4, 5…) is the same size as infinitely as the even numbers! This defies common sense, after all the even numbers are part of the set of counting numbers. Nevertheless, Cantor proved that the cardinal value of their infinite sets was the same size.
On the other hand, the infinite set of real numbers is bigger than the infinite set of natural numbers. (A real number is anything you can position on a number line – it includes the natural numbers and numbers like, 1.5, 8, 1.500005, etc.). These are called uncountable sets, or uncountable numbers.
Confusing! Definitely. It defies common sense. All that can be done is simply accept there is a sound mathematical proof of these ideas.
You would be right if you thought that our story was full of Germans. Before Herr Shicklgruber (aka Adolf Hitler) wove his evil magic, Germany was the mathematical centre of the world. It is another German who continues the story – Gottlob Frege (18481925).
In 1879 Frege published Begriffsschrift. The word translates as conceptscript. It is a formal language of what is called predicate logic. While Boole started out with the idea of developing an algebra that would calculate the validity of propositions Frege aimed to clarify the concepts of arithmetic and clean up the basis of mathematics by creating for it a logical foundation. Boole’s logic explored the relationship between one proposition and the next. Frege’s logic got inside the proposition and examined the relationship between subject and predicate. It also introduced quantifiers, words like Every, All, None, Some, Many and Most. One of Frege’s great contributions was the development of symbolic logic. That is the mathematical language (notation) used to represent logical statements. This language works whether its elements are mathematical or linguistic.
In 1902 the second volume of Frege’s book: “The Foundations of Arithmetic: the logicalmathematical Investigation of the Concept of Number” was at the printers. It summarised over twenty years of his work. Suddenly, he received a letter from, young British mathematician Bertrand Russell (18721970). It contained a devastating observation which Frege recognised, blew a gigantic hole in his theory and consequently his life’s endeavours.
Russell and his Cambridge colleague, Alfred North Whitehead (18611947), spent 10 years working on the foundational problems using the logical approach trying to fix Frege’s symbolic logic. The result of this effort was the three volume Principia Mathematica. This laborious effort took 200 pages just to prove that 1 +1 = 2.
Some years earlier another German had become involved in this mathematical clean up. The genial David Hilbert (1862 – 1943), the doyen of the mathematical world, became its campaign manager. Hilbert had had a stellar career at the heart of the mathematical world. Amongst his many achievements was the proof that consistency of Euclidean geometry depended on the consistency of arithmetic. In 1900 Hilbert had been invited to give a keynote speech at the International Conference of Mathematicians at the Sorbonne, Paris. He laid down a challenge to the mathematical world in the form of 10 problems that they need to resolve in the twentieth century. Later he expanded this to 23 problems. If you solved an Hilbert Problem, you were guaranteed entry into the mathematician’s hall of fame.
One of the problem’s was very close to Hilbert’s heart. He was a fervent supporter of Cantor’s and Frege’s logicism as the way to achieve the clean up goal. This process had refocused on what is known as formal systems. The game of chess has a set objects (King, Queen, Rook, etc.) and set of rules. The Japanese game of GO contains a set of black and white pebbles and rules. Both games form complete systems in their own right, with objects and rules. English is a system with words (objects[3]) and grammar (rules) for manipulating those words. The word object is completely synonymous with the word symbol. The proposal was you could have whatever symbols and rules for manipulating the symbols you wanted, as long as they formed a system.
All computer languages are what are called well formed systems. Mathematically, for the system to be “well formed” it must meet two stipulations. Hilbert had reduced the question to whether we could create a mathematical system that was complete and consistent. Was specifying the symbols and rules (no axioms) enough to create a system that would contain proofs of all its own truths. For example could we find some new rules that would help us get around the Russell Paradox. The second requirement was simply that the system had to be consistent. That is if you prove 1 + 1 = 2 you could not find a contradictory proof saying 1 + 1 = 7.
In 1928 Hilbert posed a related problem called in German the Entscheidungsproblem. This is the decidability issue. Is there a way we can decide whether a given proposition is provable? In a 1931 a symposium on mathematical foundations took place in the Eastern Prussian city of Königsberg. In a closing round table session a quiet a Sudeten German, Kurt Gödel (1906 – 1978) announced a proof that destroyed Hilbert’s foundational aspirations. Gödel’s incompleteness theorem showed that is was impossible for a system to be self sufficient. You would get contradictions. You could add more rules, as Russell and Whitehead had done, but that was a new system that could not prove itself. Gödel devised a method of encoding any statement into a unique number called Gödel numbers. The proof was then a matter of arithmetic.
ASCII Code is a form of Gödel Numbering. Each symbol is converted into a number the computer can understand.
R 
O 
A 
M 
E 
R 

ASCII 
82 
79 
65 
77 
69 
92 
Despite being one of the foremost logician’s of all time, Gödel became convinced that people were trying to poison him. He stopped eating and literally starved himself to death.
In 1935 a young Cambridge graduate was out for one of his regular cross country runs. He stopped for a rest, and lay in a meadow. The digital computer was about to be born. The runner was Alan Mathison Turing (1912 1954). In that moment Turing conceived of how a machine could solve the Entscheidungsproblem.
Alan had always had a history of tinkering with machines. During a visit to Princeton he built an electric multiplier machine which involved him getting dirty in a workshop making relays and other parts. There was nothing new about the technology, but the use of binary numbers and Boolean algebra was certainly a fresh idea. The machine the young athlete conceived now was different. It did not exist. It was a mental model; a process of thought. It is called a Turing Machine.
A paper tape is divided into to sections. The head reads the content of a section (the state) and then according to the configuration of the particular Turing Machine it would either leave the content of the section untouched, or overwrite the existing content with a new symbol or make it blank (change the state). Then it would either leave the tape unmoved, or move the it one section to the left or section to the right.
The virtual machine was controlled by a simple table of symbols. A tape like this consists of two sets of symbols separated by a blank.
1  1  1  1  1  1  1  1  1  1  1  1 
Is transformed, by a Turing machine into this:
1  1  1  1  1  1  1  1  1  1  1  1 
This represents and adding process, which is controlled by the table below.
So lets say the machine starts with the head scanning the section of the tape on the far left. This is blank. So according to the table in Configuration 1 it does not write anything, it moves right one section and retains the Configuration 1 status. The next section scanned is 1. So again the machine writes nothing moves right and changes the Configuration to 2. You can follow this algorithm through and you will see that eventually the tape will show the two numbers added together.
Scanned Symbols  blank  1 
Action 

configuration 1  move right, config 1  move right, config 2 
configuration 2  write 1, move right, config 3  move right, config 2 
configuration 3  move left, config 4  move right, config 3 
configuration 4  no move, config 4  erase, no move. config 4 
The problem of how do we feed the machine with the information from a two dimensional table into machine that can only scan a one dimensional tape. Turing devised a system of encoding like Gödel numbers that ended up producing what he called a description number. You can create an infinite number of Turing machine capable of determining any number whether it was , π or the values of a sinusoidal function. π is an irrational number, which means its decimal representation never ends or repeats. While actually calculating the value of π is an infinite process the table used by a Turing machine is finite. That is there is a finite descriptor number. Because it could be defined in this way, Turing called π a computable number.
3.14159265389792384626433832795028841971693993751058
49445923078164062862089986280348253421170679
Are there any uncomputable numbers? If Turing could answer that he would solve Hilbert’s decidability problem. The discovery of an uncomputable number would mean a mathematical function that could not be solved by a Turing Machine, that is no finite table, no descriptor number and no algorithm existed to solve the problem. Since there was an infinite number of potential Turing Machines, how could this be decided? The answer was in the use of Cantor’s diagonal proof. If Turing listed all the descriptor numbers together in order, they would form an infinite set. If the infinite set of descriptor numbers was bigger than the infinite set of natural (counting) numbers then the descriptor numbers are also uncountable. That is some problems existed that were beyond mathematical proof. This proved to be the case and Hilbert became another mathematician who had dreamt for decades and whose dream turned to dust.
What on earth has all this to do with thinking? We have essentially got the bedrock of machine thinking. It is as though instead of looking at human thoughts, we are looking at the firing of the brains synapses, the neurological activity that takes place when we think. Turing was not the only person to solve the Entscheidungsproblem. Americans Alonzo Church (1903 – 1995) and Emil Post (1897 – 1954) both used different approaches to get the same result. But Turing had invented a hypothetical machine. He had laid the mathematical foundation for all computers.
Turing used the term “machine thinking” and was clearly interested in the understanding how it related to human thought. The “state” of a machine was analogous to a state of mind, What symbols (thoughts) was the machine scanning and how was its “behaviour” going to make it react. This led to the Turing proposing the famous Turing Test which was aimed at deciding whether machine intelligence was equivalent to human thinking.
Everyday, a version of the Turing Test is performed millions of times. If you telephone on organisation, can you recognise whether you end up talking to a human operator of an automatic machine? When the machines become good enough to fool us, they will pass the Turing Test.
In this journey we started with the Ancient Greeks systemising thought patterns applicable to logic. We have seen how George Boole developed an algebra that would connect these thinking patterns to mathematics. We looked at how Cantor’s perseverance formulated the basic mathematical tools that Frege would use to develop a logic, which could be applied to symbolic objects whether they were mathematical, logical , graphical or linguistic. We followed the hopes, struggles and devastating traumas of the mathematical world’s efforts to purify itself. Then finally, the stroke a genius from a 24 year old mathematician. All of this led to the creation of a computer.
In the next article we will see how the computer developed, how its close relation Artificial Intelligence and robots emerged and the first steps in the use of this technology in education.
[1] In logic there is a difference between valid arguments and sound arguments. If the premises of an argument are not correct, then when combined properly they will give a valid, but unsound argument.
[2] This may seem one of those convoluted, obscure statements made by philosophers, but there are scientists, working in the weird worlds of quantum and astrophysics that are beginning to think this might be true. That the laws we know may be local and may also change with time.
[3] Words (spoken, written our thought) are symbols. The word dog symbolises a particular animal in English, but in French the symbol is chien and German hund.