3
$\begingroup$

In High School Computing I was taught the 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:

  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. 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

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

$\endgroup$

closed as off-topic by Kaveh, Radu GRIGore, David Eppstein, Jan Johannsen, Sasho Nikolov Jul 11 '16 at 10:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Radu GRIGore, David Eppstein, Jan Johannsen, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ By "mathematical operations" you actually mean "computable functions", right? $\endgroup$ – chi Jul 8 '16 at 14:44
  • $\begingroup$ 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. $\endgroup$ – hawkeye Jul 8 '16 at 21:57
8
$\begingroup$

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. 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 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.

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.

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 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!)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.