Turing, Leibniz and Hilbert’s Entscheidungsproblem

Alan Turing. This image is in the public domain in the US because its copyright has expired.

Alan Turing. This image is in the public domain in the US because its copyright has expired.

What’s the first thing you think of when you hear the name Gottfried Leibniz? Let me guess: calculus.  Now what do you think when you hear of Alan Turing?  You might think of codebreaking during World War II, or the new movie coming out about him (The Imitation Game), or maybe you haven’t heard of him.  So why would I mention these two together? Computers of course! Wait, what do these two have to do with computers? Well let’s take a look and see.

The Entscheidungsproblem origins start with Gottfried Leibniz in the seventeenth century.  Leibniz had successfully created a mechanical calculating machine, one of the first of its kind.  This calculating machine led him to question if a machine could be made that could determine the truth values of mathematical statements.  In his research, he found that one would have to find a formal language to create this machine.  In 1900, David Hilbert, a German mathematician, included the following in his 23 unsolved (at the time) problems designed to further the disciplines in mathematics:

“10. Determination of the solvability of a Diophantine equation.  Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. (Winton Newson’s translation of HIlbert’s original problem, as quoted in D. Joyce)”

By 1928, Hilbert had broadened his question about Diophantine equations to a much more general question about mathematical statements in general: is there an algorithm that is universally valid. This created a new idea; is there an algorithm that can tell us if any algorithm will terminate?  The last of these three ideas was the beginning of the Entscheidungsproblem. In May, 1936 Alan Turing wrote a paper called “On Computable Numbers, with an Application to Entscheidungsproblem.”  In this paper, Turning reformatted Kurt Godels results on the limits of proof and computation.  He made a hypothetical device known as the Turing machine and went on to prove there was no solution to the Entscheidungsproblem.  He did this by using his Turing machine to show that the halting problem is undecidable; that it is impossible to know whether a program will finish running or continue forever.

The Turing machine itself can represent a computing machine.  It can change symbols on a strip of tape based on a set of tools.  A Turing machine has 3 main components, the first being an infinite tape. This infinite tape would be divided into cells in which a symbol can be placed.  In the tape there would be a head.  The head accesses one cell at a time, while moving either right to left or left to right.  The third component would be a member were there would be a fixed finite number of states.  After having these three components you have three actions: 1) write a symbol, 2) move either left or right, and 3) update its current state.  The formal definition of a Turing machine is defined as a 7-tuple.  The seven elements of the tuple would be as follows: a set of states, an input alphabet, the tape alphabet, the start state, a unique accept state, a unique reject state, and a transition function.

A Turing Machine, without infinite tape. Image: Rocky Acosta, via Wikimedia Commons.

A Turing Machine, without infinite tape. Image: Rocky Acosta, via Wikimedia Commons.

Turing’s work on the Entscheidungsproblem and the Turing machine can be thought of as the birth of computer science and digital computers.  During World War II the idea of the Turing machine was used and manipulated into a simpler form, as well as into an actual electronic computer.  This led to machines such as the counter machine, register machine, and random access machine.  All of these machines launched us even further into the computer era.

It is interesting to see that the birth of the modern computer came from the Entscheidungsproblem, an idea that Leibniz had first thought of.  Why would I think this is interesting?  Leibniz had also worked on binary numbers and arithmetic, which is similar to what is used today in modern computing. It seems that Leibniz was ahead of his time.  Alan Turing seems to have just taken his ideas and brought them to our times.  We can see that without Turing we wouldn’t have modern computers the way they are. This means we wouldn’t be able to do any math that requires a computer to help with computations.  Think, how many times have you used your computer to access the Internet to get the answer to a math problem you were unable to solve? Not only that, but studying math wouldn’t have been as easy.  Knowledge that is passed through the Internet wouldn’t be possible without computers, with no YouTube to help show how to solve math problems, with no Khan Academy or Wolframalpha, and no easy access to any knowledge of any past essays that were written.

Sadly, Turing’s end wasn’t a happy one.  Living in England in the early 20th century as a gay man led him to commit suicide.  Leibniz lived almost twice as long as Turing.  It makes you wonder if we could have had even more interesting computing machines or ways of thinking of computational mathematics if he had lived a full life past the age of 41.

Sources

History on Turings life – http://www.math.rutgers.edu/courses/436/Honors02/turing.html

Hilberts Problems – http://aleph0.clarku.edu/~djoyce/hilbert/problems.html http://mathworld.wolfram.com/HilbertsProblems.html

Turings paper “On computable Numbers, with an application to the Entscheidungsproblem – http://plms.oxfordjournals.org/content/s2-42/1/230.full.pdf+html

Gottfried Wilhelm Leibniz on wikipedia – http://en.wikipedia.org/wiki/Gottfried_Wilhelm_Leibniz

Wikipedia article on the Turing Machine – http://en.wikipedia.org/wiki/Turing_machine

Advertisements