Editorial: Decisions, Decisions

Previously we considered how to learn a, possibly non-existent, programming language. This clearly pre-supposes we understand what a programming language is. Upon realising I only had a couple of weeks to get an editorial together, and as ever, with no opinions to share or muse on, I decided to spends hours wondering what a programming language actually is, and furthermore, what constitutes a computer program.

Opinions seem to vary. Some people do not regard VB, VBA or Excel as ‘proper’ programming, while others get upset by this viewpoint. What about mathematics or statistics packages, such as MatLab or R? They can include data structures and ways of controlling the flow of execution. They allow one to issue instructions to a computer. This seems ‘programish’. Of two colleagues at work, one does not regard R as programming since it is very high-level compared to his roots, programming in assembler. Another does regard R as a proper language, though paused for a while when I asked what the difference between using a program and writing a program was. It seems there may be a difference between a tool for getting a job done, and the building blocks for making such a tool. Ignoring the obvious emotive nature of such discussions, we can broaden this out from maths and stats packages. Is Markup a language? It seems strange to regard XML as a programming language, but XSLT almost certainly is, since it is Turing complete [Kepser]. In other words, it can ‘compute every Turing computable function’. [Turing_completeness] That was helpful, wasn’t it? Equivalently, it can simulate a universal Turing machine. Some may argue that nothing can simulate a universal Turing machine, since such a machine has infinite memory and is indestructible, but let us leave aside such practical details.

Returning to our original question, ‘What counts as a programming language?’, it might ironically be possible to regard an attempt to create a mathematics package as building the foundations of programming. Whether this means mathematics packages count as programming languages is a matter for further discussion, but for now let us consider a little history. Quite early in his career, David Hilbert published a book establishing a foundation for geometry, demonstrating that its axioms, based on Euclid’s, were consistent, in other words it does not contain or give rise to a contradiction. Why does this matter? If you start with a contradiction, you can prove anything. ‘Ex falso, quodlibet.’ From falsity, whatever you like. For example, assume A and !A, for some statement A. Formally, using & for ‘and’, ! for ‘not’, | for ‘or’ and => for ‘implies’,

A & !A => A        (1)

and similarly

A & !A => !A         (2)

by definition of &.

From (1), for any B, such as ‘Unicorns exist’ since A holds, A or B holds:

A | B        (3)

by definition of |.

From (2), !A, (3) => B, by definition of | (if A or B is true and A is false, B must be true)

From our original assumption, A & !A, we have deduced B, formally

A & !A => B

that is unicorns exist, or whatever we chose for B.

Hilbert would not be impressed. Later, he gave a major address to the Second International Congress of Mathematics in August 1900. In his speech he mentioned 10 unsolved mathematics problems, though the published version went on to list 23. He said,

This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call. There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus. [Hilbert]

His second problem called for proof of the consistency of the real numbers, which he had rather assumed in his earlier geometry book. The tenth problem called for someone to ‘Devise a process according to which it can be determined by a finite number of operations whether the [Diophantine] equation is solvable in rational integers’ [Hilbert]. The full set of twenty three problems can be readily found, for example see Wikipedia [Hilbert’s_problem]. A curious point to note is a mathematician asking for a process or algorithm, rather than an answer. We here see the beginnings of what is now known as Hilbert’s Programme; an attempt to formalise mathematics in axiomatic form together with a proof of its consistency and completeness, including no superfluous axioms, and with every well-formed formula being ‘decidable’ that is provable or falsifiable. This would allow all of mathematics to be deduced from the axioms. In 1928, Hilbert generalises these ideas and questions to the Entscheidungsproblem – the decision problem. Can you devise an algorithm which concludes whether a correctly formed statement is deducible from a set of axioms? Over time, people engaged with the problem, and some dream of devising a procedure that could be carried out by a machine. The quest to put mathematics on firm logical foundations had started a quest for the ultimate mathematics package.

