Finite promise games

Finite promise games are a family of four closely related two-player games defined by Harvey Friedman.http://cs.nyu.edu/pipermail/fom/2009-September/014007.html According to Friedman's statements, three of these games yield some fast-growing functions that eventually dominate all recursive functions provably total in an extension of ZFC known as SMAH, but are provably total in a stronger theory known as SMAH+. However, neither explicit proofs for the eventual domination nor explicit algorithms to compute them are known in the current googology community.
== Overview ==
As the name implies, each of games is finite, and its length is actually predetermined. At each turn, one of the players (which we will call Nathan) chooses an integer or a number of integers (an offering) and the other player (which we will call Wojtek) has to make one of two kinds of promises restricting his future possible moves. Wojtek wins if and only if he can keep all the promises until the end of the game.
Throughout the following sections, three major axiomatic systems are referenced. RCA0 consists of the axioms of Robinson arithmetic, \(\Sigma_1^0\)-induction, and \(\Delta_1^0\)-comprehension (see Second-order arithmetic). SMAH refers to ZFC, plus the infinite family of axioms "there exists a strongly \(k\)-Mahlo cardinal" for all positive integers \(k\). SMAH+ refers to ZFC, plus "for all \(k\), there exists a strongly \(k\)-Mahlo cardinal." The distinction between the two latter theories is that SMAH can only refer to finitely many of its axioms, and thus is incapable of assembling infinitely many of them to prove SMAH+'s sentence.
== Finite piecewise linear copy/invert games ==
Call a function \(T: \mathbb{N}^k \to \mathbb{N}\) piecewise linear iff it can be expressed using finitely many affine functions, using inequalities with integer coefficients to separate the function's pieces. Given a piecewise linear function \(T\), we say that a vector \(\mathbf{y} \in \mathbb{N}^k\) is a \(T\)-inversion of \(x\) if \(\mathbf{y} \in [0,x-1]^k\) and \(T(\mathbf{y}) = x\).
Given a piecewise linear function \(T: \mathbb{N}^k \to \mathbb{N}\) and two positive integers \(n\) and \(s\), we define the finite piecewise linear copy/invert game \(G(T, n, s)\) as follows. \(G(T, n, s)\) is a two-player game alternating between Nathan and Wojtek, with \(n\) rounds in total. Nathan goes first.
On his turn, Nathan selects a number \(x \in [0, s]\), either of the form \(w!\) or \(y + z\), where \(y\) and \(z\) were previously played by Wojtek. \(x\) is called his offer. Wojtek either has the choice of accepting or rejecting the offer:
* By accepting, he plays \(x\), and promises that there will be no \(T\) inversion of \(x\) whose entries are integers ever played by him.
* By rejecting, he plays all entries of a \(T\) inversion of \(x\) of his choice, and promises that none of the integers that he ever plays are \(x\).
If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire \(n\) rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)
----
Wojtek always has a winning strategy for any given FPLCI game. This is provable in RCA0.
He can still win even if we restrict the offers that he is allowed to reject. Consider the modified game \(G_m(T, n, s)\) where Wojtek is forced to accept all factorial numbers greater than \(m\). Wojtek can win \(G_m(T, n, s)\) for all \(T\) and \(n\) and sufficiently large \(m\) and \(s\) (a fact provable in SMAH+, but not in any consistent fragment of SMAH).
Let \(FPLCI(a)\) be the minimal \(N\) such that Wojtek can win \(G_m(T, n, s)\) for any \((m, T, n, s)\) such that \(m\) and \(s\) are greater than or equal to \(N\) and all the following are less than \(a\):
* \(n\)
* \(k\) (recall that the domain of \(T\) is \(\mathbb{N}^k\))
* the number of pieces of \(T\)
* the absolute values of the coefficients of the inequalities in \(T\)
* the absolute values of the coefficients of the affine functions in \(T\)
== Finite polynomial copy/invert games ==
All polynomials discussed in this section have the signature \(\mathbb{Z}^k \to \mathbb{Z}\) (for a fixed \(k\)) and have only integer coefficients.
Given a polynomial \(P\), we say that a vector \(\mathbf{y}\) is a special \(P\)-inversion of \(x\) iff \(P(\mathbf{y}) = x\) and every component of \(\mathbf{y}\) is strictly between 0 and \(x/2\).
Given two polynomials \(P\) and \(Q\) and two positive integers \(n\) and \(s\), we define the finite polynomial copy/invert game \(G(P, Q, n, s)\) as follows. \(G(P, Q, n, s)\) is a two-player game alternating between Nathan and Wojtek, with \(n\) rounds in total. Nathan goes first.
On his turn, Nathan selects a number \(x \in [-s, s]\), of the form \((w!)!\)Erroneously written \(w!!\) in the original posting; confirmed by pers. comm. or \(P(\mathbf{y})\) or \(Q(\mathbf{y})\), where \(\mathbf{y}\) is a vector in \(\mathbb{Z}^k\) whose components were all integers previously played by Wojtek. \(x\) is called his offer. Wojtek either has the choice of accepting or rejecting the offer:
* By accepting, he plays \(x\), and promises that the integers he plays never contain the complete components of a special \(P\) or \(Q\) inversion of \(x\).
* By rejecting, he plays a special \(P\) or \(Q\) inversion of \(x\) of his choice, and promises that none of the integers that he ever plays are \(x\).
If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire \(n\) rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)
----
Wojtek always has a winning strategy for any given FPCI game. This is provable in RCA0.
In fact, he can still win even if we restrict the offers that he is allowed to reject. Consider the modified game \(G_m(P, Q, n, s)\) where Wojtek is forced to accept all factorial numbers greater than \(m\). Wojtek can win \(G_m(P, Q, n, s)\) for all \(P,Q,n\) and sufficiently large \(m\) and \(s\) (a fact provable in SMAH+, but not in any consistent fragment of SMAH).
Let \(FPCI(a)\) be the minimal \(N\) such that Wojtek can win \(G_m(P, Q, n, s)\) for any \((m, P, Q, n, s)\) such that \(m\) and \(s\) greater than or equal to \(N\) and all the following are less than \(a\):
* \(n\)
* \(k\) (recall that the domain of the polynomials is \(\mathbb{Z}^k\))
* the degrees of \(P\) and \(Q\)
* the absolute values of the coefficients of \(P\) and \(Q\)
== Finite order invariant copy/invert games ==
Let \(R : \mathbb{N}^{2k} \to \{0, 1\}\) be order invariant — that is, the order of its inputs does not affect its output. Given a vector \(\mathbf{x} \in \mathbb{N}^{k}\), we say that a vector \(\mathbf{y} \in \mathbb{N}^{k}\) is an R-inversion of \(\mathbf{x}\) iff \(\max(\mathbf{y}) < \max(\mathbf{x})\) and \(R(\mathbf{x}, \mathbf{y}) = 1\) (where the components of the two vectors are concatenated into a vector with \(2k\) components, which is the argument to R).
Given order-invariant \(R : \mathbb{N}^{2k} \to \{0, 1\}\) and two positive integers \(n\) and \(s\), we define the finite order invariant copy/invert game \(G(R, n, s)\) as follows. \(G(R, n, s)\) is a two-player game alternating between Nathan and Wojtek, with \(n\) rounds in total. Nathan goes first.
On his turn, Nathan selects an integer vector \(\mathbf{x} \in [-s, s]^k\), each component being of the form \(z\) or \(z + 1\) or \(w!\), where \(z\) is an integer previously played by Wojtek. \(\mathbf{x}\) is called his offer. Wojtek either has the choice of accepting or rejecting the offer:
* By accepting, he plays \(\mathbf{x}\), and promises that he never plays an \(R\) inversion of \(\mathbf{x}\).
* By rejecting, he plays an \(R\) inversion of \(\mathbf{x}\) of his choice, and promises that he will never play \(\mathbf{x}\).
If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire \(n\) rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)
----
Wojtek always has a winning strategy for any given FOICI game. This is provable in RCA0.
Friedman does not specify any fast-growing functions derived from FOICI games, however.
== Finite linear copy/invert games ==
Given two vectors \(\mathbf{x},\mathbf{y} \in \mathbb{N}^k\), we say that they are additively equivalent iff, for all \(i, j \leq k\), \(\sum^i \mathbf{x} < \sum^j \mathbf{x} \Rightarrow \sum^i \mathbf{y} < \sum^j \mathbf{y}\) (where \(\sum^n \mathbf{v}\) is the sum of the first \(n\) components in \(\mathbf{v}\)).
Let \(V\) be a finite tuple of vectors in \(\mathbb{N}^k\) and two positive integers \(n\) and \(s\), and define the finite linear copy/invert game \(G(V, n, s)\) as follows. \(G(V, n, s)\) is a two-player game alternating between Nathan and Wojtek, with \(n\) rounds in total. Nathan goes first.
On his turn, Nathan selects a number \(x \in [0, s]\), either of the form \(w!\) or \(y + z\), where \(y\) and \(z\) are integers previously played by Wojtek.In the original definition, Nathan (or Alice if we follow the original setting) is required to select a number "\(x \in [0,x]\)", but it is an obvious typo. \(x\) is called his offer. Wojtek either has the choice of accepting or rejecting the offer:
* By accepting, he plays \(x\), and promises that \(x\) can never be written as \(\sum \mathbf{y}\), where all the components of \(\mathbf{y}\) were played by Wojtek at any time and \(\mathbf{y}\) is additively equivalent to a vector in \(V\).
* By rejecting, he chooses a vector \(\mathbf{y} = (y_1,\ldots,y_k)\) in \(\mathbb{N}^k\) such that \(\sum \mathbf{y} = x\) and \(\mathbf{y}\) is additively equivalent to a vector in \(V\), plays the natural numbers \(y_1,\ldots,y_k\), and promises that he will never play \(x\).
If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire \(n\) rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)
----
Wojtek always has a winning strategy for any given FLCI game. This is provable in RCA0.
In fact, he can still win even if we restrict the offers that he is allowed to reject. Consider the modified game \(G_m(V, n, s)\) where Wojtek is forced to accept all factorial numbers greater than \(m\). Wojtek can win \(G_m(V, n, s)\) for all \(V,n,s\) and sufficiently large \(m\) (a fact provable in SMAH+, but not in any consistent fragment of SMAH).
Let \(FLCI(a)\) be the minimal \(N\) such that Wojtek can win \(G_m(V, n, s)\) for all \((m,V,n,s)\) such that \(m\) is greater than or equal to \(N\), \(n\) and \(s\) are positive, and all the following are less than \(a\):
* \(k\)
* the number of vectors in \(V\)
* the components of the vectors in \(V\)
== Functions ==
As shown by Friedman, the three functions \(FPLCI(a)\), \(FPCI(a)\) and \(FLCI(a)\) are extremely fast-growing, eventually dominating any functions provably recursive in a consistent fragment of SMAH. (Note that Friedman did not explicitly describe these three functions, but the definitions in the article here have been directly inferred from his work by Googology Wiki users, who are not professional mathematicians. The original defintions in the article were completely wrong due to the failure of the interpretation of his work, and hence they might still contain errors.)
== Computability ==
Since Friedman did not give explicit algorithms to compute those functions, nobody in the current googology community knows how to compute them. At least, according to Friedman's statement without proofs, the well-definedness of each value itself is provable in arithmetic and they are total computable functions in SMAH+. It is not known in the current googology community whether they are partial computable functions in ZFC.
== Sources ==
== See also ==
Category:Functions
Category:Games
Category:Unnamed numbers
ja:有限約束ゲーム