Logic/computability theory is quite good at turning up seemingly special processes with unexpectedly universal outcomes. Goodstein's theorem (already mentioned) is one example. Another is the Matiasevich Matiyasevich theorem that polynomials with integer coefficients produce all computably enumerable sets. One way to state this is that each c.e. set is the set of nonnegative values of such a polynomial.
|
3 | transliterated Matiyasevich the way he does it | ||
|
|
||||
|
|
2 | Changed "range" to "set" | ||
|
Logic/computability theory is quite good at turning up seemingly special processes with unexpectedly universal outcomes. Goodstein's theorem (already mentioned) is one example. Another is the Matiasevich theorem that polynomials with integer coefficients produce all computably enumerable sets. One way to state this is that each c.e. set is the range set of nonnegative values of such a polynomial. |
||||
|
|
1 |
|
||
|
Logic/computability theory is quite good at turning up seemingly special processes with unexpectedly universal outcomes. Goodstein's theorem (already mentioned) is one example. Another is the Matiasevich theorem that polynomials with integer coefficients produce all computably enumerable sets. One way to state this is that each c.e. set is the range of nonnegative values of such a polynomial. |
||||