In 1936 Alonzo Church and Alan Turing both published separate papers showing there can be no general solution to the decision problem. Church used his λ-calculus [Church] and Turing invented his Turing machine [Turing]. Turing’s paper is only 36 pages long but ground-breaking. He introduces the idea of an automatic machine, which can read a symbol at a time from a tape, alter or erase the symbol, move the tape (or read head) and write further symbols. In conjunction with a state register, which stores one of finitely many states, and a table of instructions mapping states to symbols, we have a Turing machine. Some of the instructions for a given state and input symbol involve moving the tape which reads almost exactly like a goto. Taking the automatic machine a step further, Turing moves on to describe a universal machine, U, which is supplied with a tape containing the instructions and initial state of an automatic machine, M. U will then compute the same sequence as M. Furthermore, it can be given the instructions for any automatic machine M. As noted, this gives it infinite memory and assumes the machine and tape never break, nonetheless imagining a machine that can be instructed, or programmed, rather than building a special purpose machine for each and every problem is a revolutionary idea.

Turing’s paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it. [Minksy]

Turing’s paper is quite difficult to read, so on my second attempt I opted for Petzold’s The Annotated Turing [Petzold] which weighs in at 372 pages, making it just over ten times the length of the original paper and Petzold’s shortest book. He tells us:

I have sometimes tried to write 300-page books. I would very much like to write a 300-page book. But I have always failed. [Petzold2]

At least he has made an effort.

Unfortunately, Church and Turing had both scuppered Hilbert’s programme (there’s that word ‘program’ again). They had both been influenced by the earlier work of Gödel, from 1931, which burrowed down into the requirements for consistency and completeness. Many people refer to Gödel’s incompleteness theorem, but it should be noted there are two. The first shows that for any consistent axiomatic system capable of describing the natural numbers, there are true statements which the system cannot prove. At a high level, this is demonstrated by encoding ‘This statement is not provable’ within the system. If the system can prove that statement it means it cannot prove that statement. If it cannot prove that statement, this proves it can prove the statement. Either way it is inconsistent. A consistent system cannot therefore be complete. The second theorem shows that any such consistent system cannot prove its own consistency. The technical difficulty here comes from describing the consistency of the system within the system, but when you manage that the proof follows almost immediately.

What have we learnt about the nature of a computer program? First, you do not need a computer in order to write a program. Next programming languages have a syntax. Hilbert desired the decidability of a ‘well-formed formula’ in his program. How do you decide if a formula is well-formed? Strict syntax rules pin that down very easily. Gödel’s incompleteness theorems do not apply here, since the syntax checker is external to the program itself. Finally, a program does something. Given its current state and an input, using a list of instructions, it acts: Turing’s machine wrote a 1 or 0, move the tape or erased a symbol on the tape, not thrashing the program but rather keeping its rough working up to date, leaving the program in the next state. It is of course, easier to program if you have a computer, simpler if another program checks the syntax of your program for you, and very satisfying if the program does what was required.

Where does this leave a programmer today? Firstly, with a computer, which must makes things easier than they were for Turing. Secondly, armed with considerably more programming languages than existed half a century ago, confronted by more than a fistful of idioms and a plethora of patterns, a programmer can control MRI scanners, create games, numerically solve hard mathematical problems, but can still never be sure if the program will halt, run out of memory, or behave correctly. Clearly, the decision problem suggests we are, in general, unable to decide if any given program will halt, or contain a bug. Perhaps we must acknowledge ‘ignorabimus’ and uncertainty. I know I certainly couldn’t decide on a suitable editorial topic, and hope you accept my apologies and excuses yet again.

References

[Church] ‘An unsolvable problem of elementary number theory’,American Journal of Mathematics, 58 (1936), pp 345–363, and ‘A note on the Entscheidungsproblem’, Journal of Symbolic Logic, 1 (1936), pp 40–41.

[Hilbert] Quoted by Charles Petzold in The Annotated Turing Wiley, 2008 (see below)

[Hilbert’s_problem] http://en.wikipedia.org/wiki/Hilbert%27s_problems

[Kepser] Stephan Kepser ‘A Simple Proof for the Turing-Completeness of XSLT and XQuery’, Extreme Markup Languages 2004

[Minksy] Computation: Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967.

[Petzold] The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and The Turing Machine’ Wiley, 2008

[Petzold2] ‘The 300 page ideal’ http://www.charlespetzold.com/blog/2008/05/The-300-Page-Ideal.html

[Turing] Alan Turing, ‘On computable numbers, with an application to the Entscheidungsproblem’, Proceedings of the London Mathematical Society, Series 2, 42 (1936–7), pp 230–265

[Turing_completeness] http://en.wikipedia.org/wiki/Turing_completeness