Ori Livson

What NBA Legend Charles Barkley Can Teach Us About Fixed-Point Theorems

The link between questionable statues of Dwyane Wade, incompleteness, recursion, self-replication and super-rationality.

Intro

Diagonalisation arguments have revealed many important limitations throughout mathematics, computer science and logic, e.g., the impossibility of creating certain algorithms (Turing), the necessity of true but unprovable statements for any list of consistent axioms of arithmetic (Gödel), the necessity of indescribable words (Grelling), etc. Fixed-Point Theorems are the other side of the coin to many diagonalisation arguments¹ and underpin recursion in programming as well as results concerning self-replicating programs, self-referential strategies and self-simulation (more on this later).

As part of my research, I am always looking for new examples of diagonalisation and fixed-point theorems, and new ways to motivate the underlying problems and theory. My favourite example as of late is a beautiful fixed-point theorem, hidden in a joke by NBA legend Charles Barkley.

For context, In late 2024, a statue of another NBA legend Dwyane Wade was unveiled that was promptly criticised for looking nothing like the player (see Figure 1 to decide for yourself).

After the unveiling, on a panel show called Inside the NBA, the following debate ensued between two of its hosts Charles Barkley and Kenny Smith - pay special attention to the final line of Charles Barkley.

Kenny Smith “If you made an animated face and then they made a bronze statue [of it], that’s what it would look like.”

Charles Barkley: “If they made an ugly statue, that’s what it would look like. That thing is awful.”

Kenny Smith “It’s not awful. Look, he’s making an animated face, it’s a moment.”

Charles Barkley: “That was after he saw the statue right there! That’s the face he made when he saw the statue.”

(See the full clip in the embedded YouTube video of Figure 2)

The Joke, Mathematically

Let \(\textbf{Face}\) be the set of all possible human faces (including the person behind them) and let \(\textbf{Statue}\) be the set of all possible statues of faces.

Then, let Dwyane Wade’s statue maker be formalised as a function \(depict: \textbf{Face} \rightarrow \textbf{Statue}\).

Furthermore, a reaction to a statue (insofar as it changes one’s facial expression) is given by a function \(react: \textbf{Face} \times \textbf{Statue} \rightarrow \textbf{Face}\).

The function signature of \(react\) reflects that the reaction (a new facial expression) does not only depend on the statue one is reacting to but also on the person reacting to the statue. For instance, the earlier debate between Barkley and Smith shows that different people (i.e., subsets of \(\textbf{Face}\)) may react differently to the same statue.

Thus, a potential formalisation of Charles Barkley’s joke is:

The Dwyane Wade Fixed-Point Conjecture: for any face \(D \in \textbf{Face}\) of Dwyane Wade, there exists another face of Dwyane Wade \(D_{fp} \in \textbf{Face}\) such that: \[\begin{equation*} react(D,\ depict(D_{fp})) = D_{fp} \end{equation*}\]

To reiterate, \(D\) represents Dwyane Wade before seeing the statue of him (i.e., before seeing \(depict(D_{fp})\)), and after he sees that statue, he makes a reaction face (i.e., \(react(D,\ depict(D_{fp}))\)), and that face is claimed to match the face that the statue depicts, i.e., his reaction face matches \(D_{fp}\).

Moreover, \(D_{fp}\) is specifically a fixed-point of the function \(react(D,\ depict(-)): \textbf{Face} \rightarrow \textbf{Face}\).

Although, the above conjecture may only hold for particular initial faces of Dwyane Wade (i.e., one can only find a fixed-point \(D_{fp}\) given the right time, place or mood). It also remains to see whether a fixed-point like \(D_{fp}\) exists for people besides Dwyane Wade.

How the Joke Resembles Godel's First Incompleteness Theorem

In the \(19^\text{th}\) and \(20^\text{th}\) centuries, many logicians and mathematicians strove to establish an ideal, logical theory of arithmetic, from which, all truths about arithmetic on the natural numbers \(\mathbb{N} = \{0,1,2,3,...\}\) could be proven.

To begin, a logical theory simply meant a finite list of axioms (e.g., "for every \(n \in \mathbb{N}\): \(n = n\)") and rules of inference (e.g., if \(A\) implies \(B\) as well as \(A\) are proven, then so is \(B\)).

Moreover, the desired logical theory \(\mathcal{T}\) of arithmetic (e.g., Peano Arithmetic) was expected to be both:

• Consistent - meaning that \(\mathcal{T}\) does not allow any contradictions to be proven.

• Complete - meaning that for every proposition \(P\), either \(P\) is provable or its opposite "\(\neg P\)" (i.e., "not \(P\)") is provable.

