Two undecidable decision problems on an ordered pair of non-negative integers
Loading...
a_tyszka_nov_17.pdf (527.26 KB)
0000-0002-2770-5495 Date
2025-11-21
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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). Since f is not computable, no algorithm takes as input non-negative integers n and m and decides whether or not ∀(x_0,...,x_n)∈N^{n+1} ∃(y_0,...,y_n) ∈ {0,...,m}^{n+1} (∀k∈{0,...,n} (1=x_k ⇒ 1=y_k)) ∧ (∀i,j,k∈{0,...,n} (x_i+x_j=x_k ⇒ y_i+y_j=y_k)) ∧ (∀i,j,k∈{0,...,n} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k)). Similarly, no algorithm takes as input non-negative integers n and m and decides whether or not ∀(x_0,...,x_n)∈N^{n+1} ∃(y_0,...,y_n)∈{0,... ,m}^{n+1} (∀j,k∈{0,...,n} (x_j+1=x_k ⇒ y_j+1=y_k)) ∧ (∀i,j,k∈{0,...,n} (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).
Description
Keywords
Citation
Tyszka, A. Two undecidable decision problems on an ordered pair of non-negative integers. arXiv:1309.2605v32 [math.NT]. 21 Nov 2025. https://doi.org/10.48550/arXiv.1309.2605