Codex Wiki
OurBigBook.com
Site
Source code
S-m-n theorem
Home
Mathematics
Area of mathematics
Foundations of mathematics
Computability theory
OurBigBook.com
Words: 37
The S-m-n theorem says that fixed inputs can be compiled into program codes by a total computable transformation. For every
m
,
n
≥
1
, there is a total computable
s
n
m
such that
f
s
n
m
(
e
,
x
1
,
…
,
x
m
)
,
n
(
y
1
,
…
,
y
n
)
=
f
e
,
m
+
n
(
x
1
,
…
,
x
m
,
y
1
,
…
,
y
n
)
(28)
whenever either side is defined.
Ancestors
(5)
Computability theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(4)
Many-one completeness of the halting problem
Solution
Solution
Solution