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.