In 1931, Gödel’s First Incompleteness Theorem shattered any hope for the existence of such a theory \(\mathcal{T}\) of arithmetic. Specifically, he proved that any consistent theory of arithmetic must be incomplete, and that any compete theory of arithmetic must be inconsistent.

Gödel’s insight came from devising a "statue maker" for the set \(F\) of all formulae of \(\mathcal{T}\) (i.e., of arithmetic), where formulae consist of:

• Propositions - being non-variable statements about arithmetic, e.g., "\(2 > 3\)", which may or may not be true.

• Predicates - being variable statements about arithmetic, e.g., "\(x > 3\)", which may nor may not be true depending on the value of \(x\).

And the statue maker is an algorithm \({}^\ulcorner\ - {}^\urcorner: F \rightarrow \mathbb{N}\) called a Gödel numbering that assigns every formula \(f\) of \(\mathcal{T}\) a unique Gödel number \({}^\ulcorner\ f {}^\urcorner\), and likewise where everyGödel number can be algorithmically translated back into its formula.²

Formula that represent statements about Gödel numbers correspond to statements about mathematics - in mathematics. Moreover, proofs can also be assigned unique Gödel numbers, which reveals that \(\mathcal{T}\) contains formulae that bear on \(\mathcal{T}\)’s own consistency or completeness.

As with the Dwyane Wade Fixed-Point Conjecture, Gödel proves the incompatibility of consistency and completeness by finding a fixed-point to the following predicate:

The above is a mouthful to be sure, but the fixed-point \(G \in F\) of \(\neg Provable({}^\ulcorner\ - {}^\urcorner)\) more concisely yields that:

In other words, within \(\mathcal{T}\): if \(G\) is true then it is not provable (i.e., \(\mathcal{T}\) is incomplete), and if \(G\) is false, then a it, a false statement (i.e., a contradiction) is provable (i.e., \(\mathcal{T}\) is inconsistent).³

The resemblance of the above to the Dwyane Wade Fixed-Point Conjecture becomes clearer if we denote logical equivalence under \(\mathcal{T}\) by \(\equiv\), so that we have \(\neg Provable({}^\ulcorner\ G\ {}^\urcorner) \equiv G\). In other words, the role of \(depict\) is played by \({}^\ulcorner\ - {}^\urcorner\), and the role of \(react\) is played by variable substitution.

Moreover, Carnap’s Diagonalisation Lemma (1934) shows that all predicates \(A(x)\) have a fixed-point in the above sense. The computational version of Diagonalisation Lemma (Kleene’s Second Recursion Theorems) yields many more interesting consequences, e.g., the possibility of doing general purpose programming via recursion (e.g., via the Y-Combinator).

Kleene's Second Recursion Theorem

In the next two sections, we will survey two especially interesting applications of fixed-point theorems of the type of Charles Barkley’s. The first being Quines, which are programs that are able to reproduce their own source code. The second being self-referential algorithms involved in the classic Prisoner’s Dilemma problem.

To formalise these applications, we need a more general fixed-point theorem called Kleene’s (Second) Recursion Theorem (on 1 variable). However, Kleene’s Recursion Theorem has some tricky notation, which is easier to understand if we first explain a simpler result called Roger’s Theorem.

To begin, let \(\textbf{Program}\) be the set of all computable (partial) functions on natural numbers implementable by a general purpose programming language (they are more specifically, Partial Recursive Functions).

Then, consider any transformation \(F\) on programs, i.e., a function \(F: \textbf{Program} \rightarrow \textbf{Program}\). For instance, \(F\) may add extra instructions to programs, replaces existing instructions in a program, etc.

Roger’s Theorem states that for any transformation \(F\), there is always a program \(p \in \textbf{Program}\) that is unaffected by it, i.e., \(F(p)\) is defined on exactly the same inputs as \(p\), and when \(p\) is defined on an input \(n \in \mathbb{N}\): \(p(n) = F(p)(n)\).

However, while \(F(p)\) is functionally equivalent to \(p\), it does not necessarily have the same source code as \(p\) - that is where Kleene’s Recursion Theorem comes in.

Let \(source\) be a function that maps a program to its source code, say a binary representation of it, so that \(source\) is a \(\textbf{Program} \rightarrow \mathbb{N}\) function.

Now, if we take a computable function \(Q: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) instead, Kleene’s Recursion Theorem states that there is a program \(q\) equivalent to \(Q\) applied to \(q\)’s source code, i.e., \(q = Q(source(q), -)\), or equivalently:

Application 1: Quines - Programs That Reproduce Their Source Code

Quines are computer programs that ignore all inputs, and output their source code in a curious act of self-replication. For example, this python program:

