Tuesday, February 28, 2017

Thinking on the Web: Berners-Lee, Gödel and Turing

When the philosopher René Descartes proclaimed his famous observation "Cogito, ergo sum," he demonstrated the power of thought at the most basic level by deriving an important fact (i.e., the reality of his own existence) from the act of thinking and self awareness.

The boldest attempt to apply logic to mathematics was pioneered by philosopher-logician Bertrand Russell, in Principia Mathematia. The idea was that mathematical theories were logical tautologies, and his program was to show this by means to a reduction of mathematics to logic. The various attempts to carry this out met with a series of failures, such as Russell's Paradox, and the defeat of Hilbert's Program by Gödel's incompleteness theorems.

Russell's paradox represents either of two interrelated logical contradictions. The first is a contradiction arising in the logic of sets or classes. Some sets can be members of themselves, while others can not. The set of all sets is itself a set, and so it seems to be a member of itself. The null or empty set, however, must not be a member of itself. However, suppose that we can form a set of all sets that, like the null set, are not included in themselves. The paradox arises from asking the question of whether this set is a member of itself. It is, if and only if, it is not!

While it was shown that non-Euclidean geometries were consistent relative to Euclidean geometry, proving the consistency of Euclidean geometry has not been achieved by mathematics. It was only found to be consistent as long as mathematics was consistent.

What is undefined?

When students first envision the extensive mathematical landscape, they assume that it is a pristine smooth surface holding all the answers to every mathematical question - just waiting to be unearthed - point to the right spot and there's the answer. They soon discover, however, that the landscape is littered with irregularities, obstructions, and, in some spots, gaping holes.

Math and physics have a lot in common. For example, Infinity and c cannot be treated as ordinary numbers.
Infinity seems to suffer from the contradiction: infinity + 1 = infinity
which reduces to 1 = 0.
The speed of light (c) seems to suffer a similar contradiction: c + 1 = c
which reduces to 1 = 0.
But, Special Relativity put time on the same level as spatial dimensions with the Lorentz transform superseding Newton’s Galilean transform and Einstein redefined how c was understood.
Similarly, Cantor created aleph to redefined infinity through Cardinal and the Continuum Hypotheses so that infinity was no longer treated as an ordinary Real number. 
Of particular importance is the fact that division by zero is literally undefined. Nevertheless, it repeatedly pops-up in the most important problems in science from nonlinear equations to Quantum Field Theory where it is finessed by renormalization (removing/cancelling singularities). When trying to reconcile the mathematical models of physical theories it is necessary to consider the failings of math itself.

What is decidable?

In the 1930s, the logician, Kurt Gödel, established that, in certain important mathematical domains, there are problems that cannot be solved, or propositions that cannot be proved or disproved, and are therefore undecidable. In particular, the work of Kurt Gödel identified the concept of undecidability where the truth, or falsity, of some statements may not be determined. This is relevant to the field of artificial intelligence because of the limits and boundaries that can be inferred from Gödel's insights.

What is machine intelligence?

In 1947, mathematician Alan Turing first started to seriously explore the concept of intelligent machines. He determined that a computing machine can be called intelligent if it could deceive a human into believing that it was human. His test — called the Turing Test — consists of a person asking a series of questions to both a human subject and a machine. The questioning is done via a keyboard so that the questioner has no direct interaction between subjects; man, or machine. A machine with true intelligence will pass the Turing Test by providing responses that are sufficiently human-like that the questioner cannot determine which responder is human and which is not.

Recursion is the process a procedure goes through when one of the steps of the procedure involves rerunning a complete set of identical steps. In mathematics and computer science, recursion is a particular way of specifying a class of objects with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of the class.

Is there art in mathematics?

How much of math is reality-based and how much is art (avoiding irregularities and undefined features in math in order to reach an answer without running into a hole)?

Consider:

ex = -1 was considered unsolvable until Euler discovered one solution:

eiπ = cos π + i(sin π) = -1 + 1*0 = -1

or rewritten as

