User:IssaRice/Computability and logic/S–m–n theorem: Difference between revisions
(Created page with "The '''s–m–n theorem'''") |
No edit summary |
||
| Line 1: | Line 1: | ||
The '''s–m–n theorem''' | The '''s–m–n theorem''' states that if <math>\varphi_e</math> is an <math>(m+n)</math> place [[../Computable partial function|computable partial function]] and <math>a_1,\ldots,a_m</math> are natural numbers, then there exists a [[../Primitive recursive function|primitive recursive function]] <math>s^m_n</math> such that <math>\varphi_{s^m_n(e,a_1,\ldots,a_m)} \simeq \lambda y_1 \cdots y_n [\varphi_e(x_1,\ldots,x_m,y_1,\ldots,y_n)]</math>. | ||
Revision as of 06:38, 18 December 2018
The s–m–n theorem states that if is an place computable partial function and are natural numbers, then there exists a primitive recursive function such that .
![{\displaystyle \varphi _{s_{n}^{m}(e,a_{1},\ldots ,a_{m})}\simeq \lambda y_{1}\cdots y_{n}[\varphi _{e}(x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da691513388a92532626fe4d68fc835a2f6bd5c3)