Two Undecidable Decision Problems on an Ordered Pair of Non-Negative Integers

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 \(\mathcal{S} \subseteq E_{n}\) has a solution in \({\mathbb{N}}^{n + 1}\), then \(\mathcal{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)}\). Since \(f\) is not computable, no algorithm takes as input non-negative integers \(n\) and \(m\) and decides whether or not \({\forall{(x_{0},\ldots,x_{n})}} \in\)\({{\mathbb{N}}^{n + 1}{\exists{(y_{0},\ldots,y_{n})}}} \in {{{\{ 0,\ldots,m\}}^{n + 1}{({{\forall k} \in {{\{ 0,\ldots,n\}}{({1 = x_{k}\Rightarrow 1 = y_{k}})}}})}}\ \land}\)\({(\forall i,j,k \in {\{ 0,\ldots,n\}}{(x_{i} + x_{j} = x_{k}\Rightarrow y_{i} + y_{j} = y_{k})})}\ \land\) \({(\forall i,j,k \in {\{ 0,\ldots,n\}}{(x_{i} \cdot x_{j} = x_{k}\Rightarrow}} {y_{i} \cdot y_{j} = y_{k})})\). Similarly, no algorithm takes as input non-negative integers \(n\) and \(m\) and decides whether or not \({\forall{(x_{0},\ldots,x_{n})}} \in {{\mathbb{N}}^{n + 1}{\exists{(y_{0},\ldots,y_{n})}}} \in \\ {{{\{ 0,\ldots,m\}}^{n + 1}{({{{\forall j},k} \in {{\{ 0,\ldots,n\}}{({{x_{j} + 1} = x_{k}\Rightarrow{y_{j} + 1} = y_{k}})}}})}} \land \\ {({{{\forall i},j,k} \in {{\{ 0,\ldots,n\}}{({{x_{i} \cdot x_{j}} = x_{k}\Rightarrow{y_{i} \cdot y_{j}} = y_{k}})}}}).}}\) For \(n \in {\mathbb{N}}\), \(\beta{(n)}\) denotes the smallest \(b \in {\mathbb{N}}\) such that if a system of equations \(\mathcal{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)}\).