Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2103.02489 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- When formalized, some diagonal arguments do not show the diagonal object to be impossible but rather reveal some other anomaly (e.g., that one of the relevant sets is ill-defined). This raises the possibility that some diagonal arguments have been misinterpreted along this parameter. The diagonal argument against a universal p.r. function is considered in this light. The impetus is the construction of a binary p.r. function that apparently computes, for any $i$ and $n$, $f_i\left(i,n\right)$. The construction features an algorithm which exploits that, in the theory of concern, the index assigned to a p.r. function codes the definitional composition of the function. The algorithm is guided by this to generate a "canonical proof" of $f_i\left(i,n\right)=m$, and a dynamically updated counter tracks how many computations are needed before halting. The resulting algorithm and function then appear to satisfy all standard criteria for being p.r. while simulating a universal function. This suggests that the standard diagonal argument does not apply straightforwardly in this setting, despite surface-level compliance with its assumptions. The case points to a need for greater clarity about these assumptions.