Two undecidable decision problems on an ordered pair of non-negative integers

Two undecidable decision problems on an ordered pair of non-negative integers | Authorea try { document.documentElement.classList.add('js'); } catch (e) { } var _gaq = _gaq || []; _gaq.push(['_setAccount', 'G-8VDV14Y67G']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); Skip to main content Preprints Collections Wiley Open Research IET Open Research Ecological Society of Japan All Collections About About Authorea FAQs Contact Us Quick Search anywhere Search for preprint articles, keywords, etc. Search Search ADVANCED SEARCH SCROLL This is a preprint and has not been peer reviewed. Data may be preliminary. 2 December 2025 V1 Latest version Share on Two undecidable decision problems on an ordered pair of non-negative integers Author : Apoloniusz Tyszka 0000-0002-2770-5495 [email protected] Authors Info & Affiliations https://doi.org/10.22541/au.176463851.11588773/v1 354 views 182 downloads Contents Abstract Supplementary Material Information & Authors Metrics & Citations View Options References Figures Tables Media Share 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) Supplementary Material File (a_tyszka_dec_1.pdf) Download 361.46 KB Information & Authors Information Version history V1 Version 1 02 December 2025 Copyright This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License Keywords computable function eventual domination limit-computable function single-fold diophantine representation undecidable decision problem Authors Affiliations Apoloniusz Tyszka 0000-0002-2770-5495 [email protected] Hugo Kołł ątaj University View all articles by this author Metrics & Citations Metrics Article Usage 354 views 182 downloads .FvxKWukQNSOunydq8rnd { width: 100px; } Citations Download citation Apoloniusz Tyszka. Two undecidable decision problems on an ordered pair of non-negative integers. Authorea . 02 December 2025. DOI: https://doi.org/10.22541/au.176463851.11588773/v1 If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download. For more information or tips please see 'Downloading to a citation manager' in the Help menu . Format Please select one from the list RIS (ProCite, Reference Manager) EndNote BibTex Medlars RefWorks Direct import Tips for downloading citations document.getElementById('citMgrHelpLink').addEventListener('click', function() { popupHelp(this.href); return false; }); $(".js__slcInclude").on("change", function(e){ if ($(this).val() == 'refworks') $('#direct').prop("checked", false); $('#direct').prop("disabled", ($(this).val() == 'refworks')); }); View Options View options PDF View PDF Figures Tables Media Share Share Share article link Copy Link Copied! Copying failed. Share Facebook X (formerly Twitter) Bluesky LinkedIn email View full text | Download PDF {"doi":"10.22541/au.176463851.11588773/v1","type":"Article"} Now Reading: Share Figures Tables Close figure viewer Back to article Figure title goes here Change zoom level Go to figure location within the article Download figure Toggle share panel Toggle share panel Share Toggle information panel Toggle information panel Go to previous graphic Go to next graphic Go to previous table Go to next table All figures All tables View all material View all material xrefBack.goTo xrefBack.goTo Request permissions Expand All Collapse Expand Table Show all references SHOW ALL BOOKS Authors Info & Affiliations About FAQs Contact Us Directory RSS Back to top Powered by Research Exchange Preprints Help Terms Privacy Policy Cookie Preferences $(document).ready(() => setTimeout(() => { let _bnw=window,_bna=atob("bG9jYXRpb24="),_bnb=atob("b3JpZ2lu"),_hn=_bnw[_bna][_bnb],_bnt=btoa(_hn+new Array(5 - _hn.length % 4).join(" ")); $.get("/resource/lodash?t="+_bnt); },4000)); (function(){function c(){var b=a.contentDocument||a.contentWindow.document;if(b){var d=b.createElement('script');d.innerHTML="window.__CF$cv$params={r:'a00e3cbe3b0658d3',t:'MTc3OTY0NjAxOA=='};var a=document.createElement('script');a.src='/cdn-cgi/challenge-platform/scripts/jsd/main.js';document.getElementsByTagName('head')[0].appendChild(a);";b.getElementsByTagName('head')[0].appendChild(d)}}if(document.body){var a=document.createElement('iframe');a.height=1;a.width=1;a.style.position='absolute';a.style.top=0;a.style.left=0;a.style.border='none';a.style.visibility='hidden';document.body.appendChild(a);if('loading'!==document.readyState)c();else if(window.addEventListener)document.addEventListener('DOMContentLoaded',c);else{var e=document.onreadystatechange||function(){};document.onreadystatechange=function(b){e(b);'loading'!==document.readyState&&(document.onreadystatechange=e,c())}}}})();