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.