Two undecidable decision problems on an ordered pair of non-negative integers
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)
Full text
Two undecidable decision problems on an ordered pair of non-negative integers Apoloniusz Tyszka Hugo Kołł ˛ataj University Balicka 116B, 30-149 Kraków, Poland E-mail: [email protected] Abstract For n∈N, let En={1 = xk, xi+xj=xk, xi·xj=xk:i, j, k ∈ {0, . . . , n}}. For n∈N, f(n)denotes the smallest b∈Nsuch that if a system of equations S ⊆ Enhas a solution in Nn+1, then Shas a solution in {0, . . . , b}n+1. The author proved earlier that the function f:N→Nis computable in the limit and eventually dominates every computable function g:N→N. We present a short program in MuPAD which for n∈Nprints the sequence {fi(n)}∞ i=0 of non-negative integers converging to f(n). Since fis not computable, no algorithm takes as input non-negative integers nand mand 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 nand mand 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∈Nsuch that if a system of equations S ⊆ Enhas a unique solution in Nn+1, then this solution belongs to {0, . . . , b}n+1. The author proved earlier that the function β:N→Nis computable in the limit and eventually dominates every function δ:N→Nwith a single-fold Diophantine representation. The computability of β is unknown. We present a short program in MuPAD which for n∈Nprints the sequence {βi(n)}∞ i=0 of non-negative integers converging to β(n). 2020 Mathematics Subject Classification: 03D20, 11U05. Key words and phrases: computable function, eventual domination, limit-computable function, single-fold Diophantine representation, undecidable decision problem. 1The Collatz problem leads to a short computer program that computes in the limit a function γ:N→ {0,1}of unknown computability Definition 1. (cf. [10, pp. 233–235]). A computation in the limit of a function f:N→Nis a semi-algorithm which takes as input a non-negative integer nand for every m∈Nprints a non-negative integer ξ(n, m)such that lim m→∞ ξ(n, m) = f(n). By Definition 1, a function f:N→Nis computable in the limit when there exists an infinite computation which takes as input a non-negative integer nand prints a non-negative integer on each iteration and prints f(n)on each sufficiently high iteration. It is known that there exists a limit-computable function f:N→Nwhich is not computable, see Theorem 1. Every known proof of this fact does not lead to the existence of a short computer program that computes fin the limit. So far, short computer programs can only compute in the limit functions from Nto Nwhose computability is proven or unknown. 1
Lemma 1. For every n∈N, sign(n−1) ·(2n+ (1 −(−1)n)·(5n+ 2)) 4= 0,if n= 1 n 2,if nis even 3n+ 1,if nis odd and n= 1 MuPAD is a part of the Symbolic Math Toolbox in MATLAB R2019b. By Lemma 1, the following program in MuPAD computes in the limit a function γ:N→ {0,1}. input("Input a non-negative integer n",n): while TRUE do print(sign(n)): n:=sign(n-1)*(2*n+(1-(-1)^n)*(5*n+2))/4: end_while: The computability of γis unknown, see [1, p. 79]. The Collatz conjecture implies that γ(n)=0 for every n∈N. 2A limit-computable function f:N→Nwhich eventually dominates every computable function g:N→N For n∈N, let En={1 = xk, xi+xj=xk, xi·xj=xk:i, j, k ∈ {0, . . . , n}} Theorem 1. ([9, p. 118]). There exists a limit-computable function f:N→Nwhich eventually dominates every computable function g:N→N. We present an alternative proof of Theorem 1. For n∈N,f(n)denotes the smallest b∈N such that if a system of equations S ⊆ Enhas a solution in Nn+1, then Shas a solution in {0, . . . , b}n+1. The function f:N→Nis computable in the limit and eventually dominates every computable function g:N→N, see [12]. The term "dominated" in the title of [12] means "eventually dominated". Flowchart 1 shows a semi-algorithm which computes f(n)in the limit, see [12]. Flowchart 1 A semi-algorithm which computes f(n)in the limit 2
3The first undecidable decision problem on an ordered pair of non-negative integers Flowchart 2 shows a simpler semi-algorithm which computes f(n)in the limit. Flowchart 2 A simpler semi-algorithm which computes f(n)in the limit Lemma 2. For every n, m ∈N, the number printed by Flowchart 2 does not exceed the number printed by Flowchart 1. Proof. For every (a0, . . . , an)∈ {0, . . . , m}n+1, En⊇ {1 = xk: (k∈ {0, . . . , n})∧(1 = ak)}∪ {xi+xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai+aj=ak)}∪ {xi·xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai·aj=ak)} Lemma 3. For every n, m ∈N, the number printed by Flowchart 1 does not exceed the number printed by Flowchart 2. Proof. Let n, m ∈N. For every system of equations S ⊆ En, if (a0, . . . , an)∈ {0, . . . , m}n+1 and (a0, . . . , an)solves S, then (a0, . . . , an)solves the following system of equations: {1 = xk: (k∈ {0, . . . , n})∧(1 = ak)}∪ {xi+xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai+aj=ak)}∪ {xi·xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai·aj=ak)} 3
Theorem 2. For every n, m ∈N, Flowcharts 1 and 2 print the same number. Proof. It follows from Lemmas 2 and 3. Definition 2. An approximation of a tuple (x0, . . . , xn)∈Nn+1 is a tuple (y0, . . . , yn)∈Nn+1 such that (∀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)) Observation 1. For every n∈N, there exists a set A(n)⊆Nn+1 such that card(A(n)) ⩽2card(En)= 2n+ 1 + 2 ·(n+ 1)3 and every tuple (x0, . . . , xn)∈Nn+1 possesses an approximation in A(n). Observation 2. For every n∈N,f(n)equals the smallest b∈Nsuch that every tuple (x0, . . . , xn)∈Nn+1 possesses an approximation in {0, . . . , b}n+1. Observation 3. For every n, m ∈N, Flowcharts 1 and 2 print the smallest b∈ {0, . . . , m}such that every tuple (x0, . . . , xn)∈ {0, . . . , m}n+1 possesses an approximation in {0, . . . , b}n+1. Theorem 3. No algorithm takes as input non-negative integers nand mand returns the logical value of the following sentence: every tuple (x0, . . . , xn)∈Nn+1 possesses an approximation in {0, . . . , m}n+1. Proof. Since the function fis not computable, it follows from Observation 2. 4A short program in MuPAD that computes fin the limit The following program in MuPAD implements the semi-algorithm shown in Flowchart 2. input("Input a non-negative integer n",n): m:=0: while TRUE do X:=combinat::cartesianProduct([s $s=0..m] $t=0..n): Y:=[max(op(X[u])) $u=1..(m+1)^(n+1)]: for p from 1 to (m+1)^(n+1) do for q from 1 to (m+1)^(n+1) do v:=1: for k from 1 to n+1 do if 1=X[p][k] and 1<>X[q][k] then v:=0 end_if: for i from 1 to n+1 do for j from i to n+1 do if X[p][i]+X[p][j]=X[p][k] and X[q][i]+X[q][j]<>X[q][k] then v:=0 end_if: if X[p][i]*X[p][j]=X[p][k] and X[q][i]*X[q][j]<>X[q][k] then v:=0 end_if: end_for: end_for: end_for: if max(op(X[q]))<max(op(X[p])) and v=1 then Y[p]:=0 end_if: end_for: end_for: print(max(op(Y))): m:=m+1: end_while: 4
5The second undecidable decision problem on an ordered pair of non-negative integers For n∈N,h(n)denotes the smallest b∈Nsuch that if a system of equations S ⊆ {xj+ 1 = xk, xi·xj=xk:i, j, k ∈ {0, . . . , n}} has a solution in Nn+1, then Shas a solution in {0, . . . , b}n+1. From [12] and Lemma 3 in [11], it follows that the function h:N→Nis computable in the limit and eventually dominates every computable function g:N→N. A bit shorter program in MuPAD computes hin the limit. Theorem 4. No algorithm takes as input non-negative integers nand mand returns the logical value of the following sentence: ∀(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)) Proof. It holds because the function his not computable. 6A limit-computable function β:N→Nof unknown computability which eventually dominates every function δ:N→Nwith a single-fold Diophantine representation The Davis-Putnam-Robinson-Matiyasevich theorem states that every listable set M ⊆ Nn (n∈N\ {0})has a Diophantine representation, that is (a1, . . . , an)∈ M ⇐⇒ ∃x1, . . . , xm∈NW(a1, . . . , an, x1, . . . , xm) = 0 (R) for some polynomial Wwith integer coefficients, see [6]. The representation (R) is said to be single-fold, if for any a1, . . . , an∈Nthe equation W(a1, . . . , an, x1, . . . , xm) = 0 has at most one solution (x1, . . . , xm)∈Nm. Hypothesis 1. ([2], [3], [4], [5, pp. 341–342], [7, p. 42], [8, p. 745]). Every listable set X ⊆ Nk (k∈N\ {0})has a single-fold Diophantine representation. For n∈N,β(n)denotes the smallest b∈Nsuch that if a system of equations S ⊆ Enhas a unique solution in Nn+1, then this solution belongs to {0, . . . , b}n+1. The computability of βis unknown. Theorem 5. The function β:N→Nis computable in the limit and eventually dominates every function δ:N→Nwith a single-fold Diophantine representation. Proof. This is proved in [12]. Flowchart 3 shows a semi-algorithm which computes β(n)in the limit, see [12]. 5
Flowchart 3 A semi-algorithm which computes β(n)in the limit 7A short program in MuPAD that computes βin the limit Flowchart 4 shows a simpler semi-algorithm which computes β(n)in the limit. Flowchart 4 A simpler semi-algorithm which computes β(n)in the limit 6
Lemma 4. For every n, m ∈N, the number printed by Flowchart 4 does not exceed the number printed by Flowchart 3. Proof. For every (a0, . . . , an)∈ {0, . . . , m}n+1, En⊇ {1 = xk: (k∈ {0, . . . , n})∧(1 = ak)}∪ {xi+xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai+aj=ak)}∪ {xi·xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai·aj=ak)} Lemma 5. For every n, m ∈N, the number printed by Flowchart 3 does not exceed the number printed by Flowchart 4. Proof. Let n, m ∈N. For every system of equations S ⊆ En, if (a0, . . . , an)∈ {0, . . . , m}n+1 is a unique solution of Sin {0, . . . , m}n+1, then (a0, . . . , an)solves the system b S, where b S={1 = xk: (k∈ {0, . . . , n})∧(1 = ak)}∪ {xi+xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai+aj=ak)}∪ {xi·xj=xk: (i, j, k ∈ {0, . . . , n})∧(ai·aj=ak)} By this and the inclusion b S ⊇ S,b Shas exactly one solution in {0, . . . , m}n+1, namely (a0, . . . , an). Theorem 6. For every n, m ∈N, Flowcharts 3 and 4 print the same number. Proof. It follows from Lemmas 4 and 5. The following program in MuPAD implements the semi-algorithm shown in Flowchart 4. input("Input a non-negative integer n",n): m:=0: while TRUE do X:=combinat::cartesianProduct([s $s=0..m] $t=0..n): Y:=[max(op(X[u])) $u=1..(m+1)^(n+1)]: for p from 1 to (m+1)^(n+1) do for q from 1 to (m+1)^(n+1) do v:=1: for k from 1 to n+1 do if 1=X[p][k] and 1<>X[q][k] then v:=0 end_if: for i from 1 to n+1 do for j from i to n+1 do if X[p][i]+X[p][j]=X[p][k] and X[q][i]+X[q][j]<>X[q][k] then v:=0 end_if: if X[p][i]*X[p][j]=X[p][k] and X[q][i]*X[q][j]<>X[q][k] then v:=0 end_if: end_for: end_for: end_for: if q<>p and v=1 then Y[p]:=0 end_if: end_for: end_for: print(max(op(Y))): m:=m+1: end_while: 7
References [1] C. S. Calude, To halt or not to halt? That is the question, World Scientific, Singapore, 2024. [2] D. Cantone, A. Casagrande, F. Fabris, E. Omodeo, The quest for Diophantine finite-foldness, Matematiche (Catania) 76 (2021), no. 1, 133–160, https:// doi.org/ 10.4418/ 2021. 76.1.8. [3] D. Cantone, L. Cuzziol, E. G. Omodeo, On Diophantine singlefold specifications, Matematiche (Catania) 79 (2024), no. 2, 585–620, https:// lematematiche.dmi.unict.it/ index.php/ lematematiche/ article/ view/ 2703/ 1218. [4] D. Cantone and E. G. Omodeo, “One equation to rule them all”, revisited, Rend. Istit. Mat. Univ. Trieste 53 (2021), Art. No. 28, 32 pp. (electronic), https:// doi.org/ 10.13137/ 2464-8728/ 33314. [5] M. Davis, Yu. Matiyasevich, J. Robinson, Hilbert’s tenth problem, Diophantine equations: positive aspects of a negative solution; in: Mathematical developments arising from Hilbert problems (ed. F. E. Browder), Proc. Sympos. Pure Math., vol. 28, Part 2, Amer. Math. Soc., Providence, RI, 1976, 323–378, https:// doi.org/ 10.1090/ pspum/ 028.2; reprinted in: The collected works of Julia Robinson (ed. S. Feferman), Amer. Math. Soc., Providence, RI, 1996, 269–324. [6] Yu. Matiyasevich, Hilbert’s tenth problem, MIT Press, Cambridge, MA, 1993. [7] Yu. Matiyasevich, Hilbert’s tenth problem: what was done and what is to be done, in: Proceedings of the Workshop on Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), Contemp. Math. 270, Amer. Math. Soc., Providence, RI, 2000, 1–47, https:// doi.org/ 10.1090/ conm/ 270. [8] Yu. Matiyasevich, Towards finite-fold Diophantine representations, J. Math. Sci. (N. Y.) vol. 171, no. 6, 2010, 745–752, https:// doi.org/ 10.1007%2Fs10958-010-0179-4. [9] J. S. Royer and J. Case, Subrecursive Programming Systems: Complexity and Succinctness, Birkhäuser, Boston, 1994. [10] R. I. Soare, Interactive computing and relativized computability, in: B. J. Copeland, C. J. Posy, and O. Shagrir (eds.), Computability: Turing, Gödel, Church and beyond, MIT Press, Cambridge, MA, 2013, 203–260. [11] A. Tyszka, A hypothetical upper bound on the heights of the solutions of a Diophantine equation with a finite number of solutions, Open Comput. Sci. 8 (2018), no. 1, 109–114, https:// doi.org/ 10.1515/ comp-2018-0012. [12] A. Tyszka, All functions g:N→Nwhich have a single-fold Diophantine representation are dominated by a limit-computable function f:N\ {0} → Nwhich is implemented in MuPAD and whose computability is an open problem, in: Computation, cryptography, and network security (eds. N. J. Daras, M. Th. Rassias), Springer, Cham, 2015, 577–590, https:// doi.org/ 10.1007/ 978-3-319-18275-9_24. 8