c = 'c = %r; print(c %% c)'; print(c % c)

(Verify it by executing it yourself in a python REPL or this online editor)

The existence of a Quine is surprising because it would appear that a program that prints its own source would need to have the following 3 distinct portions of code:

• \(S\) for some representation of the source code of the Quine.

• \(R\) for the code needed to read \(S\).

• \(P\) for the code needed to print \(S\).

So that somehow \(S = R + S + P\) is satisfied, which seems paradoxical.

The existence of Quines (in any general purpose programming language - or more generally, any Turing complete model of computation) follows form Kleene’s Recursion Theorem.

Specifically, let \(Q: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) be the computable function defined by mapping \((x, y) \mapsto x\). By Kleene’s Recursion Theorem, there exists a program \(q\) such that: \[\begin{equation*} \forall\ y \in \mathbb{N}:\ q(y) = Q(source(q), y) = source(q) \end{equation*}\] Hence, \(q\) is a Quine, and importantly, a product of a fixed-point theorem: Kleene’s Recursion Theorem.

Interlude: The Prisoner's Dillema

To derive the next application, we first summarise the classic Prisoner’s Dilemma problem of Game Theory.

The Prisoner’s Dilemma begins with two prisoners being independently interrogated over their joint involvement in a crime.

Each prisoner prisoner has two choices:

• Cooperate (C) with one another, i.e., by admitting nothing about pair’s involvement in the crime.
• Defect (D) from the other prisoner, i.e., by confessing the pair’s involvement in the crime as part of a deal for a favourable sentence (i.e., for themself, not the other prisoner).

The possible outcomes are as follows:

1. If one prisoner cooperates and the other defects, the defector receives the shortest possible (prison) sentence, and the cooperator receives the longest possible sentence.
2. If both prisoner’s cooperate, they both receive an equal, relatively short sentence (but not as short as being the defector in outcome 1).
3. If both prisoner’s defect, they both receive an equal, moderately long sentence (but not as long as being hte cooperator in outcome 1).

All 4 possible combinations of prisoner choices (i.e., (C,C), (C,D), (D,C), (D,D)) can be tabulated in a “payoff matrix”, where the cell values are the prisoners’ sentences - see Figure 3 below for example sentencing values.⁴

In the 1950’s, John Nash famously introduced the argument that a rational prisoner ought to always defect in classic Prisoner’s Dilemma problem, i.e., where they play once without any further communication or consequences besides their final prison sentence.

The reason is that mutual defection is the problem’s Nash Equilibrium, meaning that it is the only pair of choices where neither side would gain by changing their mind upon knowing their opponent’s decision.

Specifically, if prisoner 1 is considering defection, and somehow finds out their opponent will cooperate, it still does not make sense for prisoner 1 to change their mind because that would increase their sentence (e.g., from 1 to 2 years per Figure 3). The same is true if prisoner 1 considers defection and finds out their opponent is also considering defection (e.g., switching to cooperate raises the sentence from 5 to 10 years per Figure 3).

However, both prisoners abiding by this logic and mutually defecting leads to a worse outcome than mutual cooperation. Hence, it is of great interest to find out how and when mutual cooperation is achievable… Or at least methods for cooperating without falling prey to an uncompromising defector.

Application 2: CliqueBot and FairBot - The Self-Referential Robot Prisoners

How might we transcend the pitfalls of the Nash Equilibrium of the Prisoner’s Dilemma? Douglas Hofstadter (of the famous Gödel Escher Bach) envisions an argument called super-rationality, which goes something like:

“I prefer mutual cooperation to mutual defection, and I understands my opponent agrees. Hence, if I commit to cooperating under this understanding, the fact they are like me means they will too - so we must (and shall) cooperate.”

(See: Metamagical Themes for more information)

To formalise this argument, we need to formalise the self-referential definition of the other player being “like me”.

Barasz, Christiano, Fallenstein, Herreshoff, LaVictoire and Yudkowsky recently explored this question in several works stemming from their 2014 paper that consider important possibilities regarding algorithms caught in a Prisoner’s Dilemma - but with the twist that the algorithms can read each other’s source code before making a choice.

In this setting, one could in theory design an algorithm that cooperates in certain circumstances, but would not be so naive as to cooperate with an opponent that can be proven to always defect.

Moreover, Kleene’s Fixed-Point Theorem (or equivalently, the Diagonalisastion Lemma⁵) allows us to demonstrate the existence of algorithms that are super-rational in the sense that they will specifically cooperate with other algorithms that are super-rational in the same manner.

