Timeline for Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function "Abit" primitive recursive?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 14, 2018 at 17:45 | answer | added | wisusedforomega | timeline score: -3 | |
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| May 14, 2014 at 12:22 | comment | added | Emil Jeřábek | I believe Abit and Amod will be primitive recursive for any reasonable Ackermann function, by a similar argument as in my answer. If you want something that might not be PR, I’d suggest to look at the other end of the numbers. For example, I don’t see how you could compute the leading trinary digit of $A(x,y)$ without essentially evaluating the whole function (though I have no idea how to prove that this is not PR). | |
| May 12, 2014 at 15:31 | comment | added | François G. Dorais | Armando, I have no idea how to write a multiple recursion for Abit or Amod. What I claim is that if there is one, then they are primitive recursive. The reason is that, from the multiple recursion and the fact that Amod(x,y,m) < m, you will be able to find a primitive recursive bound for the size of the table of values needed to compute Amod(x,y,m). | |
| May 12, 2014 at 15:22 | answer | added | Emil Jeřábek | timeline score: 3 | |
| May 12, 2014 at 15:11 | comment | added | Armando Matos | Thanks for your observations! I was thinking in the version A(0,n)=n+1, A(m+1,0)=A(m,1), A(m+1,n+1)=A(m,A(m+1,n)), as used for instance in the wikipedia. I was interested in a version for which the function Abit(m,n,b), the bit b of A(m,n), is not PR. | |
| May 12, 2014 at 14:56 | comment | added | Emil Jeřábek | There are many different “Ackermann” functions in the literature (to begin with, the function actually introduced by Ackermann takes three arguments, not two). While they share fundamental properties such as approximate growth rate, the particulars of the definition may well affect the answer to your questions, as the devil is in the detail when it comes to bit fiddling. So, you need to specify exactly what you want. | |
| May 12, 2014 at 13:57 | comment | added | Armando Matos | To F. G. Dorais. 1. Yes, your interpretation is ok. 2. How can we bound the tables? Does for instance A(x-1,A(x,y-1))%m depend only on (x-1)%m and A(x,y-1)%m (the args mod m)? Or does it depend on the entire computation? | |
| May 12, 2014 at 13:09 | comment | added | j.p. | cstheory.stackexchange.com might be a better place to ask this kind of question (if you do so, please link back to this page). | |
| May 12, 2014 at 11:50 | comment | added | François G. Dorais | I'm not sure what you mean by "definable by a set of recursive equations" but if you mean that it is definable by a double recursion or multiple recursion like the Ackermann function, then that would imply that it is primitive recursive since it's easy to bound the size of verification tables. | |
| May 12, 2014 at 10:43 | history | edited | Armando Matos | CC BY-SA 3.0 |
deleted 24 characters in body; edited title
|
| May 12, 2014 at 10:37 | history | asked | Armando Matos | CC BY-SA 3.0 |