Non-termination without loops, iteration or recursion: Omega in Javascript

Javascript is a great vehicle for teaching functional programming techniques and the lambda-calculus.

The lambda-calculus, which forms the theoretical basis for programming languages like Lisp and Scheme, is also present in Javascript thanks to its support for anonymous functions.

At first glance, anonymous functions seem like merely a syntactic convenience. This article demonstrates otherwise by creating a non-terminating program entirely out of anonymous functions. In the functional programming community, this expression is known as omega.

Related pages:

The program omega is made up of two functions which each take one argument. Each of these functions applies the argument to itself. Omega is then the application of one of these functions to the other:

var omega = (function (f){f(f);})(function (g){g(g);}) ;

Trying to evaluate this code fragment will hang the browser until it decides to terminate the script.

The means by which omega achieves non-termination is self-application, and self-application turns out to be the theoretical source of power for the computational universality of the lambda-calculus.

(Self-application creates a number of issues needing careful handling for logical theories based on the lambda-calculus, but these aren’t a concern when the lambda-calculus is used as the basis of a programming language.)

More specifically, self-application allows the construction of fixed combinators, such as the Y combinator, and these permit the construction of recursive functions without explicit support for recursion.

I’ve also created an article demonstrating the Y combinator and showing how it can be used for memoizing recursive functions.

Related articles