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

For n ∈ N , let En = {1 = xk , xi + xj = xk, xi · xj = xk : i, j, k ∈ {0, … , n}} . For n ∈ N, ƒ(n) denotes the smallest b ∈ N such that if a system of equations S ⊆ En has a solution in Nn+1 , then S has a solution in {0 , … , b}n+1 . The author proved earlier that the function ƒ : 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 {ƒi(n)}i∞=0 of non-negative integers converging to ƒ(n) . Since ƒ is not computable, no algorithm takes as input non-negative integers n and m and decides whether or not ∀(x0, … , xn) ∈ Nn+1 ∃(y0, … , yn) ∈ {0 , … , m}n+1 (∀k ∈ {0 , … , n} (1 = xk ⇒ 1 = yk)) ∧ (∀i, j, k ∈ {0, … , n} (xi + xj = xk ⇒ yi + yj = yk) )∧(∀i, j, k ∈ {0 , … , n} ( xi · xj = xk ⇒ yi · yj = yk)) . Similarly, no algorithm takes as input non-negative integers n and m and decides whether or not ∀(x0, … , xn) ∈ Nn+1 ∃ (y0, … , yn) ∈ {0, … , m}n+1 (∀j, k ∈ {0 , … , n} (xj + 1 = xk ⇒ yj + 1 = yk)) ∧ (∀i, j, k ∈ {0 , … , n} (xi · xj = xk ⇒ yi · yj = yk) ) . For n ∈ N, β(n) denotes the smallest b ∈ N such that if a system of equations S ⊆ E n has a unique solution in Nn+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).