Welcome to MathOverflow

Question

0

Inspired by http://mathoverflow.net/questions/88368/can-a-group-be-a-universal-turing-machine, what about the more restricted case of finding a a group isomorphic to the primitive recursive functions?

edited Dec 26 at 12:11

asked Dec 22 at 11:03

Vlad Infinitum
1●1

2

Could you explain a little more what you mean? What group operation did you have in mind on the set of primitive recursive functions? It might seem natural to restrict to primitive recursive permutations of $\mathbb{N}$, under composition, but these don't form a group, since the inverse of a primitive recursive function need not be primitive recursive. – Joel David Hamkins Dec 22 at 11:17

2

Or perhaps you wanted a group, as in the question of Tao's to which you link, where the group operations are not only computable, but are actually primitive recursive? And in which the reduction of the halting problem is also primitive recursive? In this case, the accepted answer over there already has that feature, since the presentation of the group there is extremely concrete, enough to make the group operations primitive recursive. – Joel David Hamkins Dec 22 at 11:29

Joel, thanks for forcing me to clarify my thoughts somewhat. I'd actually settle for a monoid of the primitive recursive permutations of $\mathbb{N}$ under composition. Is there a readily described presentation for the monoid? – Vlad Infinitum Dec 26 at 11:57

So you want a presentation of the monoid of primitive recursive functions under composition, which does not involve directly the concept of primitive recursive functions? – Joel David Hamkins Dec 26 at 12:26

1

@Joel: It's not rigid, but the automorphism group consists of conjugations by PR bijections with PR inverse. One inclusion is obvious. OTOH, constant functions are exactly the left zero elements of the monoid, hence any automorphism $\phi$ induces a permutation $\pi$ of the constants, and then it easily follows that $\phi(f)=\pi\circ f\circ\pi^{-1}$ for every $f$. The function $t=\phi(s)$ is PR, hence $\pi(n)=t^n(\pi(0))$ is also PR, and since $\phi^{-1}$ is also an automorphism, $\pi^{-1}$ is PR by a symmetric argument. – Emil Jeřábek Dec 26 at 13:53

show 4 more comments

Can the primitive recursive functions be modelled by a group?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.