<p>Abstractly, by a <em>programming language</em> that operates on binary strings I mean a set <span class="math-container">$P$</span> of programs along with a semantics relation <span class="math-container">$[p](x) = y$</span>, ``the program <span class="math-container">$p$</span> on string <span class="math-container">$x$</span> halts with output <span class="math-container">$y$</span>.&quot; An <em>encoding</em> of a programming language is an identification of <span class="math-container">$P$</span> as a subset of binary strings.</p>
<p>Say a programming language with a fixed encoding has the <em>second recursion property</em> in case
<span class="math-container">$$(\forall p \in P)(\exists p^\star \in P)(\forall d \in 2^\star)\ [p](p^\star,d) = [p^\star](d).$$</span></p>
<p>Now Kleene's second recursion theorem basically says that any reasonable Turing-complete programming language with a reasonable encoding has the second recursion property. My question is:</p>
<p><em>Do Bellantoni-Cook safe recursive programs (or any other implicit characterizations of polynomial time), suitably encoded, enjoy the second recursion property?</em></p>
<p><strong>Context.</strong> In the 70's and 80's people figured out that some natural subrecursive programming languages capturing &quot;large&quot; classes (like primitive recursive functions) <em>did</em> have the second recursion property. I am wondering whether the same holds for more modern Implicit Computational Complexity-style languages.</p>
<p><strong>Note.</strong> In classical recursion theory, Kleene's second recursion theorem is equivalent to the Rogers fixpoint theorem. For indexings of complexity classes, that is not the case: the equivalence relies on the existence of universal programs, which do not exist in the subrecursive setting.</p>

CC BY-SA 4.0
2023-03-27T19:50:55.740Z
I don't see how this answers the original question. What would the program be? (It certainly can't be $p^\star$, which must depend on $p$.)
Lê Thành Dũng 'Tito' Nguyễn
CC BY-SA 4.0
2022-12-12T16:25:12.530Z
Is this not trivial from completeness?
cody
CC BY-SA 4.0
2022-12-12T22:27:16.607Z
what does completeness mean in this sense? (These are not Turing-complete languages)
Siddharth
CC BY-SA 4.0
2022-12-13T20:25:07.813Z
Complete for the relevant complexity class, which these systems tend to be.
cody
CC BY-SA 4.0
2022-12-14T15:44:24.227Z
Certainly, any polynomial-time computable function can be computed (by definition) by some program in any such language. However, I don't see how the second recursion property trivially follows from this.
Siddharth
CC BY-SA 4.0
2022-12-15T16:18:22.197Z
Well, one such program is that which takes as input the code for a turing machine $M$, a polynomial $P$ and an input string $s$, and simulates $M$ for $P(|s|)$ steps on $s$ (the original P-complete problem). Does that fill the requirement?
cody
<cc.complexity-theory><computability><pl.programming-languages>
Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?
Siddharth
# Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?

(Asked by: username_0 on 2022-12-09)

Abstractly, by a *programming language* that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, ``the program $p$ on string $x$ halts with output $y$." An *encoding* of a programming language is an identification of $P$ as a subset of binary strings.

Say a programming language with a fixed encoding has the *second recursion property* in case
$$(\forall p \in P)(\exists p^\star \in P)(\forall d \in 2^\star)\ [p](p^\star,d) = [p^\star](d).$$

Now Kleene's second recursion theorem basically says that any reasonable Turing-complete programming language with a reasonable encoding has the second recursion property. My question is:

*Do Bellantoni-Cook safe recursive programs (or any other implicit characterizations of polynomial time), suitably encoded, enjoy the second recursion property?*

**Context.** In the 70's and 80's people figured out that some natural subrecursive programming languages capturing "large" classes (like primitive recursive functions) *did* have the second recursion property. I am wondering whether the same holds for more modern Implicit Computational Complexity-style languages.

**Note.** In classical recursion theory, Kleene's second recursion theorem is equivalent to the Rogers fixpoint theorem. For indexings of complexity classes, that is not the case: the equivalence relies on the existence of universal programs, which do not exist in the subrecursive setting.

**Tags:** cc.complexity-theory, computability, pl.programming-languages
> **Comments:**
> **username_2**: Is this not trivial from completeness?  
> **username_0**: what does completeness mean in this sense? (These are not Turing-complete languages)  
> **username_2**: Complete for the relevant complexity class, which these systems tend to be.  
> **username_0**: Certainly, any polynomial-time computable function can be computed (by definition) by some program in any such language. However, I don't see how the second recursion property trivially follows from this.  
> **username_2**: Well, one such program is that which takes as input the code for a turing machine $M$, a polynomial $P$ and an input string $s$, and simulates $M$ for $P(|s|)$ steps on $s$ (the original P-complete problem). Does that fill the requirement?  
> **username_1**: I don't see how this answers the original question. What would the program be? (It certainly can't be $p^\star$, which must depend on $p$.)  

---

## 0 answers

