Podcast: Play in new window | Download | Embed
Episode Summary:
In this episode, we explore the question of what can computers do as well as what computers can’t do using the Turing Machine argument. Specifically, we discuss the computational limits of computers and raise the question of whether such limits pertain to biological brains and other non-standard computing machines.
Show Notes:
Hello everyone! Welcome to the fourth podcast in the podcast series Learning Machines 101. In this series of podcasts my goal is to discuss important concepts of artificial intelligence and machine learning in hopefully an entertaining and educational manner. Today, we will learn how mathematicians have approached the problem of characterizing the computational limits of computing machines. The podcast today has lots of examples but before jumping to the examples, let’s briefly discuss the core idea that will be covered today.
The basic idea is as follows. We will define a simple logical rule-based machine which can, in principle, replicate the computations of every possible modern electronic digital computer. This simple logical rule-based machine consists of a collection of IF-THEN rules and can be considered to be a special type of production system such as discussed in Episode 3. We will call this simple but very special logical rule-based machine a “Turing Machine”. We will then review a mathematical result which states that for no matter how carefully we try to define the logical rules that govern the behavior of the Turing Machine, there will always be certain problems in deductive inference that can’t be solved by the machine. Since the simplified machine can represent the behavior of any possible electronic digital computer and the simplified Turing Machine can not solve certain problems, it then follows that those problems can not be solved by every possible computer.
This is an interesting argument because it is a theoretical argument about the limitations of what can and can not be computed which is applicable not only to every possible computer that exists today but additionally every possible computer that could be built in the distant future!
Ok…now that we have reviewed the key idea of this podcast…let’s discuss each of the components of this key idea.
The first component is the concept of a “theoretical argument”. An experimental argument involves making some observations and gathering evidence to support some hypothesis. Experimental arguments are fundamentally inductive arguments. The result of an experimental argument could be called an “experimental result.” In contrast, a “theoretical argument” involves making certain assumptions about the world and the using deductive inference to generate the implications of those assumptions. The result of a theoretical argument could be called a “theoretical result” and is typically presented in the form of a mathematical theorem.
This is the power of mathematics. Using mathematical reasoning it is sometimes possible to figure out by logical deduction the outcome of an experiment without actually doing the experiment at all!! This type of mathematical reasoning works as follows. First, we try to write down all the assumptions characterizing the context of the experiment. Then we try to use logical deduction to determine what are the implications of those assumptions and come to conclusions regarding what will happen. If we can explicitly write down every single assumption in an exact manner and if we can explicitly document every specific logical deduction which we used to come to our conclusions, then we have what is called a theoretical result. Such theoretical results are summarized as theorems. A theorem states that IF we make certain assumptions about the world and the experimental context, THEN we can state the outcome of the experiment even though we never did the experiment at all!
Theorems are always true. However, just because a theorem is always true, doesn’t mean the theorem makes a true prediction of reality in the world in which we live. That is because the assumptions of the theorem may or may not be true of the physical world. That is, the IF part of the theorem are often an “abstraction” or “approximation” to the real world. For example, the laws of Newtonian gravitational physics are sometimes used to calculate the gravitational force between the earth and the sun where both the earth and sun are treated as “point masses”. However, this is just an approximation to reality.
[Time Travel Transition Music]
We are now in the year 1900. The Great Mathematician Hilbert thought the field of mathematics was not built on sturdy foundations. All of mathematics is based upon logical deduction. In mathematics, as we previously noted, you make assumptions and then you prove theorems. That is, you do logical thought experiments exploring the implications of specific assumptions. The Great Mathematician Hilbert wanted to prove a theorem which said that if the field of mathematics comes up with just the right set of IF-THEN rules describing mathematical results then it would be possible by logical deduction to prove whether or not any statement in mathematics was true or false. Hilbert was unable to prove this theorem. For simplicity, we will refer to this problem as “Hilbert’s Homework Problem”!
Although this problem may not seem as if it is related to artificial intelligence, it is in fact very central to the field. For example, suppose that we have a robot and we have provided the robot with a knowledge base in the form of IF-THEN rules. Some of these IF-THEN rules correspond to knowledge about how the world works while other IF-THEN rules correspond to knowledge about strategies for guiding behavior. When we provide the robot with a request, then it tries to apply its IF-THEN rules in order to comply with the request. This is actually equivalent to proving a mathematical theorem where the premise of the theorem corresponds to the current state of the world and the conclusion of the theorem corresponds to your request to the robot. The robot must figure out how to apply the IF-THEN rules so that the request can be achieved given the current state of the world. Or equivalently, the robot must prove a theorem!
Thus, Hilbert’s problem was not only a problem about proving mathematical theorems it also had the equivalent interpretation as a problem about deriving plans of action from IF-THEN rules for robots!
Additional discussion of computer systems that represent knowledge using IF-THEN rules can be found in Episode 3.
[Time Travel Transition Music]
We are now in the year 1929 which is about three decades later. The Great Mathematician Gödel was investigating Hilbert’s Homework Problem and managed to show something very interesting. Gödel proved that Hilbert’s Homework Problem was impossible to solve!
In other words, Gödel showed that no matter how hard you try that you will never be able to come out with a set of IF-THEN rules for a sufficiently rich collection of statements that will allow you to determine whether each member of the set of statements is definitely true or definitely false. A famous example of such a situation which was closely related to the approach Gödel used in his analysis is called the “Liar’s Paradox”. The Liar’s paradox can be described as follows.
Suppose we are trying to cross a bridge but there is a monster troll who guards the bridge. The monster troll will let us cross the bridge but only if we ask the troll a question that it can not answer correctly. After consulting briefly with Gödel, we ask the troll the following question:
“Monster Troll! Here is the question we ask in order to cross the bridge! Please tell us whether or not the meaning of the statement on this piece of paper is either TRUE or FALSE. The statement on this piece of paper is: “THIS STATEMENT IS FALSE.”
Note that if the Monster Troll decides the meaning of the statement on the piece of paper is true then this is a contradiction because the meaning of the statement on the piece of paper is false. If the Monster Troll decides the meaning of the statement on the piece of paper is false then this is a contradiction because that implies that the meaning of the statement on the piece of paper is true!
The “Liar’s Paradox” as illustrated by the Monster Troll story essentially implies that for certain collections of IF-THEN statements representing logical rules that there will always exist some statements that can’t be proved to be either true or false.
[Time Travel Transition Music]
It is now the year 1936 about 6 years after Gödel’s analysis of Hilbert’s Homework Problem. In the Year 1936 (10 years before the first digital computer ENIAC had been built in 1946) the Great Mathematician Alan Turing was interested in pursuing a “thought experiment”. Specifically, he was trying to convince other researchers as well as himself that if a computer was actually built that it could do all sorts of amazing things. Here was Turing’s thought experiment.
Turing imagined a logic machine that had the following three ingredients:
(1) A finite number of IF-THEN rules
(2) An infinite amount of memory storage
(3) The machine can run forever if necessary
We will call this a Turing Machine. The Turing Machine can be interpreted as a type of production system for manipulating logical rules. We discussed production systems in Episode 3 of this podcast series.
A machine that incorporates these 3 elements is said to have implemented an “effective procedure”. Every modern computer can be viewed as a special case of this more general machine so if we understand the limitations of computing for this machine then this helps us understand the limitations of computation for a wide range of computing machines.
This is the first amazing contribution of Turing!!! When we are trying to develop a THEORETICAL RESULT, in many cases 50% of the problem is coming up with the right ASSUMPTIONS. Proving an amazing theoretical result is always a lot easier when you have the right assumptions. In this case, Turing formulated a collection of assumptions which to some extent capture the essence of all “computing”. Not just electronic computers but also biological computers such as human and animal brains!!!! Note, however, the key assumption of Turing’s analysis is that “computing” means “computing with logical rules”.
We will define a Turing Machine as “solving a computational problem” if it stops in a finite number of steps following the formulation of the mathematician Kleene. This is a little different from Turing’s original definition.
Ok…so now..Turing proved the following Theorem.
- it doesn’t matter how many rules you provide the computing machine…
- it doesn’t matter how much time you give the computing machine…
- it doesn’t matter how much knowledge
(i.e., the IF part or Assumptions of the IF-THEN rules) you give the machine…
there will always be some computational problems that the computing machine will never be able to answer. This theorem turned out to be another way of stating Gödel’s theorem but it was formulated in terms of the problem of computing.
[Begin Digression Music]
Before continuing our discussion, however, it is appropriate that we have a short digression….
[Digression Music Fade out]
In Chapter 27 of the fiction book “The Hitchhikers Guide to the Galaxy” by Douglas Adams, a race of hyperintelligent pandimensional beings builds a fantastic supercomputer the size of a small city. They build the supercomputer in the hopes that it will be able to provide answers to their social problems as well as answers to all problems associated with the universe.
This supercomputer was called “Deep Thought”. On the day of the “Great On-Turning”, two of the hyperintelligent pandimensional beings approach the supercomputer and ask the supercomputer for “The ANSWER to Life, the Universe, and Everything”. Deep Thought responds that it would take about Seven and a Half Million years to figure out the answer. The pandimensional beings were disappointed but agreed to wait for the answer.
Seven and a half million years later, a great celebration was held among the hyperintelligent pandimensional beings since this was the day that Deep Thought had said that the answer would be revealed.
All the hyperintelligent pandimensional beings gathered to hear Deep Thought’s Answer. Deep Thought began to talk. His first words were: “Well…I have the answer but you guys are not going to like this answer!” The hyperintelligent pandimensional beings were not dissuaded…indeed they had waited 7.5 million years for the answer…they wanted to hear it!!! And so after some persuasion, Deep Thought provided them with the “The ANSWER to Life, the Universe, and Everything”. Deep Thought’s answer was: 42!
There was a long dead silence as all of the hyperintelligent pandimensional beings tried to absorb Deep Thought’s statement.
Finally, in great consternation, the hyperintelligent pandimensional beings cried out that they did not understand the meaning of this answer and asked the Stupendous Supercomputer Deep Thought to explain. But the Stupendous Supercomputer simply said that if the hyperintelligent pandimensional beings had a better understanding of the question, then the answer 42 would be more meaningful to them. To this, the hyperintelligent pandimensional beings asked the Stupendous Supercomputer Deep Thought if he could provide the QUESTION associated with the answer 42 in more detail.
The Stupendous Supercomputer Deep Thought responded that its computing power was limited and even if it worked on this problem forever it would be incapable of figuring out the Ultimate Question even though he had the computational power to provide the ANSWER to the Ultimate Question. The hyperdimensional beings were upset with this news, but Deep Thought managed to make them feel a little better by saying the following.
Deep Thought explained that it (Deep Thought) was capable of designing an even more powerful computer which, in fact, after ten million years of computations would be able to compute the Ultimate QUESTION to Life, the Universe, And Everything whose ANSWER is 42.
Deep thought described this new and infinitely more powerful supercomputer (which Deep Thought would design) as a computer of “infinite and subtle complexity that organic Life itself shall form part of its operational matrix”. Moreover, the new computer will take ten million years to complete the calculation of the Ultimate Question. Deep Thought refers to this new computer as: Earth.
And so the Earth was created by Deep Thought.
[DIGRESSION TRANSITION MUSIC]
The concept of the Earth as a giant supercomputer is intriguing. We can visualize the evolution of all physical processes on Earth at multiple levels: subatomic, atomic, molecular, organic, geological. The current state of the Earth can be visualized as a long list of features each of which takes on the value of “present” or the value of “absent”. As each physical process evolves from one time instant to the next the state of the Earth is recomputed from the previous state of the Earth according to a large collection of rules.
If these rules could be represented as IF-THEN rules then why couldn’t we imagine the Earth to be some sort of super advanced computer that is doing some sort of super advanced calculation?
On the other hand, one might argue that the state variables of the planet Earth are not true or false but rather are numerical. If this argument is correct, then certain features of the physical dynamics of the Earth can not be represented as IF-THEN rules in which case either we must conclude that the Earth is not a computer or it is a computer which can’t necessarily be represented as a Turing machine and maybe it is even more powerful than a Turing machine. Or, in other words, perhaps the concept of a “computer” should not be limited to a machine that is restricted to symbolic IF-THEN rule-based computations?
We can develop a generalization of the concept of a symbolic rule-based machine such as a Turing machine by introducing the idea of a dynamical system. Every Turing machine can be represented as a dynamical system but there are many dynamical systems that can not be represented by Turing machines. A dynamical system consists of a collection of variables.
The particular value a variable takes on is called the variable’s state. The state of a variable in a Turing machine is restricted to taking on the values of 1 (true) and 0 (false). However, in a dynamical system the range of possible values a state variable can realize is not restricted to the values of 0 or 1 but is extended to many possible values. In fact, a state variable can have a numerical state which corresponds to an infinite collection of values. Another feature of a Turing machine is that it operates in discrete-time rather than continuous-time. A dynamical system generates a particular system state at some future time based upon the current system state and current time. Thus, the dynamical system is a mathematical model of a physical machine. Many physical systems are naturally modeled as continuous-time systems rather than discrete-time systems. For example, Newton’s Laws of motion are based upon the concepts of velocity and acceleration which involve the concepts of continuous-time rather than discrete-time. As another example, an electric razor, motorcycle, and sun-powered sundial are examples of machines that are not based upon digital logic and operate using numerically-continuous-states and in continuous-time. Perhaps some types of computers might be naturally represented as continuous-time systems with numerically-continuous-states?
On the other hand, mathematicians and computer scientists have begun exploring more general notions of computation involving systems with either (or both) continuous-time dynamics and numerically-continuous-states. Computations with such machines have been referred to as: Super-Turing computation or hypercomputation. Super-Turing computations and hypercomputations use more general dynamical system computers not representable as Turing machine dynamical systems which are physically realizable as machines but can’t be exactly represented on a digital computer (or Turing Machine). Such dynamical systems are designed to be mathematical models of the physical world and are not limited to symbolic representations that involve IF-THEN rules.
Recent theoretical work by Blum, Shab, and Smale and others is highly mathematical yet suggests that it might be reasonable to extend the current definition of “computable” to go beyond IF-THEN rules. If this was indeed the case, then it would follow that biological computers such as human brains might be capable of computing things which would be impossible using Turing machines or equivalently standard computer technology.
Interestingly enough, in this series of podcasts we will discuss a number of learning machines (some of which are called “statistical learning machines” while others are called “artificial neural networks”) which are capable of physically realizable super-Turing computations. Like biological brains, such statistical learning machines might be capable of super-Turing computations as well.
Still, the concept of “super-turing computation” and “hypercomputation” is not a mainstream topic in computer science and artificial intelligence. The reason for this is probably because one could argue that if one had a Super-Turing Computer which was in principle more powerful than a Turing computer, then the argument is that it should always be possible to approximately simulate the Super-Turing computer on a digital computer. If so, then the computational power of a Super-Turing computer would be reduced to the computational power of a Turing machine since a Turing machine can represent any computation that is implemented on any digital computer! On the other hand, one might argue that this theoretical response is based upon an “approximation assumption” which has not been properly formalized.
So…the bottom line question is that: if one had a Hypercomputer and you programmed a Turing-Machine to simulate that hypercomputer, would you really need the concept of Hypercomputation?
In the next episode we will try to approach the issue of what is computable by computers and biological brains from a more experimental perspective by introducing a procedure for deciding if a machine (the machine can be a Turing machine, a human brain, a human being, an android, or an EARTH) is behaving in an intelligent manner. And then..after doing so…we will discuss the strengths and weaknesses of such a procedure…
[Closing…]
Further Reading:
- The Illustrated Hitchhiker’s Guide to the Galaxy by Douglas Adams
(Harmony Brooks, New York, 1994). [See Chapter 27. Easy reading!!!]. - Charles Petzold. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine (a little advanced but fun to skim) (Wiley, 2008).
- What is Gödel’s Theorem? (Henriksen, 1999, Scientific American) http://www.scientificamerican.com/article/what-is-Gödels-theorem/
- The Wikipedia article on Hypercomputation. http://en.wikipedia.org/wiki/Hypercomputation
which is relatively readable. - Blum’s review of his work on SuperTuring Computation which is very relevant to this discussion: http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf
(still pretty hard to understand but easier than reference 6). - Blum, L., M. Shub, and S. Smale, “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”, Bulletin of the AMS, Vol. 21, No.1, 1-46 (July 1989) [This is a super-duper difficult article which is pretty much impossible to understand in its entirety unless you have at least one PhD in Math but its still important so it’s worth staring at while you kick back with your favorite beverage. As you stare at the article, you can ponder whether or not its worthwhile to get a PhD in Math!!!]
Copyright Notice:
Copyright © 2014 by Richard M. Golden. All rights reserved.
