Notes
2025/09/13
Here's a sketch for a two-player game: One person writes a function in a simple programming language with nothing but strings and if-then-else statements, the other person then looks at the program and has to come up with a value that, if used as the argument of the function, is also the return value of the function. If it's not possible to come up with such a value, the person who wrote the function wins.
For example, let's say player 1 came up with the following function:
def f(x):
if x == "foo":
"bar"
else:
"baz"
Now player 2 has to come up with a value x so that x is the same as f(x). The value "foo" wouldn't work, because f("foo") is "bar", but the value "baz" would work, because f("baz") returns "baz".
Let's consider a more interesting case:
def f(x):
if x == "foo":
"bar"
else:
"foo"
Is it possible for player 2 to win the game by coming up with a value so that x is f(x)? It doesn't seem that way, because f("foo") returns "bar", but f("bar") returns "foo". In a way, the function is adversarial, because no matter whether player 2 picks "foo" or "bar" as their prediction, the function always returns exactly the other value.
The last function is conceptually similar to the halting problem. To show why there is no general algorithm that could decide whether an arbitrary function halts or loops forever, let's assume that we had a function h that takes another function f as its argument and returns "halts" if f halts and "loops" if f doesn't terminate. We could then write the following function:
def f():
if h(f) == "halts":
while true:
# loop forever
else:
"halts"
The function f just does the opposite of what h predicts f will do: If h(f) predicts that f halts, it loops forever, otherwise it just terminates and returns the value "halts". This contradicts our assumption that h is a general algorithm that decides correctly whether an arbitrary function halts, it follows that there can be no such function h, the halting problem is undecidable.
(The above is just a sketch of the proof, an actual proof usually proceeds by diagonalization, so that no explicit self-reference is necessary. Still, it uses the same principle of constructing a case that we could describe as similar to our adversarial "foo"/"bar" function above.)
Making a prediction about a function that self-recursively refers to this very prediction leads to similar paradoxes as time travel, such as the grandfather paradox:
A common example given is a time traveler killing their grandfather before their parents' conception, thus preventing the conception of themselves. If the traveler were not born, they could not kill their grandfather; therefore, the grandfather proceeds to beget the traveler's ancestor who begets the traveler. This scenario is self-contradictory.
If we squint a bit, we can view our prediction game as a game about time travel, because a winning value x must form a closed time loop in respect to f so that “sending” the value into the past and “through” f returns the same value x in the future.
The example function that returns "bar" if x is "foo" and else "foo" is thus similar to the grandfather paradox, because neither "foo" nor "bar" are valid predictions on their own. But could we change the rules of the language in such a way that a prediction is made possible?
Well, why not embrace the paradox and say that a valid prediction for x is "foo" and "bar"? Our prediction for x is, in other words, a value that is both "foo" and "bar" at the same time, written as "foo" & "bar". We will call & a “paradoxical and”, not to be confused with the boolean and that most languages provide.
When a paradoxical value is involved in a comparison such as ("foo" & "bar") == "foo", the if-then-else construct returns the result of evaluating both branches connected as a paradoxical &:
# evaluates to `"foo" & "bar"`
if ("foo" & "bar") == "foo":
"bar"
else:
"foo"
This brings us to the real point of the prediction game: Player 1 still needs to come up with a function for which player 2 has to find a value so that x equals f(x), but player 2 can now extend the rules of the language at the beginning of the game, by for example adding a construct like the paradoxical & operator and fully specifying how it behaves.
The new rules must be extensions: Player 1 must still be able to write normal functions that do not use any paradoxical operators, but player 2 is free to make predictions that involve paradoxical values using the rules that have been determined at the beginning of the game. Similarly, player 2 is free to use paradoxical values and operators when writing the function.
Coming up with good rules is harder than it looks, because if player 1 is free to use paradoxical values while writing their function, they can try to block paradoxical predictions by simply returning normal values in such a case:
def f(x):
if x == ("foo" & "bar"):
"bar"
else:
"foo"
Is it possible to come up with a language that makes it possible for player 2 to always make a valid prediction, no matter which function player 1 comes up with? To design a language that can express the fixed point where x is f(x) as a value for arbitrary functions, even if that value might necessarily be paradoxical?
One last note on recursion, because all of the previous examples have been expressed in terms of a function with one argument and the goal of the game was to find the fixed point, in other words, the value where x equals f(x). All of the previous examples could also have been defined directly using recursion, as follows:
def f():
if f() == "foo":
"bar"
else:
"baz"
This makes it easier to see the parallels with time loops and time travel, because f() clearly loops! But that's also the problem, because we're so used to thinking about f() as obviously never terminating that it's hard to even talk about what a value such as "foo" & "bar" could mean in this example.
So that's the point of stating it as a game. One that is superficially about taking turns and making predictions, but actually about recursion and how inconsistent solutions to fixed points could look like.