Return to Question

Natural numbers ≡ \$\{0,1,2,...\}\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function that maps \$n\$ natural numbers (with \$n>0\$ being a number of your choosing) to 1 natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive_recursive_function)

Zero $$Z()=0$$

Successor $$S(x)=x+1$$

Projection $$P_i^n(x_0,x_1,\dots,x_{n-1})=x_i$$

Composition $$h(x_0,x_1,\dots,x_m)=f(g_1(x_0,x_1,\dots,x_m),\dots,g_k(x_0,x_1,\dots,x_m))$$

Primitive recursion

$$\begin{align}h(0,x_0,\dots,x_k)&=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&=g(y,h(y,x_0,\dots,x_k),x_0,\dots,x_k)\end{align}$$

An example of such a function is the Ackermann function, with its proof of not being primitive recursive on Wikipedia.

The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always terminate and return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

A proof accompanying your answer is appreciated, but not required.

This challenge was drafted thanks to the helpful commenters at its Sandbox.

Natural numbers ≡ \$\mathbb{N}≡\{0,1,2,...\}\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function \$\mathbb{N}^n→\mathbb{N}\$, i.e. a function that maps \$n\$ natural numbers (with \$n>0\$ being a number of your choosing) to a natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive_recursive_function)

Zero $$Z()=0$$

Successor $$S(x)=x+1$$

Projection $$P_i^n(x_0,x_1,\dots,x_{n-1})=x_i$$

Composition $$h(x_0,x_1,\dots,x_m)=f(g_1(x_0,x_1,\dots,x_m),\dots,g_k(x_0,x_1,\dots,x_m))$$

Primitive recursion

$$\begin{align}h(0,x_0,\dots,x_k)&=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&=g(y,h(y,x_0,\dots,x_k),x_0,\dots,x_k)\end{align}$$

From the above five functions/operations, we can get many functions like the constant function, addition, multiplication, exponentiation, factorial, primality test, etc.

A (total) function that is not primitive recursive could be one that grows faster than any primitive recursive function, like the Ackermann function. Its proof of not being primitive recursive is on Wikipedia.

Or a function could be non primitive recursive due to contradictions that would arise otherwise; examples are provided in the answers to this Math Stack Exchange question as pointed out by Bubbler.

The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always terminate and return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

The submission should theoretically work for any input, including those outside of the used numeric data types.

A proof accompanying your answer is appreciated, but not required.

This challenge was drafted thanks to the helpful commenters at its Sandbox.

Natural numbers ≡ \$\{0,1,2,...\}\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function that maps \$n\$ natural numbers (with \$n>0\$ being a number of your choosing) to 1 natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive_recursive_function)

Zero $$Z()=0$$

Successor $$S(x)=x+1$$

Projection $$P_i^n(x_0,x_1,\dots,x_{n-1})=x_i$$

Composition $$h(x_0,x_1,\dots,x_m)=f(g_1(x_0,x_1,\dots,x_m),\dots,g_k(x_0,x_1,\dots,x_m))$$

Primitive recursion

$$\begin{align}h(0,x_0,\dots,x_k)&=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&=g(y,h(y,x_0,\dots,x_k),x_0,\dots,x_k)\end{align}$$

An example of such a function is the Ackermann function, with its proof of not being primitive recursive on Wikipedia.

The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

A proof accompanying your answer is appreciated, but not required.

This challenge was drafted thanks to the helpful commenters at its Sandbox.

Natural numbers ≡ \$\{0,1,2,...\}\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function that maps \$n\$ natural numbers (with \$n>0\$ being a number of your choosing) to 1 natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive_recursive_function)

Zero $$Z()=0$$

Successor $$S(x)=x+1$$

Projection $$P_i^n(x_0,x_1,\dots,x_{n-1})=x_i$$

Composition $$h(x_0,x_1,\dots,x_m)=f(g_1(x_0,x_1,\dots,x_m),\dots,g_k(x_0,x_1,\dots,x_m))$$

Primitive recursion

$$\begin{align}h(0,x_0,\dots,x_k)&=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&=g(y,h(y,x_0,\dots,x_k),x_0,\dots,x_k)\end{align}$$

An example of such a function is the Ackermann function, with its proof of not being primitive recursive on Wikipedia.

The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always terminate and return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

A proof accompanying your answer is appreciated, but not required.

This challenge was drafted thanks to the helpful commenters at its Sandbox.