Computer programs are all alike: they take an input and return a result. Each deterministic program calculates the result in its own way, but it always associates the same result with the same input. Non-deterministic programs are upside down: given the same input, different executions of the same program can return different results.

A calculator usually implements a deterministic program: if you type 3+2, the result will always be 5. Now imagine, instead, a calculator that decides, from time to time and on your behalf, which operation to perform on the numbers you type on the keyboard. On Wednesday afternoon, you press 3, 2, and then enter, and the calculator returns 5. You press 3, 2, and then enter on Thursday morning, and the same calculator returns 6. And the calculator is not broken; it simply performed the sum of 3 and 2 on Wednesday afternoon, while on Thursday morning it performed the product of 2 and 3. There you have it: this calculator implements a non-deterministic program. Given the same input (the pair of numbers 3 and 2), it randomly selects which operation to perform on them. Perhaps a silly example, but quite clear. Well, this calculator is probably not very useful, but in certain cases a program capable of performing different operations, randomly selecting which one to perform each time, can be extremely useful.

One of the simplest classic examples is the quicksort algorithm for sorting lists of numbers. The algorithm works roughly as follows. The input is an unordered list of numbers, such as:

“3,7,12,2,3,1”.

The result will be a list containing the same numbers but ordered from smallest to largest. In this case, “1,2,3,3,7,12”. To do this, the algorithm splits the list into two shorter lists, one containing the small numbers and the other containing the large numbers from the previous list. For the moment, let us suppose that a number is small if it is less than 7 and large otherwise. We will return to this choice, which is currently unmotivated, later on. Splitting the previous list in two, we obtain:

“3,2,3,1” and “7,12”.

Notice that the numbers are not yet sorted; they have merely been included, one by one, in one of the two lists in the same order in which they appeared before. The resulting lists are split again into small numbers and large numbers, once more choosing a definition of small and large: “3,2,3,1” is split, for example, into “2,1” and “3,3”, if we consider every number smaller than 3 to be small; and “7,12” into “7” and “12”, if we consider every number smaller than 12 to be small. So now we have:

“2,1”, “3,3”, “7”, and “12”.

If we also split the last remaining lists that contain more than one element, we obtain the following six lists, each containing one element:

“1”, “2”, “3”, “3”, “7”, and “12”

which, when concatenated in that order, give us the desired list:

“1,2,3,3,7,12”.

Now, the secret to quickly sorting a list with quicksort lies in choosing a good definition of small number and large number whenever a list has to be split in two. The first time we did this, we chose to divide large and small numbers with respect to the number 7. In general, we would like this division to ensure that, whenever we split a list, we split it into two lists of similar length: approximately half the length of the list being split. To choose a number that is certain to produce this kind of division, we would already have to have sorted the entire list. But that does not help us, because if we have already sorted the list, we do not need quicksort at all. Enter non-determinism: to efficiently choose a number that separates large numbers from small numbers, we can randomly select a number from the list. Without knowing anything about the order of the list, a random choice gives us an excellent chance of splitting lists effectively most of the time.

It is important to note that quicksort is not, overall, so to speak, a non-deterministic algorithm. In fact, given the same input list, we will always obtain the same sorted list as output. However, within a program that implements the algorithm, it is useful to use a non-deterministic subprogram that randomly chooses a number to separate small numbers from large numbers. Examples of programs that are non-deterministic overall can be found, for instance, in artificial intelligence. Although many programs developed through machine-learning processes are deterministic, a program’s behavior during learning is inherently non-deterministic. Machine learning consists precisely of a process of gradually modifying the way a program responds to the inputs it receives. This modification aims to make the program’s outputs progressively closer to ideal outputs and therefore entails that, as learning proceeds, the program returns different—hopefully better—results in response to the inputs it receives. Some programs, moreover, are developed with the idea of keeping their learning functions active even during use, and not only in preparation for actual use. Two famous examples are the virtual assistants Alexa and Siri. These systems constantly make use of data concerning their interactions with the user in order to provide answers that are progressively more consistent with the user’s own expectations. If the same thing is asked of these systems at different times, therefore, they may give different answers. Systems for selecting which advertisements should be shown to users on certain social networks are also continuously learning. The parameters for selecting advertisements are updated with every user action so that, in the future, advertisements more closely aligned with that user’s interests can be selected.

A different use of non-deterministic programming techniques, on the other hand, can be found in some of ChatGPT chatbot’s functions. The way ChatGPT formulates its responses to the user is based on a complex process of selecting the word that is most likely to follow the series of words making up the conversation between ChatGPT and the user. In other words, at the heart of ChatGPT there is an extremely complex and efficient mechanism for finding the most obvious word that could be uttered after what has been said. This basic mechanism is probabilistic, but deterministic. That is, although the mechanism is based on calculating the probability that certain words may occur in certain conversations, given the same reference conversation, the calculation will always be the same, the calculated probability will always be the same, and therefore the word chosen by ChatGPT will always be the same. Almost always, at least. In fact, the possibility of increasing ChatGPT’s temperature—temperature, in English—makes it possible to configure the program so that the returned answer is not always the most probable one, but is selected non-deterministically from among the most probable ones. This is supposed, they say, to introduce a little creativity into ChatGPT. Now, whether the ability to create new things consists in doing the same thing that has always been done, but in two or three slightly different ways, and then tossing a coin to choose randomly among the results obtained, is not for me to say. The fact remains that the creative version of ChatGPT is an excellent example of a non-deterministic program.

Francesco A. Genco

(translated by MIRAI)