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) ).