Euler’s Equation    eiπ +1 = 0

Where this one equation equates five fundamental elements of math:

0 = additive identity - a finite real number
1 = multiplicative identity - an integer real number
π = circular constant pi - a number with unending decimal places
e = the base of natural logarithms - an infinite series
i = imaginary unit

Question: What does it 'mean' when we seek an ‘exact’ value to an infinite series? If it's true in the limit (approaching infinite) then Euler's Equation is an approximation - not an exact solution. 
_______________________________________________

The following excerpts from Alesso [1] illustrate some of these fundamental concepts:

Interlude #1: Thinking about Thinking 

John picked up the two double Latte Grandes and walked over to the corner table near the fireplace where Mary was setting up the chess game. She took a pawn of each color and concealed them in her hands before offering two fists to John.

Putting the cups down, he tapped Mary’s left hand and was pleased to see the white piece as he took his chair.

John said “Playing chess always reminds me of the game between IBM’s Deep Blue Supercomputer and the reigning World Chess Champion at the time, Garry Kasparov.” He glanced at the board, “d4, I think” as he moved his pawn.

Mary said, “Me too.” Mary smiled to herself as she moved her own queen’s pawn forward to d5. She knew that John had strong feelings about the limits of true Artificial Intelligence and she hoped to gain an advantage by baiting him. “That was the first time a computer won a complete match against the world’s best human player. It took almost 50 years of research in the field, but a computer finally was thinking like a human.”

John bristled slightly, but then realized that Mary was just poking a little fun. Taking his next move, c4, he said “You can guess my position on that subject.  The basic approach of Deep Blue was to decide on a chess move by assessing all possible moves and responses. It could identify up to a depth of about 14 moves and value-rank the resulting game positions using an algorithm developed in advance by a team of grand masters. Deep Blue did not think in any real sense. It was merely computational brute force.”

Mary reached over and took John’s pawn, accepting the gambit. “You must admit,” she replied, “although Kasparov’s ‘thought’ processes were without a doubt something very different than Deep Blue’s, their performances were very similar. After all, it was a team of grand masters that designed Deep Blue’s decision-making ability to think like them.”

John played his usual Nc3, continuing the main line of the Queen’s Pawn Gambit. “You’ve made my point,” he exclaimed, “Deep Blue did not make its own decisions before it moved. All it did was accurately execute, the very sophisticated judgments that had been pre-programmed by the human experts.”

“Let’s look at it from another angle.” Mary said as she moved Nf6.  “Much like a computer, Kasparov’s brain used its billions of neurons to carry out hundreds of tiny operations per second, none of which, in isolation, demonstrates intelligence. In totality, though, we call his play ‘brilliant.’  Kasparov was processing information very much like a computer does. Over the years, he had memorized and pre-analyzed thousands of positions and strategies."

“I disagree,” said John quickly moving e3. “Deep Blue’s behavior was merely logic algebra – expertly and quickly calculated, I admit. However, logic established the rules between positional relationships and sets of value-data. A fundamental set of instructions allowed operations including sequencing, branching and recursion within an accepted hierarchy.”

Mary grimaced and held up her hands, "No lectures please." Moving to e6 she added, "A perfectly reasonable alternative explanation to logic methods is to use heuristics methods, which observe and mimic the human brain. In particular, pattern recognition seems intimately related to a sequence of unique images connected by special relationships. Heuristic methods seem as effective in producing AI as logic methods. The success of Deep Blue in chess programming is important because it employed both logic and heuristic AI methods."

"Now who’s lecturing," responded John, taking Mary’s pawn with his bishop. “In my opinion, human Grandmasters, do not examine 200,000,000 move sequences per second.”

Without hesitation Mary moved c5 and said, "How do we know? Just because human grandmasters are not aware of searching such a number of positions doesn’t prove it. Individuals are generally unaware of what actually does go on in their minds. Patterns in the position suggest what lines of play to look at, and the pattern recognition processes in the human mind seem to be invisible to the mind."

