“I feel sure that I shall meet Morcom again”

Thurs 13 Feb 1930, Alan Turing’s first (and unrequited) love Christopher Morcom died. Turing was 17. “I feel sure that I shall meet Morcom again somewhere and that there will be some work for us to do together…” (Hodges, 1983/2014, pp. 61-62):

Dear Mother,

I wrote to Mrs Morcom as you suggested and it has given me a certain relief. […] I feel sure that I shall meet Morcom again and that there will be work for us to do together, and as I believed there was for us to do here. Now that I am left to do it alone I must not let him down but put as much energy into it, if not as much interest, as if he were still here. If I succeed I shall be more fit to enjoy his company than I am now. I remember what G O’H said to me once ‘Be not weary of well doing for in due ye shall reap if ye faint not’ and Bennett who is very kind on these occasions ‘Heaviness may endure for a night but joy cometh in the morning’. Rather Plymouth brotherish perhaps. I am sorry he is leaving. It never seems to have occurred to me to try and make any other friends besides Morcom, he made everyone seem so ordinary […].

References

Andrew Hodges (1983/2014). Alan Turing: the Enigma. Princeton University Press.

The Halting Problem in R

It’s possible to write a program that peeks at another program and tells you something about it. Here’s an R function that tells you how long the definition of a function is:

library(stringr)

function_length <- function(func) {
  body(func) |>
    as.character() |>
    str_length() |>
    sum()
}

It can even be applied to itself: function_length(function_length) happens to be 42.

It might be handy to have an R function that tells you whether a function terminates in finite time, returning TRUE if it does and FALSE if it runs forever. Something like this, with magic in the ellipsis to make it work:

terminates <- function(f) {
  if (...)
    TRUE
  else
    FALSE
}

For instance, consider this function:

is_a_loop_is_a_loop <- function() {
  while (TRUE) {}
}

Calling terminates(is_a_loop_is_a_loop) should return FALSE, since it has an infinite while loop.

The challenge of finding such a function is known as the halting problem. It turns out that there is no general function – a result due to Alan Turing (1937).

Here is an R version of Christopher Strachey’s (1965) proof, inspired by a proof Turing told him verbally “in a railway carriage on the way to a conference” in 1953.

Suppose for the sake of argument that terminates does exist, with the ellipsis above filled in, and that it works as we hope.

Now, define another function, taking_the_p, as follows:

taking_the_p <- function() {
  if (terminates(taking_the_p)) 
    while (TRUE) {}
}

The argument has a Russell’s paradox flavour to it.

Suppose terminates(taking_the_p) is TRUE. Then the if statement will dutifully trigger an infinite loop, meaning that taking_the_p doesn’t terminate. So terminates got it wrong. Suppose taking_the_p does actually terminate. That means terminates(taking_the_p) must have returned FALSE – again it was wrong.

But we started the proof by assuming that terminates actually works. Contradiction. Therefore there is no general function terminates.

There are countably infinite computable functions. The terminates function is an example that is not computable.

This general result does not mean it is never possible to determine whether a function terminates. There’s an easy heuristic: run a function for a bit and if it hasn’t finished after a period of time, decide that it doesn’t terminate. It’s far from the general solution, but for what it’s worth here’s the R:

library(R.utils)

terminates <- function(expr, secs = 1) {
  terminates <- FALSE
  res <- NULL
  try({
    res <- withTimeout(expr,
                       timeout = secs)
    terminates <- TRUE
  }, silent = TRUE)

  terminates
}

Note that this takes an expression rather than a function, so that it easily applies to functions of any arguments.

Let’s try two examples: the identity function (which simply returns its argument) applied to itself, and is_a_loop_is_a_loop. For the latter, note the empty parentheses, (), which is how to ask R to run a function rather than inspect it.

terminates(identity(identity))
# [1] TRUE

terminates(is_a_loop_is_a_loop())
# [1] FALSE

The timeout is doing the heavy lifting. I have chosen 1 second, which would rule out a large number of functions that do terminate.

References

Strachey, C. (1965). An impossible program. The Computer Journal, 7(4), 313–313.

Turing, A. M. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(1), 230–265.

GCHQ’s director’s Turing speech – a research team manual?

Just read the (4 Oct 2012) speech about Alan Turing, given by Iain Lobban, Director GCHQ, at the University of Leeds.

Fantastic stuff in there. Here are some excerpts.

On learning to solve problems

“… [Turing] reported to Bletchley Park as agreed and immediately started working with [Dilly] Knox [expert on the Enigma cypher …]. Knox’s influence on Turing at this time is immense. The older veteran cryptanalyst shared everything he knew about Enigma with Turing, who eventually used this knowledge to write the first four chapters of his treatise on Enigma […]

“…[Turing] was happy to learn from Dilly Knox, happy to use that knowledge as the foundation for what he would develop subsequently, and was diligent in recording what he had learned and how he developed that into new areas so that others could profit from his knowledge just as he had profited from that of Knox.”

Knox could only take Turing so far and his quest for experience-based understanding of the cryptanalysis of Enigma took Turing to France in January 1940…”

Team work

There are lots of different ways in which people can work as part of a team.  Turing’s way was to take in other people’s ideas, develop and build on them, and then pass the product on to other people to be the foundation for the next stage.  He took the idea of electromechanical processing of Enigma messages from the Poles but developed their idea into something radically different.  When Welchman later enhanced the Bombe with his diagonal board, Turing was among the first to congratulate him on this major improvement.  Turing was part of the team, and shared in the success of the team.”

Respecting diversity

“I strongly believe a Sigint agency needs the widest range of skills possible if it is to be successful, and to deny itself talent just because the person with the talent doesn’t conform to a social stereotype is to starve itself of what it needs to thrive.”

“I don’t want to pretend that GCHQ was an organisation with twenty-first century values in the twentieth century, but it was at the most tolerant end of the cultural spectrum.  In an organisation which valued the skills and characteristics that difference can bring, Turing’s homosexuality was less of a talking point than his insights into the complex crypt problems of the day.  When he was put on trial, Hugh Alexander, the Head of Cryptanalysis at GCHQ went, with official approval, to speak as a character witness on his behalf, saying in court that Turing was a national asset.”

Exploiting serendipity

“Geoffrey Tandy was posted to Bletchley by the Admiralty in a spirit of helpfulness: his posting officer had understood him to be an expert in cryptograms, a word still used in the Admiralty at that time to mean messages signalled in code.  In fact he was an expert in cryptogams: non-flowering plants like ferns, mosses and seaweeds.  But while this knowledge might not have appeared to be of much use, Tandy became expert in German naval Enigma and because of his work on seaweed was able to provide unique advice on the preservation of cryptologic documents rescued from the sea.”

The role of management

“Part of my job is to continue to foster that atmosphere: to attract the very best people and harness their talents, and not allow preconceptions and stereotypes to stifle innovation and agility.”