User:IssaRice/Computability and logic/S–m–n theorem - Revision history

https://machinelearning.subwiki.org/w/index.php?action=history&feed=atom&title=User%3AIssaRice%2FComputability_and_logic%2FS%E2%80%93m%E2%80%93n_theorem User:IssaRice/Computability and logic/S–m–n theorem - Revision history 2026-06-05T20:27:30Z Revision history for this page on the wiki MediaWiki 1.41.2 https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=2041&oldid=prev IssaRice at 20:23, 22 May 2019 2019-05-22T20:23:45Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:23, 22 May 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3">Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In other words, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In other words, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e <del style="font-weight: bold; text-decoration: none;">(</del>x,y<del style="font-weight: bold; text-decoration: none;">) = </del>x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e<del style="font-weight: bold; text-decoration: none;">(</del>x<del style="font-weight: bold; text-decoration: none;">,3) = </del>x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e <ins style="font-weight: bold; text-decoration: none;">= \lambda </ins>x,y <ins style="font-weight: bold; text-decoration: none;">. </ins>x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e <ins style="font-weight: bold; text-decoration: none;">= \lambda </ins>x<ins style="font-weight: bold; text-decoration: none;">.</ins>x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in. e.g. if we have <code>def f(x, y): return x + y</code> and we want <code>y=3</code>, we can easily transform this into <code>def g(x): y=3; return x + y</code>. To perform this translation, all we needed was the original source code (for <code>f</code>) as well as the value we are substituting (<code>y=3</code>). The ''s''–''m''–''n'' theorem claims that (1) the result is computable (is a computer program); and (2) the transformation is primitive recursive (can be computed using only bounded loops).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in. e.g. if we have <code>def f(x, y): return x + y</code> and we want <code>y=3</code>, we can easily transform this into <code>def g(x): y=3; return x + y</code>. To perform this translation, all we needed was the original source code (for <code>f</code>) as well as the value we are substituting (<code>y=3</code>). The ''s''–''m''–''n'' theorem claims that (1) the result is computable (is a computer program); and (2) the transformation is primitive recursive (can be computed using only bounded loops).</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=2040&oldid=prev IssaRice at 20:22, 22 May 2019 2019-05-22T20:22:50Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:22, 22 May 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l5">Line 5:</td> <td colspan="2" class="diff-lineno">Line 5:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in. e.g. if we have <code>def f(x, y): return x + y</code> and we want <code>y=3</code>, we can easily transform this into <code>def g(x): y=3; return x + y</code>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in. e.g. if we have <code>def f(x, y): return x + y</code> and we want <code>y=3</code>, we can easily transform this into <code>def g(x): y=3; return x + y</code><ins style="font-weight: bold; text-decoration: none;">. To perform this translation, all we needed was the original source code (for <code>f</code>) as well as the value we are substituting (<code>y=3</code>). The ''s''–''m''–''n'' theorem claims that (1) the result is computable (is a computer program); and (2) the transformation is primitive recursive (can be computed using only bounded loops)</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=2039&oldid=prev IssaRice at 20:21, 22 May 2019 2019-05-22T20:21:00Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:21, 22 May 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l5">Line 5:</td> <td colspan="2" class="diff-lineno">Line 5:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in<ins style="font-weight: bold; text-decoration: none;">. e.g. if we have <code>def f(x, y): return x + y</code> and we want <code>y=3</code>, we can easily transform this into <code>def g(x): y=3; return x + y</code></ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=2038&oldid=prev IssaRice at 20:19, 22 May 2019 2019-05-22T20:19:43Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:19, 22 May 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">In terms of programming, the ''s''–''m''–''n'' theorem says that if we start out with a computer program taking several arguments, then we can transform the source code of the program into another computer program that does the same thing except with some of the variables filled in.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=2037&oldid=prev IssaRice at 20:18, 22 May 2019 2019-05-22T20:18:16Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:18, 22 May 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2">Line 2:</td> <td colspan="2" class="diff-lineno">Line 2:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In other words, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In other words, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">To give an example, suppose we start out with the function <math>\varphi_e (x,y) = x+y</math>. Then we can "fill in" one of the variables with a value, e.g. by taking <math>y=3</math>. Now we have <math>\varphi_e(x,3) = x+3</math>. The ''s''–''m''–''n'' theorem claims that this resulting function is also computable. It also says that we can find the source code of this new function using <math>e</math> (the original source code) and 3 (the value we are substituting).</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=1138&oldid=prev IssaRice at 07:13, 18 December 2018 2018-12-18T07:13:10Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:13, 18 December 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The '''''s''–''m''–''n'' theorem''' (also called the '''parametrization 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>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The '''''s''–''m''–''n'' theorem''' (also called the '''parametrization 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>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Roughly speaking</del>, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">In other words</ins>, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=1137&oldid=prev IssaRice at 07:10, 18 December 2018 2018-12-18T07:10:52Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:10, 18 December 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l6">Line 6:</td> <td colspan="2" class="diff-lineno">Line 6:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''s''–''m''–''n'' theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Different kinds of proofs:</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Tape/register-based way</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Using recursive functions and ways of encoding them</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=1134&oldid=prev IssaRice: /* Etymology */ 2018-12-18T07:06:02Z