John said, "You mean like your playing the same Queen’s Gambit Accepted line over and over again?" as he castled.

Ignoring him, Mary moved a6 and said, "Suppose most of the chess player’s skill actually comes from an ability to compare the current position against images of thousands of positions already studied. We would call selecting the best position (or image) insightful. Still, if the unconscious human version yields intelligent results, and the explicit algorithmic Deep Blue version yields essentially the same results, then why can't I call Deep Blue intelligent too?"

John said, "I’m sorry, but for me you’ve overstated your case by calling Deep Blue intelligent,” moving Qe2. He continued, “ Would you like to reconsider your position?”

Mary moved Nc3 and said, "Of course not, I still have plenty of options to think about, alone this line.”
_______________________________________________

Interlude #2: The Truth and Beauty of Math

As John passed with a sour look on his face, Mary looked up from her text book and asked, “Didn’t you enjoy the soccer game?”

“How can you even ask that when we lost?” asked John gloomily.

“I think the team performed beautifully, despite the score” said Mary.

This instantly frustrated John and he said, "Do you know Mary that sometimes I find it disarming the way you express objects in terms of beauty. I find that simply accepting something on the basis of its beauty can lead to false conclusions?"

Mary reflected upon this before offering a gambit of her own, "Well John, do you know that sometimes I find that relying on objective truth alone can lead to unattractive conclusions."

John became flustered and reflected his dismay by demanding, "Give me an example."

Without hesitation, Mary said, "Perhaps you will recall that in the late 1920's, mathematicians were quite certain that every well-posed mathematical question had to have a definite answer ─ either true or false. For example, suppose they claimed that every even number was the sum of two prime numbers,” referring to Goldbach's Conjecture which she had just been studying in her text book. Mary continued, “Mathematicians would seek the truth or falsity of the claim by examining a chain of logical reasoning that would lead in a finite number of steps to prove if the claim were either true or false."

"So mathematicians thought at the time," said John. "Even today most people still do."

"Indeed," said Mary. "But in 1931, logician Kurt Gödel proved that the mathematicians were wrong. He showed that every sufficiently expressive logical system must contain at least one statement that can be neither proved nor disproved following the logical rules of that system. Gödel proved that not every mathematical question has to have a yes or no answer. Even a simple question about numbers may be undecidable. In fact, Gödel proved that there exist questions that while being undecidable by the rules of logical system can be seen to be actually true if we jump outside that system. But they cannot be proven to be true.”

“Thank you for that clear explanation,” said John. “But isn’t such a fact simply a translation into mathematical terms of the famous Liar’s Paradox: ‘This statement is false.’”

“Well, I think it's a little more complicated than that,” said Mary. “But Gödel did identify the problem of self-reference that occurs in the Liar’s Paradox.  Nevertheless, Gödel’s theorem contradicted the thinking of most of the great mathematicians of his time. The result is that one can not be as certain as the mathematician had desired. See what I mean, Gödel may have found an important truth, but it was – well to be frank – rather disappointingly unattractive," concluded Mary.

"On the contrary,” countered John, “from my perspective it was the beauty of the well-posed mathematical question offered by the mathematicians that was proven to be false.

Mary replied, “I’ll have to think about that.”
_______________________________________________

Interlude #3: Computing Machines

Having had the final word in their last discussion, John was feeling a little smug as he listened to his ipod. Mary sat down next to him on the library steps. Their last class had been on computer design and they were both thinking about just how far the new technology could evolve.

John said, “As you suggested earlier, Gödel was concerned that a logic system had to be consistent and then he determined that no logic system can prove itself to be consistent.”

“True,” replied Mary. “But it was Turing who built on Gödel’s findings. Shortly before WWII, Turing found a way to translate Gödel’s logic results about numbers and mathematics into analogous results about calculations and computing machines.”

John interrupted, “Yes, Turing was convinced that mathematical problem solving could be reduced to simple steps that could be used to program computer actions."

