Three Undecidable Decision Problems About a Non-Negative Integer n Which Have a Short Description in Terms of Arithmetic

We prove that the following decision problems (1) and (2) are algorithmically undecidable when \( n∈N \). (1) \( ∃(y_0,...,y_n)∈N^{n+1} ∀i,j,k∈{0,...,n} (((2^{2^{2^j \cdot 3^k}}+1 divides n) ⇒ (y_j+1=y_k))∧((2^{2^{2^i \cdot 3^j \cdot 5^{k+1}}}+1 divides n)⇒(y_i \cdot y_j=y_k))) \). (2) \( ∃p,q∈N ((n=2^p \cdot 3^q)∧∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ∀i,j,k∈{0,...,p} (((x_j+1=x_k)⇒(y_j+1=y_k))∧((x_i \cdot x_j=x_k)⇒(y_i \cdot y_j=y_k)))) \). For \( n∈N \), let \( E_n={1=x_k, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k∈{0,...,n}} \). For \( n∈N \), f(n) denotes the smallest b∈N such that if a system of equations \( S⊆E \)_n has a solution in \( N^{n+1} \), then S has a solution in\( {0,...,b}^{n+1} \). The author proved earlier that the function \( f:N→N \) is computable in the limit and eventually dominates every computable function g:N→N. We present a short program in MuPAD which for n∈N prints the sequence \( {f_i(n)}_{i=0}^∞ \) 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 \( ∃p,q∈N ((n=2^p \cdot 3^q)∧∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ((∀j,k∈{0,...,p} (x_j+1=x_k ⇒ y_j+1=y_k)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k)))) \). For \( n∈N \), \( β(n) \) denotes the smallest b∈N such that if a system of equations \( S⊆E_n \) has a unique solution in \( N^{n+1} \), then this solution belongs to \( {0,...,b}^{n+1} \). The author proved earlier that the function \( β:N→N \) is computable in the limit and eventually dominates every function δ:N→N with a single-fold Diophantine representation. The computability of β is unknown. We present a short program in MuPAD which for n∈N prints the sequence \( {β_i(n)}_{i=0}^∞ \) of non-negative integers converging to \( β(n) \).