Category: Computation

The paper “On computable numbers, with an application to the Entscheidungsproblem” by Alan Turing was published in 1936 and in addition to having a really cool title is a cornerstone piece of computational theory. Before we get to the paper, though, first we need to go over a a bit of background.
The Entscheidungsproblem was proposed by David Hilbert in 1928.

Hilbert asked if it was possible to create an algorithm that would take as input a statement in a formal language and answer whether that statement was true or false. In other words the algorithm would provide an answer as to the decidability of the inputted statement. Entscheidungs is German for decision and Hilbert was German himself, and so entscheidungsproblem was the term given to his question. This was all in parallel and partly in response to Russell and Whitehead’s work on the Principia Mathematica in the earlier part of the century. It appears that Hilbert believed that the answer to his question would be yes and set about trying to create a foundational system that would meet his requirements. This effort in mathematics was known as the Hilbert Programme.
The main goal of Hilbert’s program was to provide secure provable foundations for all of mathematics. Hilbert proposed the creation of a finite, complete set of axioms, and provide a proof that these axioms were consistent. Hilbert then further proposed that the consistency of more complicated systems could be proven in terms of these simpler systems. The basic steps for doing this would include:

1. There would need to be formalization system for all of mathematics. Every mathematical statements should be able to be written in this formal language. This formal language would need to be able to be manipulated according to well defined rules. (No step such as–“and then something magic happens.”)
2. Completeness: There would need to be a proof that all true mathematical statements can be proven in the formal system.
3. Consistency: The formal system would need to be consistent with itself. This means that there would need to be a proof that no contradiction can be obtained in the formal system of mathematics.
4. Conservation: There would need to be a proof that any result about “real objects” obtained using reasoning about “ideal objects” (such as uncountable sets) can be proven without having to use ideal objects to obtain the proof.
5. Decidability: This gets to the well established rules. To satisfy this requirement there should be an algorithm for deciding the truth or falsity of any mathematical statement within the formal system.

In 1931, Kurt Gödel produced the paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”, Monatshefte für Mathematik und Physik, 38: 173–198. Here’s a link to an english translation–On formally undecidable propositions of Principia
Mathematica and related systems. This is another truly amazing paper and I may do a whole post about it sometime. For now, lets just summarize and say that it deals with points 1 – 4 above. Basically, Gödel showed that in any system of mathematics sufficiently powerful to describe itself it was possible to create propositions that were inherently contradictory. The propositions may be thought of as being of the form “This statement is false.” In particular, Gödel used a very clever technique to encode propositions in a formal language into numbers. These numbers are called Gödel numbers. Gödel didn’t, however, say anything about the decidability question. That (finally) brings us to Turing in 1936.
Continue reading On “On computable numbers, with an application to the Entscheidungsproblem”

In an earlier post on Project Euler I mentioned that I was using the problems from the project as one way of picking up the language Scala.
Scala is quite interesting. It is a new language, but it utilizes the Java VM to run upon (Scala compiles to bytecode). This cool idea lets a programmer take advantage of the plethora of Java code that is already out there and call it quite easily from a Scala program.
Scala is object oriented, but more importantly (otherwise just use Java) Scala is a functional language. Every value is a object, and every function is a value. The syntax lets you do things in either a way that seems natural to someone who has been programming in Java (or C) or in a much more succinct functional style.
For example, the first problem in project Euler is to add all the natural numbers below one thousand that are multiples of 3 or 5.
A simple way of doing this in Java would be:

int accum = 0;

for (int i=1; i <= 1000; i++) { if ( i % 3 == 0 || i % 5 == 0) accum += i; } System.out.println(accum);
This is a pretty straightforward rendering of the problem.

In Scala we could do something like:

println( (1 until 1000).filter(n => n%3 == 0 || n%5 == 0).foldLeft(0)(_+_) )

This looks kind of odd on first glance, but it is really doing something similar to the java example.
(1 until 1000) defines the range of numbers from 1 to 1000. until is a method in this case, producing a Range. The filter method is then called, on that Range instance and selects all of the elements that satisfy the predicate (n%3 == 0 || n%5== 0) or in other words, all the elements that are divisible by 3 or 5. On this new Range, we then call foldLeft. This takes a starting value of 0 and applies the function "+" to successive elements (remember + is a value too). The result is then printed.
In this example, the Java code was pretty simple, so the advantage of using Scala may not be immediately apparent. It is kind of fun though. I'll share a more complex example later.

Project Euler is a site that presents a series of programming/mathematical problems. The Euler part comes from Leonhard Euler, a Swiss mathematician.
All of the problems are designed so that a correct implementation can arrive at a solution in 1 minute or less. Sometimes the obvious (brute force) solution might take a very long time indeed. This means that a “correct” solution needs to be correct in both answer and performance.
I’ve done the first 158 out of 321 problems so far. New problems are added periodically. I’ve been using the problems as a way to learn the Scala language. That’s been working out fairly well.

I found the internet reaction to Deolalikar’s proposed proof that P<>NP (
Deolalikar’s P vs NP paper)
fascinating. The paper is interesting in and of itself (if you like computational theory).
The massive number of notes and proof examination that the internet allowed was, to put it succinctly, really cool.

Edit:8/9/2012:
There hasn’t been much activity on this paper for quite some time. It would appear that it was a nice try, but contained several key errors. See the above link to a number of references.

Edit:7/16/2013:
Here is a link for the latest discussions on this. Essentially, there continue to be deep questions about the viability of the proof but there are many interesting areas that may be exposed.