Search                        Top                                  Index
HELP HALTS                                                    K. Goedel, 1930


The POP-11 procedure HALTS takes two arguments, a POP-11 procedure and some
other object. The first argument, the procedure, is expected to be a procedure
that takes one argument.  HALTS succeeds if, when applied to the other object,
the computation of the procedure would terminate. Hence:

    halts(pr,"apple") =>
    ** <true>

    define loop(x);
        repeat forever x => endrepeat

    halts(loop, "apple") =>
    ** <false>

HALTS can be used to define some quite useful procedures. For instance,

    define niceproc(x);
        if halts(x,x) then
            repeat forever x => endrepeat

It is left as an exercise to the reader what result is printed out by:

    halts(niceproc, niceproc) =>