Révision 198 CSL17/preliminaries.tex
| preliminaries.tex (revision 198) | ||
|---|---|---|
| 156 | 156 |
|
| 157 | 157 |
where $\mu y.h(\vec u; \vec x , y)\mod 2 = 0$ is the least $y$ such that the equality holds. |
| 158 | 158 |
|
| 159 |
We will denote this function $f$ as $\mu y^{+1} . h(\vec u ; \vec x , y) =_2 0$.
|
|
| 160 |
|
|
| 159 | 161 |
If $\Phi$ is a class of functions, we denote by $\mubc(\Phi)$ the class obtained as $\mubc$ but adding $\Phi$ to the set of initial functions. |
| 160 | 162 |
|
| 161 | 163 |
\item For each $i\geq 0$, $\mubc^i$ is the set of $\mubc$ functions obtained by at most $i$ applications of predicative minimization. So $\mubc^0=BC$ and $\mubc =\cup_i \mubc^i$. |
| ... | ... | |
| 163 | 165 |
\end{definition}
|
| 164 | 166 |
One then obtains: |
| 165 | 167 |
\begin{theorem}[\cite{BellantoniThesis, Bellantoni95}]
|
| 166 |
The class of functions representable by $\mubc$ programs is $\fph$, and for each $i$ the class representable by $\mubc^i$ programs is $\fphi{i}$.
|
|
| 168 |
The class of functions representable by $\mubc$ programs is $\fph$, and for each $i\geq 1$ the class representable by $\mubc^{i-1}$ programs is $\fphi{i}$.
|
|
| 167 | 169 |
\end{theorem}
|
| 168 | 170 |
We will also need an intermediary lemma, also proved in \cite{BellantoniThesis}.
|
| 169 | 171 |
\begin{definition}
|
Formats disponibles : Unified diff