compsci: Simple illustration of halting problem (from SICP)

The halting problem asks whether we can write a general function halts(fn) that returns whether or not a given function would ever halt.

If halts(fn) existed then the following would prove it can't work:

fun strange(fn) =
  halts(fn)
    ? spinForever()
    : "done"

Notice that strange(strange) is a contradiction!

• if halts(strange) returns true then strange never halts
• if halts(strange) returns false then strange immediately halts