<p><span dir="auto"><span class="autocomment">Etymology</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:06, 18 December 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l9">Line 9:</td> <td colspan="2" class="diff-lineno">Line 9:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The name "''s''–''m''–''n''" comes from the notation <math>s^m_n</math> (<math>s^n_m</math> in some texts) for the function that finds the new index.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The name "''s''–''m''–''n''" comes from the notation <math>s^m_n</math> (<ins style="font-weight: bold; text-decoration: none;">denoted </ins><math>s^n_m</math> in some texts) for the function that finds the new index.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><references/></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><references/></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=1133&oldid=prev IssaRice at 07:05, 18 December 2018 2018-12-18T07:05:28Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:05, 18 December 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The '''<del style="font-weight: bold; text-decoration: none;">s–m–n </del>theorem''' (also called the '''parametrization 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>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The '''<ins style="font-weight: bold; text-decoration: none;">''s''–''m''–''n'' </ins>theorem''' (also called the '''parametrization 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>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Roughly speaking, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Roughly speaking, the theorem states that if we start out with a computable partial function <math>\varphi_e</math> of <math>m+n</math> variables, then we can fill in <math>m</math> of the variables with actual values. When we do this, the resulting <math>n</math>-place partial function continues to be computable. Moreover, we can find the index of this new partial function in terms of the old index and the values in a primitive recursive way.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The <del style="font-weight: bold; text-decoration: none;">s–m–n </del>theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The <ins style="font-weight: bold; text-decoration: none;">''s''–''m''–''n'' </ins>theorem is essentially the same thing as currying in functional programming languages.<ref>https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying</ref></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The <del style="font-weight: bold; text-decoration: none;">s–m–n </del>theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The <ins style="font-weight: bold; text-decoration: none;">''s''–''m''–''n'' </ins>theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The name "<del style="font-weight: bold; text-decoration: none;">s–m–n</del>" comes from the notation <math>s^m_n</math> (<math>s^n_m</math> in some texts) for the function that finds the new index.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The name "<ins style="font-weight: bold; text-decoration: none;">''s''–''m''–''n''</ins>" comes from the notation <math>s^m_n</math> (<math>s^n_m</math> in some texts) for the function that finds the new index.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><references/></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><references/></div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/S%E2%80%93m%E2%80%93n_theorem&diff=1131&oldid=prev IssaRice at 06:51, 18 December 2018 2018-12-18T06:51:59Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 06:51, 18 December 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7">Line 7:</td> <td colspan="2" class="diff-lineno">Line 7:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The s–m–n theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The s–m–n theorem, together with the universal function, is useful for proving other theorems and also to avoid the arbitrariness of the specific encoding used.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==Etymology<del style="font-weight: bold; text-decoration: none;">=</del>==</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==Etymology==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The name "s–m–n" comes from the notation <math>s^m_n</math> (<math>s^n_m</math> in some texts) for the function that finds the new index.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The name "s–m–n" comes from the notation <math>s^m_n</math> (<math>s^n_m</math> in some texts) for the function that finds the new index.</div></td></tr> </table>

IssaRice