A Characterization of Turing Machines that Compute Primitive Recursive Functions
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915566254555136 |
|---|---|
| author | Schwartz, Daniel G. |
| author_facet | Schwartz, Daniel G. |
| contents | This paper provides a new and more direct proof of the assertion that a Turing computable function of the natural numbers is primitive recursive if and only if the time complexity of the corresponding Turing machine is bounded by a primitive recursive function of the function's arguments. In addition, it provides detailed proofs of two consequences of this fact, which, although well-known in some circles, do not seem to have ever been published. The first is that the Satisfiability Problem, properly construed as a function of natural numbers, is primitive recursive. The second is a generalization asserting that all the problems in NP are similarly primitive recursive. The purpose here is to present these theorems, fully detailed, in an archival journal, thereby giving them a status of permanence and general availability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18283 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Characterization of Turing Machines that Compute Primitive Recursive Functions Schwartz, Daniel G. Formal Languages and Automata Theory This paper provides a new and more direct proof of the assertion that a Turing computable function of the natural numbers is primitive recursive if and only if the time complexity of the corresponding Turing machine is bounded by a primitive recursive function of the function's arguments. In addition, it provides detailed proofs of two consequences of this fact, which, although well-known in some circles, do not seem to have ever been published. The first is that the Satisfiability Problem, properly construed as a function of natural numbers, is primitive recursive. The second is a generalization asserting that all the problems in NP are similarly primitive recursive. The purpose here is to present these theorems, fully detailed, in an archival journal, thereby giving them a status of permanence and general availability. |
| title | A Characterization of Turing Machines that Compute Primitive Recursive Functions |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2510.18283 |