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 a R function that tells you how long 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 otherwise. 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.

It turns out that there is no such general function – a result due to Alan Turing (1937).

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

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 of one 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 most of 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.