An Undecidable Decision Problem About a Non-Negative Integer 𝘯 That Has a Short Description in Terms of Arithmetic

For \(n \in {\mathbb{N}}\), let \(E_{n} = {\{{{1 = x_{k}},{{{x_{i} + x_{j}} = x_{k}},{{x_{i} \cdot x_{j}} = x_{k}}}}:{{i,j,k} \in {\{ 0,\ldots,n\}}}\}}\). For \(n \in {\mathbb{N}}\), \(f{(n)}\) denotes the smallest \(b \in {\mathbb{N}}\) such that if a system of equations \(S \subseteq E_{n}\) has a solution in \({\mathbb{N}}^{n + 1}\), then \(S\) has a solution in \({\{ 0,\ldots,b\}}^{n + 1}\). The author proved earlier that the function \(f:{{\mathbb{N}}\rightarrow{\mathbb{N}}}\) is computable in the limit and eventually dominates every computable function \(g:{{\mathbb{N}}\rightarrow{\mathbb{N}}}\). We present a short program in MuPAD which for \(n \in {\mathbb{N}}\) prints the sequence \({\{{f_{i}{(n)}}\}}_{i = 0}^{\infty}\) of non-negative integers converging to \(f{(n)}\). We prove that no algorithm takes as input a non-negative integer \(n\) and decides whether or not \(\exists p, q \in \mathbb{N}\left(\left(n=2^p \cdot 3^q\right) \wedge \forall\left(x_0, \ldots, x_p\right) \in \mathbb{N}^{p+1} \exists\left(y_0, \ldots, y_p\right) \in\right.\) \(\{0, \ldots, q\}^{p+1}\left(\left(\forall j, k \in\{0, \ldots, p\}\left(x_j+1=x_k \Rightarrow y_j+1=y_k\right)\right)\right. \wedge\) \(\left.\left.\left(\forall i, j, k \in\{0, \ldots, p\}\left(x_i \cdot x_j=x_k \Rightarrow y_i \cdot y_j=y_k\right)\right)\right)\right)\). For \(n \in {\mathbb{N}}\), \(\beta{(n)}\) denotes the smallest \(b \in {\mathbb{N}}\) such that if a system of equations \(S \subseteq E_{n}\) has a unique solution in \({\mathbb{N}}^{n + 1}\), then this solution belongs to \({\{ 0,\ldots,b\}}^{n + 1}\). The author proved earlier that the function \(\beta:{{\mathbb{N}}\rightarrow{\mathbb{N}}}\) is computable in the limit and eventually dominates every function \(\delta:{{\mathbb{N}}\rightarrow{\mathbb{N}}}\) with a single-fold Diophantine representation. The computability of \(\beta\) is unknown. We present a short program in MuPAD which for \(n \in {\mathbb{N}}\) prints the sequence \({\{{\beta_{i}{(n)}}\}}_{i = 0}^{\infty}\) of non-negative integers converging to \(\beta{(n)}\).