 Home

Codex Wiki

Mathematics

Area of mathematics

Foundations of mathematics

Computability theory

{c}
{wiki=Smn_theorem}

The S-m-n theorem says that fixed inputs can be compiled into program codes by a total computable transformation. For every $m,n\geq1$, there is a total computable $s_n^m$ such that
$$
f_{s_n^m(e,x_1,\ldots,x_m),n}(y_1,\ldots,y_n)
=f_{e,m+n}(x_1,\ldots,x_m,y_1,\ldots,y_n)
$$
whenever either side is defined.


S-m-n theorem

Many-one completeness of the halting problem

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 25 / 1 / Solution

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 27 / 3 / Solution

Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 25 / 1 / Solution

Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 20 / 1 / Solution

Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 120 / 3 / Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 11H / b / Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 11H / c / Solution

Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 4G / a / Solution

Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 4G / b / Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 12H / a / Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 12H / b / Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 12H / c / Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 12H / d / Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 4F / Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 12I / vi / Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 12I / v / Solution

S-m-n theorem

 Ancestors (5)

 Incoming links (17)

 Discussion (0)

 Articles by others on the same topic (0)

S-m-n theorem

 Ancestors (5)

 Incoming links (17)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)