Timeline for Shortest total non-primitive recursive function
Current License: CC BY-SA 4.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2021 at 18:40 | answer | added | NoLongerBreathedIn | timeline score: 0 | |
| May 13, 2021 at 17:09 | history | edited | user41805 |
edited tags
|
|
| Mar 23, 2020 at 2:55 | answer | added | Bubbler | timeline score: 1 | |
| Mar 22, 2020 at 21:38 | comment | added | Mitchell Spector | @EricTowers The OP specifically allowed for functions with domain \$\mathbb{N}^k\$ for any \$k>0\$ of your choosing. My earlier comment was directed at solutions where people had written a function whose domain was some proper subset of \$\mathbb{N},\$ rather than being all of \$\mathbb{N}.\$ At the time, I don't think anybody had chosen to use any \$k\$ other than \$1.\$ It was also directed at purported solutions where the function being computed was actually primitive recursive, even though the algorithm used didn't match the requirements for primitive recursion itself. | |
| Mar 22, 2020 at 21:33 | comment | added | Eric Towers | @MitchellSpector : From your prior comment, " its domain is the entire set of natural numbers", which is $\Bbb{N}$, not $\Bbb{N}^k$ for some $k \in \Bbb{Z}_{>0}$. | |
| Mar 22, 2020 at 20:08 | comment | added | Mitchell Spector | @EricTowers The domain of the desired answer is just \$\mathbb{N}^k\$ for some \$k>0\$ of your choosing. The domain of any particular primitive recursive function is \$\mathbb{N}^k\$ for some corresponding particular \$k>0.\$ | |
| Mar 22, 2020 at 18:55 | comment | added | Eric Towers | @MitchellSpector : It's worse than that: the domain is all nonempty lists of natural numbers. | |
| Mar 22, 2020 at 11:18 | history | edited | user41805 | CC BY-SA 4.0 |
clarified and added note on integer size thanks to dzaima
|
| Mar 22, 2020 at 8:49 | answer | added | Mitchell Spector | timeline score: 6 | |
| Mar 22, 2020 at 0:30 | review | Close votes | |||
| Mar 22, 2020 at 1:25 | |||||
| Mar 21, 2020 at 19:37 | answer | added | Neil | timeline score: 1 | |
| Mar 21, 2020 at 17:57 | answer | added | Arnauld | timeline score: 1 | |
| Mar 21, 2020 at 17:46 | answer | added | xnor | timeline score: 6 | |
| Mar 21, 2020 at 17:37 | answer | added | Noodle9 | timeline score: 2 | |
| Mar 21, 2020 at 17:09 | comment | added | FryAmTheEggman | @JonathanAllan It is not too difficult to come up with certain classes of functions which aren't primitive recursive. For example, the quickly growing functions like the Ackermann function are not too hard to modify or replicate and then "reprove." That said, it is not trivial - but I am no expert in this area, so there could be another approach that is easier. | |
| Mar 21, 2020 at 17:02 | comment | added | Jonathan Allan | @FryAmTheEggman Not being familiar with the subject matter does this challenge boil down to "pick some already known function and golf it"? Or is there reasonable scope to actually write said function first? | |
| Mar 21, 2020 at 17:00 | comment | added | Jonathan Allan | @FryAmTheEggman Thanks, the function has one output which is a variable natural number, rather than only ever outputting a single natural number :) | |
| Mar 21, 2020 at 16:55 | comment | added | FryAmTheEggman | @JonathanAllan It is a little unconventional as really the program is just there for scoring. You write a program which maps some vector \$ x \in \{ 0, 1, 2, \dots \}^{n} \$ to a single number. If that total mapping cannot be replicated by a primitive recursion function, then your submission is valid. Hope that helps. | |
| Mar 21, 2020 at 16:49 | comment | added | Jonathan Allan | Ah I get it - we "output a function". Still got no idea how to compete though :( | |
| Mar 21, 2020 at 16:47 | comment | added | FryAmTheEggman |
@JonathanAllan I'm not sure if I understand what you are asking, precisely, but the goal is to output a function that is NOT primitive recursive, therefore you can't output n as that is just the projection function. Similarly e.g. you cannot output a constant because that function is the zero function composed with some number of successor functions.
|
|
| Mar 21, 2020 at 16:44 | comment | added | Jonathan Allan |
If I output x isn't that the successor to the successor, ..., to zero?
|
|
| Mar 21, 2020 at 16:38 | history | became hot network question | |||
| Mar 21, 2020 at 16:33 | answer | added | Wheat Wizard♦ | timeline score: 5 | |
| Mar 21, 2020 at 16:19 | answer | added | Noodle9 | timeline score: 2 | |
| Mar 21, 2020 at 15:27 | answer | added | Mitchell Spector | timeline score: 4 | |
| Mar 21, 2020 at 15:23 | comment | added | Mitchell Spector | I think people are misinterpreting this challenge. It's supposed to be a total function, meaning mathematically that its domain is the entire set of natural numbers -- that is, it halts for every natural number as input. Also, you need to show that there is no primitive recursive algorithm for it, not just that the particular algorithm you have doesn't appear to match how primitive recursive functions work. | |
| Mar 21, 2020 at 15:00 | history | tweeted | twitter.com/StackCodeGolf/status/1241379206942072833 | ||
| Mar 21, 2020 at 14:52 | comment | added | AviFS |
1) Darn! Sounds like my BF & 05AB1E answers are out... 2) It is unproven, correct. However the question still holds; it was just the simplest example I could think of. For another example, please see my APL answer, which does return just one number and doesn't loop indefinitely. However, the output behaves like f(n) = n==1. 3) Ah, my fault, I see that now!
|
|
| Mar 21, 2020 at 14:48 | history | edited | user41805 | CC BY-SA 4.0 |
clarified on halting
|
| Mar 21, 2020 at 14:43 | comment | added | user41805 |
@AviF.S. 1) The submission cannot loop indefinitely, as per "it cannot loop indefinitely." 2) Isn't f(n)=1 still unproven? 3) The input is mapped to one output natural number (finite in size), so an infinite array/stream would not count as valid output.
|
|
| Mar 21, 2020 at 13:56 | answer | added | Jonathan Frech | timeline score: 3 | |
| Mar 21, 2020 at 12:54 | comment | added | AviFS | I keep surpassing my comment edit cap, so forgive me for yet another: What about truly constant functions that print the same stream. On the one hand, the infinite list could not be calculated with primitive recursion nor print a non-terminating stream. On the other hand... | |
| Mar 21, 2020 at 12:25 | comment | added | AviFS |
Does the function our code computes need to be non-primitive recursive, or the simplest function which describes its behavior? For example, the fix point of the Collatz function is non-primitive recursive, however it always outputs 1 (equivalent to f(n)=1), so one could say it doesn't count...
|
|
| Mar 21, 2020 at 12:24 | comment | added | AviFS | I'm afraid most winning entries will just output infinite lists, or apply the same operator to the input ad infinitum... | |
| Mar 21, 2020 at 8:29 | history | asked | user41805 | CC BY-SA 4.0 |