<blockquote>
  <p>But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?</p>
</blockquote>

<p>These are <strong>excellent</strong> questions! The best answer your question is for you to read Turing's 1936 paper <a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf"><em>On Computable Numbers, With an Application to the Entscheidungsproblem</em></a>. It's a very surprisingly readable and accessible paper, and it is concerned with precisely this question. </p>

<p>To gloss the paper, there is no way to give a purely mathematical characterization of the computable functions, because what is computable is partly a question of <em>physics</em> -- it matters what sorts of computers we can build to compute with. </p>

<p>But something we can do is to think about the operations humans perform when doing computations, and once we have a list of these, then we can build a mathematical model of a machine performing these kinds of actions (as a state-transition system). Then we can mathematically analyze this model, of course -- for example to compare it with other proposed formalisms. Turing performed such an analysis, and built a model of the situation where you have a piece of paper and a pencil, and are permitted to write on the paper, and to read what you have written and perform new actions based on what you have read. </p>

<p>All of these operations are obviously physically realizable, and it turns out that (for number-computability) that all the various proposed models of computation, such as Turing machines, Church's lambda calculus, Post's rewriting systems, and Godel's systems of guarded equations are all equivalent. </p>

<p>So that's why people think that Turing-completeness = computability. However, note that it is not <em>a priori</em> impossible that we might discover some new physical principle letting us build machines that could let us decide the halting problem. If we did, then we would be compelled to revisit our definition of computability. (Or more likely, have the super-intelligent noncomputable AI we build using such exotic physics revisit the definitions for us!)</p>

CC BY-SA 3.0
2016-07-08T13:32:57.130Z
2016-07-08T13:32:57.130Z
Neel Krishnaswami
<p>In High School Computing I was taught the <a href="https://en.wikipedia.org/wiki/Structured_program_theorem" rel="nofollow noreferrer">Structured Program Theorem</a> - that you could implement any mathematical operation using:</p>

<ol>
<li>Sequence</li>
<li>Selection</li>
<li>Iteration</li>
</ol>

<p>After completing a Computer Science degree - we can express what is required for any computable function more formally with <a href="https://en.wikipedia.org/wiki/%CE%9C-recursive_function" rel="nofollow noreferrer">M-recursive functions</a>: </p>

<ol>
<li>The constant $0$ function</li>
<li>The successor function</li>
<li>Selecting parameters</li>
<li>Function composition</li>
<li>Primitive Recursion</li>
<li>The $\mu$-operator (look for the smallest $x$ such that...)</li>
</ol>

<p>This being the <a href="https://cs.stackexchange.com/a/995/1709">minimal set of axioms</a>. Translating this to code we get:</p>

<ol>
<li>The constant <code>0</code></li>
<li>Incrementation <code>_ + 1</code></li>
<li>Variable access <code>x</code></li>
<li>Program/statement concatenation <code>_; _</code></li>
<li>Countdown loops <code>for ( x to 0 ) do _ end</code></li>
<li>While loops <code>while ( x != 0 ) do _ end</code></li>
</ol>

<p>But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?</p>

<p>(Noting of course that </p>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/36090/how-is-lambda-calculus-a-specific-type-of-term-writing-system">Lambda Calculus is a subset</a> of Term rewriting, </li>
<li>that <a href="https://mathematica.stackexchange.com/questions/119933/why-did-the-mathematica-language-choose-term-rewriting-instead-of-the-lambda-cal">Mathematica chose Term-writing over Lambda Calculus</a> as its foundation,    </li>
<li>and recent work in <a href="https://en.wikipedia.org/wiki/Univalent_foundations" rel="nofollow noreferrer">Univalent Foundations</a>. )</li>
</ul>

<p>My question is: <strong>Can all mathematical operations be encoded with a Turing Complete language?</strong></p>

CC BY-SA 3.0
2016-07-08T14:44:09.177Z
By "mathematical operations" you actually mean "computable functions", right?
chi
CC BY-SA 3.0
2016-07-08T21:57:32.920Z
Well part of my question is 'what is a computable function and what are the limits of that'? So I went back to something more operational.
hawkeye
<computability><lambda-calculus><turing-machines>
Can all mathematical operations be encoded with a Turing Complete language?
hawkeye
# Can all mathematical operations be encoded with a Turing Complete language?

(Asked by: username_0 on 2016-07-08)

In High School Computing I was taught the [Structured Program Theorem](https://en.wikipedia.org/wiki/Structured_program_theorem) - that you could implement any mathematical operation using:

1. Sequence
2. Selection
3. Iteration

After completing a Computer Science degree - we can express what is required for any computable function more formally with [M-recursive functions](https://en.wikipedia.org/wiki/%CE%9C-recursive_function):

1. The constant $0$ function
2. The successor function
3. Selecting parameters
4. Function composition
5. Primitive Recursion
6. The $\mu$-operator (look for the smallest $x$ such that...)

This being the [minimal set of axioms](https://cs.stackexchange.com/a/995/1709). Translating this to code we get:

1. The constant `0`
2. Incrementation `_ + 1`
3. Variable access `x`
4. Program/statement concatenation `_; _`
5. Countdown loops `for ( x to 0 ) do _ end`
6. While loops `while ( x != 0 ) do _ end`

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

(Noting of course that

* [Lambda Calculus is a subset](https://cstheory.stackexchange.com/questions/36090/how-is-lambda-calculus-a-specific-type-of-term-writing-system) of Term rewriting,
* that [Mathematica chose Term-writing over Lambda Calculus](https://mathematica.stackexchange.com/questions/119933/why-did-the-mathematica-language-choose-term-rewriting-instead-of-the-lambda-cal) as its foundation,
* and recent work in [Univalent Foundations](https://en.wikipedia.org/wiki/Univalent_foundations). )

My question is: **Can all mathematical operations be encoded with a Turing Complete language?**

**Tags:** computability, lambda-calculus, turing-machines

> **Comments:**
> **username_1**: By "mathematical operations" you actually mean "computable functions", right?  
> **username_0**: Well part of my question is 'what is a computable function and what are the limits of that'? So I went back to something more operational.  

---

## 1 answers

### Answer by username_2 on 2016-07-08. Score: 8 | Accepted answer

> But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

These are **excellent** questions! The best answer your question is for you to read Turing's 1936 paper [*On Computable Numbers, With an Application to the Entscheidungsproblem*](https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf). It's a very surprisingly readable and accessible paper, and it is concerned with precisely this question.

To gloss the paper, there is no way to give a purely mathematical characterization of the computable functions, because what is computable is partly a question of *physics* -- it matters what sorts of computers we can build to compute with.

But something we can do is to think about the operations humans perform when doing computations, and once we have a list of these, then we can build a mathematical model of a mausername_1ne performing these kinds of actions (as a state-transition system). Then we can mathematically analyze this model, of course -- for example to compare it with other proposed formalisms. Turing performed such an analysis, and built a model of the situation where you have a piece of paper and a pencil, and are permitted to write on the paper, and to read what you have written and perform new actions based on what you have read.

All of these operations are obviously physically realizable, and it turns out that (for number-computability) that all the various proposed models of computation, such as Turing mausername_1nes, Church's lambda calculus, Post's rewriting systems, and Godel's systems of guarded equations are all equivalent.

So that's why people think that Turing-completeness = computability. However, note that it is not *a priori* impossible that we might discover some new physical principle letting us build mausername_1nes that could let us decide the halting problem. If we did, then we would be compelled to revisit our definition of computability. (Or more likely, have the super-intelligent noncomputable AI we build using such exotic physics revisit the definitions for us!)


---

