function computed by programs

40 Views Asked by At

I have two questions:

  1. Which is the function computed by the program $o^1_1(Succ, Succ)$?

  2. Which is the function computed by the program $\mu^1(\pi^2_1)$?

where

$o^n_m$ for the composition rule

$Succ$ for the successor rule

$\mu^n$ for minimisation

$\pi^n_i$ where $i$ and $n$ are natural numbers and $1\leq i \leq n$, in the case of a projection rule.

Composition, that is, the operation that associates to the functions $h$ from $N^m$ to $N$ and $g_1, ... , g_m$ from $N^n$ the function from $N^n$ to $N$ $x_1,...,x_n->h(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))$.

Minimisation, that is, the operation that associates to $g$ from $N^{n+1}$ to $N$ the function $f$ from $N^n$ to $N$ such that $f(x_1,...,x_n)$ is the least natural number $y$ such that $g(x_1,...,x_n,y)=0$.

Projection functions $x_1,...,x_n->x_i$.

1

There are 1 best solutions below

1
On BEST ANSWER

The first one then is $$ o_1^1(\text{Succ}, \text{Succ}) = \text{Succ}\circ\text{Succ} $$ The projection is $$ \pi_1^2(x_1, x_2) = x_1 $$ The minimization criterion is $$ 0=g(x_1, y)=\pi_1^2(x_1, y) = x_1 $$ however that value depends only on $x_1=0$ and not on $y$, so I see no useful choice $f$ for $f(x_1)=y$. Can you check your definition for $\mu^n$?

Or it means one can pick any number including the smallest one, which depending on your definition of the natural numbers is either $1$ or $0$, so $f$ might be that constant number.