Important: This section is intended for those familiar with traditional languages like JavaScript or C.  If you're not already a programmer, skip to the next section, which is written for all audiences.

Let's start with an otherwise “normal” programming language, NDScript¹, that just happens to be clairvoyant.  It's a tiny subset of JavaScript with two new statements: choose and fail.  This will let us look at the value of non-determinism by itself, before we bring in the other kinds of features that are typically packaged alongside it in languages like Prolog.

Decision-making in computers

When a computer “makes a decision,” it generally takes the form of something like an if statement.  There are elaborations on these: switch statements, while and for loops, etc.  But the basic pattern is:

if (condition) {
    // Option 1
} else {
    // Option 2
}

The computer tests whether condition is true.  If so, it chooses option 1, otherwise option 2.  Nearly all programs have these.  But the computer must be able to compute the condition before it can run the if.  So the computer gathers information, then makes a decision:

information → decision

But as we said, many problems only give you the information after you make the decision:

decision → information

Choice and failure

The if statement packages the condition with the choices: you have to put them together.  But what if we could break them apart?  What if we could put the choices first, and then put the condition later in the program, once we've learned the information we need?  That's the basic idea of clairvoyance (aka nondeterminism).  Rather than a single if statement, we have separate choose and fail statements.  The choose statement looks like an if with no condition:²

choose {
    // Option 1
} or {
    // Option 2
}

It tells the computer to guess one of the options and run it.  The fail statement:

fail;

tells the computer that some earlier guess was wrong (not necessarily the last one).  So the basic pattern is:

choose {
    // Option 1
} or {
    // Option 2
}
...
do more stuff, gather more information...
...
if (something_is_wrong) fail;

The clairvoyant contract

NDScript and systems like it promise that when they execute choose they will always guess right.  Or to be more precise, they will never make choices that lead to failure (executing the fail statement).³  So if you write your program to always fail sooner or later for bad choices, then the system will only make good choices.  This is the sense in which it is "clairvoyant." 

Of course, behind the scenes, it does make bad choices and it does fail.  It just hides those mistakes from you: it undoes mistakes and systematically tries choices until it finds a sequence of choices that succeeds (i.e. doesn't fail).  This can mean the program runs very slowly if it's making a lot of bad choices internally.  But the final output of the system looks as if it had always guessed correctly.

Notes