3
$\begingroup$

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion from $f$ and $g$ if for all $x_1,\dots,x_k\in\mathbb N$ and $y\in\mathbb N$, \begin{align} h(x_1,\dots,x_k,0)&=f(x_1,\dots,x_k), \\ h(x_1,\dots,x_k,y')&=g(x_1,\dots,x_k,y,h(x_1,\dots,x_k,y)), \end{align} where $y'$ denotes the successor of $y$.

Primitive recursion can be seen as corresponding to a "for loop" in a programming language – the following pseudocode computes $h(x_1,\dots,x_k,y)$:

INPUT x1,...xk,y
value = f(x1,...,xk)
for i=0 to y:
    value = g(x1,...,xk,i,value)
RETURN value

I find such an explanation quite valuable, since it reinforces the idea that general recursive functions are ones that can be "computed" in a reasonable sense. Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages?


For reference, the minimisation operation can be defined as follows:

If $f:\mathbb N^{k+1}\rightharpoonup \mathbb N$ is a partial function, then the minimisation $m:\mathbb N^k\rightharpoonup\mathbb N$ of $f$ is given by the following rule: if $f(x_1,\dots,x_k,t)$ is defined and $\neq0$ for all $t<y$, and $f(x_1,\dots,x_k,y)=0$, then $m(x_1,\dots,x_k):=y$; if there is no such $y$, then $m(x_1,\dots,x_k)$ is undefined.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages?

Yes, minimisation corresponds to possibly non-terminating loops. It increments t and searches for the first 0 value. When the function is undefined it means that it is looping forever.

INPUT x1,...xk
t = 1
value = f(x1,...,xk,t)
while value != 0:
     t = t + 1
     value = f(x1,...,xk,t)
RETURN t

Note that when f is undefined, it also would not terminate.

$\endgroup$
6
  • $\begingroup$ Might want to clarify, op gives a definition for the bounded minimization operator, while this answer gives an example of the unbounded minimization operator (aka μ operator) $\endgroup$
    – BurnsBA
    Commented Apr 12 at 19:36
  • $\begingroup$ @BurnsBA correct me if I’m wrong, but the op gives the definition for unbounded minimization (its arity is one less than f). Bounded minimization would be a total function $\endgroup$ Commented Apr 12 at 20:39
  • $\begingroup$ op definition says "...for all $t<y$...". This answer has no limit on $t$. See perhaps planetmath.org/boundedminimization . This question might be relevant: math.stackexchange.com/q/1276185/114910 $\endgroup$
    – BurnsBA
    Commented Apr 12 at 20:50
  • 3
    $\begingroup$ @BurnsBA I think you might be misunderstanding, $y$ is the result of the minimization in ops definition, not $t$. There's no upper bound on y. $\endgroup$
    – Knogger
    Commented Apr 12 at 22:44
  • 2
    $\begingroup$ @BurnsBA no, the bound is in the antecedent of a conditional, it reads that the result of the minimization is equal to y if for all t < y, …. The bound of t is y, but y is the result, not a parameter, so the search is not bounded. There is no ultimate bound on y. See definition here en.m.wikipedia.org/wiki/General_recursive_function where the i is OP’s t. $\endgroup$ Commented Apr 14 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.