On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems
Signifiable computability aims to separate what is theoretically computable from what is computable through performable processes on computers with finite amounts of memory. Mathematical objects are signifiable in a formalism <inline-formula><math display="inline" xmlns="http...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/6/934 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850280579804692480 |
|---|---|
| author | Vladimir A. Kulyukin |
| author_facet | Vladimir A. Kulyukin |
| author_sort | Vladimir A. Kulyukin |
| collection | DOAJ |
| description | Signifiable computability aims to separate what is theoretically computable from what is computable through performable processes on computers with finite amounts of memory. Mathematical objects are signifiable in a formalism <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on an alphabet <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> if they can be written as spatiotemporally finite texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>. In a previous article, we formalized the signification and reference of real numbers and showed that data structures representable as multidimensional matrices of discretely finite real numbers are signifiable. In this investigation, we continue to formulate our theory of signifiable computability by offering an axiomatization of signifiable computation on discretely finite real numbers. The axiomatization implies an ontology of functions on discretely finite real numbers that classifies them as signifiable, signifiably computable, and signifiably partially computable. Relative to <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> and <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>, signification is performed with two formal systems: the Former <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> that forms texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> and the Transformer <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>T</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> that transforms texts formed by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> into other texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>. Singifiable computation is defined relative to <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> as a finite sequence of signifiable program states, the first of which is generated by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> and each subsequent state is deterministically obtained from the previous one by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>T</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula>. We define a debugger function to investigate signifiable computation on finite-memory devices and to prove two theorems, which we call the Debugger Theorems. The first theorem shows that, for a singifiably partially computable function signified by a program on a finite-memory device <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula>, the memory capacity of <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> is exceeded when running the program on signifiable discretely finite real numbers outside of the function’s domain. The second theorem shows that there are functions signifiably computable in general that become partially signifiably computable when signified by programs on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> insomuch as the memory capacity of <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> can be exceeded even when the programs are executed on some signifiable discretely finite real numbers in the domains of these functions. |
| format | Article |
| id | doaj-art-c51e051cbe3d4f7fb1f850c9e2a1085d |
| institution | OA Journals |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-c51e051cbe3d4f7fb1f850c9e2a1085d2025-08-20T01:48:41ZengMDPI AGMathematics2227-73902025-03-0113693410.3390/math13060934On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger TheoremsVladimir A. Kulyukin0Department of Computer Science, Utah State University, Logan, UT 84322, USASignifiable computability aims to separate what is theoretically computable from what is computable through performable processes on computers with finite amounts of memory. Mathematical objects are signifiable in a formalism <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on an alphabet <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> if they can be written as spatiotemporally finite texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>. In a previous article, we formalized the signification and reference of real numbers and showed that data structures representable as multidimensional matrices of discretely finite real numbers are signifiable. In this investigation, we continue to formulate our theory of signifiable computability by offering an axiomatization of signifiable computation on discretely finite real numbers. The axiomatization implies an ontology of functions on discretely finite real numbers that classifies them as signifiable, signifiably computable, and signifiably partially computable. Relative to <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> and <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>, signification is performed with two formal systems: the Former <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> that forms texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> and the Transformer <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>T</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> that transforms texts formed by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> into other texts in <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula>. Singifiable computation is defined relative to <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">L</mi></semantics></math></inline-formula> on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">A</mi></semantics></math></inline-formula> as a finite sequence of signifiable program states, the first of which is generated by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>F</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula> and each subsequent state is deterministically obtained from the previous one by <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mover accent="true"><mover accent="true"><mi>T</mi><mo>¨</mo></mover><mo>^</mo></mover><mrow><mi mathvariant="script">A</mi><mo>,</mo><mi mathvariant="script">L</mi></mrow></msub></semantics></math></inline-formula>. We define a debugger function to investigate signifiable computation on finite-memory devices and to prove two theorems, which we call the Debugger Theorems. The first theorem shows that, for a singifiably partially computable function signified by a program on a finite-memory device <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula>, the memory capacity of <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> is exceeded when running the program on signifiable discretely finite real numbers outside of the function’s domain. The second theorem shows that there are functions signifiably computable in general that become partially signifiably computable when signified by programs on <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> insomuch as the memory capacity of <inline-formula><math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi mathvariant="script">D</mi></semantics></math></inline-formula> can be exceeded even when the programs are executed on some signifiable discretely finite real numbers in the domains of these functions.https://www.mdpi.com/2227-7390/13/6/934computability theoryrecursion theorysignifiable computabilityaxiomatizationdebugger theoremsdiscretely finite real numbers |
| spellingShingle | Vladimir A. Kulyukin On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems Mathematics computability theory recursion theory signifiable computability axiomatization debugger theorems discretely finite real numbers |
| title | On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems |
| title_full | On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems |
| title_fullStr | On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems |
| title_full_unstemmed | On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems |
| title_short | On Signifiable Computability: Part II: An Axiomatization of Signifiable Computation and Debugger Theorems |
| title_sort | on signifiable computability part ii an axiomatization of signifiable computation and debugger theorems |
| topic | computability theory recursion theory signifiable computability axiomatization debugger theorems discretely finite real numbers |
| url | https://www.mdpi.com/2227-7390/13/6/934 |
| work_keys_str_mv | AT vladimirakulyukin onsignifiablecomputabilitypartiianaxiomatizationofsignifiablecomputationanddebuggertheorems |