0

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$.

Kasia
  • 3
  • To answer your second question one would need the meaning of $\mu^n$ (how does it minimize, what role plays $n$) and $\pi_i^n$ (what role play $i$ and $n$?) – mvw Dec 26 '15 at 13:38
  • 1
    Thinking again, what would $o_2^5$ do? Please provide the full definition for it. – mvw Dec 26 '15 at 13:40
  • Already I completed the content. – Kasia Dec 26 '15 at 17:19

1 Answers1

0

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.

mvw
  • 34,562