Mary said, “True. Turing considered the logical steps one goes through in constructing a proof as being the same steps that a human mind follows in a computation.” Mary gave John a sideways glance before continuing, “Turing was convinced that the ability to solve this type of mathematical problem is a significant indication of the ability of machines to duplicate human thought.”

John dissented, “Wait a minute. We’ve been here before. Just because machines follow the same logical steps a human uses to solve a calculation doesn’t mean that they actually think. Since calculating machines are not biological, it seems unreasonable to me to suggest that machines are capable of actual creative thought. They may be mimicking the logical steps, but are they actually thinking? I think not.”

“Therefore, you are not,” Mary said with a grin.

John relied, “Hey.”

Mary said, “OK. Seriously, if it were even remotely possible that machines could independently mimic thought that would be significant.”

She continued, “Consider Turing’s Machine. Turing held that a mechanical computer is basically a large number of address locations acting as a memory, together with an executive unit that carries out individual operations of a calculation. These operations represent a program. Let’s imagine that I want to use the machine to add two numbers 1 and 2 together. The computing machine would begin with placing a ‘1’ in the first location and a ‘2’ in the second location and then the computer consults a program for how to do addition. The instructions would say gather the numbers from the two locations and perform a summing operation to yield the sum of the two numbers and place the resultant number ‘3’ in the third location. This process could be considered to mimic the operations a human would perform.”

John replied solemnly, “Simple rote actions.”

Mary added, “Turing’s computer consists of two basic elements: an infinitely long tape ruled off into squares, each capable of being inscribed with the symbol ‘0’ or ‘1,’ and a scanning head that can move forward or back one square at a time reading the symbol on that square, either leaving it alone or writing a new symbol on that square.  At any step of the operation, the scanning head can be in one of an infinite number of states. The machine has a pointer that is set at one of the letters ‘A’ ‘B’ ‘C,’ and this letter represents the state of the machine. Part of the program tells the machine how to change the pointer setting, depending on what state the machine is currently in and what symbol is on the square of the tape that the head is currently reading.”

John nodded slowly as he visualized the machine.

Mary continued, “The action of a Turing machine is determined completely by; (1) the current state of the machine, (2) the symbol in the cell currently being scanned by the head, and (3) a table of transition rules, which serves as the “program” for the machine. If the machine reaches a situation in which there is not exactly one transition rule specified, then the machine halts. While it may take a long tape and many steps to carry out sophisticated calculations, anything at all that can be thought of as following from a set of rules, can be calculated in the step by step fashion.”

John said, “It is easy to appreciate that Turing Machine is the foundation of the modern computer.”

Mary said, “And that leads us to your earlier question about whether a computing machine can have human-like intelligence.”

John said, “In general, I would consider ‘thinking’ to be a complex process that uses concepts and relationships to infer new knowledge. Thinking would involve acts such as memory recall, arithmetic calculations, puzzle solving, and so on. By extension the performance of these acts would indicate ‘intelligence’.” For example, a child who can perform difficult arithmetic calculations quickly would display intelligence. Likewise an individual who has rapid memory recall and who has accumulated sufficient amounts of information to consistently win games such as Scrabble, or Trivial Pursuit, might also be considered to be intelligent.”

“Well then,” responded Mary, “Why wouldn’t a computer that could perform the same calculations as that child, but faster and with greater accuracy be considered intelligent. Or consider a computer with substantial memory storage that is able to answer all those Trivial Pursuit questions. Why can’t that computer, be considered intelligent.”

John said, “Well human thinking involves complicated interactions within the biological components of the brain. In addition, the processes of communication and learning are also important elements of human intelligence.”

Mary replied, “By mentioning intelligent communication you have led us to Turing’s Test for machine intelligence.”

John said, “OK, but please, let’s talk about that tomorrow.”

___________________________________________________________

REFERENCE:

[1]  Thinking on the Web: Berners-Lee, Gödel and Turing, H. Peter Alesso  and Craig F. Smith,
Wiley-Interscience , November 24, 2008, ISBN-13: 978-0471768661.