To begin, let \(\textbf{Choice} = \{C,D\}\), and let \(\mathbb{N}\) (the natural numbers) include the source code of all Prisoner’s Dilemma algorithms in the sense that each number has a binary representation that may comprise such an algorithm’s source code.

Thus, we define the set: \[\begin{equation*} \textbf{Algorithm} = \{f \mid f \text{ is a } \mathbb{N} \rightarrow \textbf{Choice} \text{ function}\} \end{equation*}\] And a source code function \(source: \textbf{Algorithm} \rightarrow \mathbb{N}\).

(Note, we ignore how strategies behave on numbers that do not correspond to an algorithm’s source code)

The first super-rational like algorithm the authors consider is called CliqueBot, which is an algorithm that cooperates with any algorithm that has the exact same source code as it.⁶

I.e., CliqueBot can be described by the following pseudocode.

def CliqueBot(X: SourceCode) -> {Cooperate, Defect}:
    if X == source_code(CliqueBot):
        return Cooperate
    else:
        return Defect

However, CliqueBot’s source code requiring knowledge of its own source code appears paradoxical in the same way Quines seemed to be. In other words, CliqueBot’s source code \(S\) appears to need an additional portion of code \(C\) that compares CliqueBot’s input to \(S\), so that \(S = S + C\).

Yet, once again, by Kleene’s Recursion Theorem, this problem can be solved as follows.

1. Let \(Q: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) be any function that for all algorithms \(a: \mathbb{N} \rightarrow \textbf{Choice}\), satisfies:

(Note, \(1\) will be a proxy for Cooperate (C) and \(0\) will be a proxy for Defect (D))

2. By Kleene’s Recursion Theorem, there exists a function \(q: \mathbb{N} \rightarrow \mathbb{N}\) such that \(\forall\ n \in \mathbb{N}:\ q(n) = Q(source(a), n)\), and moreover that:

And hence CliqueBot can be defined by mapping \(n\) to \(C\) when \(\ q(n)\ = 1\) and \(D\) otherwise.

However, a limitation of CliqueBot is that it can only cooperate with clones of itself. In other words, super-rationality should mean that cooperation occurs between agents that (semantically) hold the same beliefs as them (i.e., with regards to the Prisoner’s Dilemma problem) but are otherwise (syntactically) distinct. For human players this translates to the requirement that different people with the matching super-rational beliefs should cooperate, i.e., despite not being clones of one another.

Thus, the authors go further and demonstrate an algorithm FairBot exists that cooperates with any algorithm that can be proven to cooperate with them.

I.e., FairBot can be described by the following pseudocode.

def FairBot(X: SourceCode) -> {Cooperate, Defect}:
    if provable("The algorithm specified by X will cooperate with FairBot"):
        return Cooperate
    else:
        return Defect

As with CliqueBot, FairBot exists by Kleene’s Recursion Theorem, and importantly any two implementations of FairBot can be proven to cooperate with one another, as desired.

Conclusion: A Unifying Pattern

From Dwyane Wade to incompleteness, to recursion, to self-reproduction (in Quines) and super-rationality, we find fixed-point theorems. However, there are many other kinds of broadly applicable fixed-point theorems, e.g., Brouwer’s fixed-point theorem of topology. What characterises the results of this post are that they are fixed-points with respect to encoding functions, i.e.,:

• The function \(depict: \textbf{Face} \rightarrow \textbf{Statue}\) for the Dwyane Wade Fixed-Point Conjecture.

• The Gödel numbering function \({}^\ulcorner\ - {}^\urcorner: F \rightarrow \mathbb{N}\) for Gödel’s Incompleteness Theorem.

• A source code function \(\textbf{Program} \rightarrow \mathbb{N}\) for the Kleene’s Recursion Theorem examples (i.e., Quines, CliqueBot and Fairbot).

The corresponding fixed-point results manifested as follows.

• \(react(D, depict(D_{fp})) = D_{fp}\) for faces of Dwyane Wade \(D\) and \(D_{fp}\).

• \(\neg Provable({}^\ulcorner\ G\ {}^\urcorner) \equiv G\) for a Gödel sentence \(G\).

• \(Q(source(q), -) = q(-)\) for computable (i.e., partial recursive) functions \(Q\) and \(q\).

Stay-tuned for relevant theoretical results and new applications in some upcoming publications of mine. In particular, a mathematical framework that abstracts the concept of encoding, fixed-point theorems and diagonalisation (i.e., the how of proving fixed-point theorems) such that the above examples of fixed-point theorems become more clearly linked.

Until then, for some related frameworks, see: Smullyan’s Representation Systems (1947, 1994, Gaiffman’s Naming Systems (2006), and Gonda, Reinhart, Stengele & De les Coves (2024).