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!
|
| _version_ | 1866916694899818496 |
|---|---|
| author | Parent, T. |
| author_facet | Parent, T. |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_02489 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | An anomaly in diagonalization Parent, T. Logic 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. |
| title | An anomaly in diagonalization |
| topic | Logic |
| url | https://arxiv.org/abs/2103.02489 |