A programming language is said to be Turing Completeness if it can successfully simulate a universal TM. Let's take functional programming language for example.

In functional programming, function has highest priority over anything. You can pass functions around like any primitives or objects. This is called first class function.

In functional programming, your function does not produce side effect i.e. output strings onto screen, change the state of variables outside of its scope. Each function has a copy of its own objects if the objects are passed from the outside, and the copied objects are returned once the function finishes its job. Each function written purely in functional style is completely independent to anything outside of it. Thus, the complexity of the overall system is reduced. This is referred as referential transparency.

In functional programming, each function can have its local variables kept its values even after the function exits. This is done by the garbage collector. The value can be reused the next time the function is called again. This is called memoization.

A function usually should solve only one thing. It should model only one algorithm to answer a problem. Do you think that a function in a functional language with the above properties simulates a Turing Machine?

  • Functions (= algorithms = Turing Machines) are able to be passed around as input and returned as output. TM also accepts and simulate other TMs
  • Memoization models the set of states of a Turing Machine. The memorized variables can be used to determine states of a TM (i.e. which lines to execute, what behavior should it take in a give state ...). Also, you can use memoization to simulate your internal tape storage. In language like C/C++, when a function exits, you lose all of its internal data (unless you store it elsewhere outside of its scope).
  • The set of symbols are the set of all strings in a programming language, which is the higher level and human-readable version of machine code (opcode)
  • Start state is the beginning of the function. However, with memoization, start state can be determined by memoization or if you want, switch/if-else statement in imperative programming language. But then, you can't
  • Final accepting state when the function returns a value, or rejects if an exception happens. Thus, the function (= algorithm = TM) is decidable. Otherwise, it's undecidable. I'm not sure about this. What do you think?

Is my thinking true on all of this?

The reason I bring function in functional programming because I think it's closer to the idea of TM.

What experience with other programming languages do you have which make you feel the idea of TM and the ideas of Computer Science in general? Can you specify how you think?

  • 1
    I think you do not need so many different concepts to prove that functional programming languages are Turing complete. AFAIK the lambda-calculus is the simplest example of a functional programming language. You can look up the proof that the lambda-calculus is equivalent to a Turing machine in a text book about the theory of computability.
    – Giorgio
    Commented Jun 17, 2012 at 17:43
  • 1
    See also cstheory.stackexchange.com/questions/625/…
    – Giorgio
    Commented Jun 17, 2012 at 17:45
  • 10
    I'm confused, what is the question? Commented Jun 17, 2012 at 17:50
  • @Austin Henley: Yes the question is not very clear. I have interpreted it as "How to prove that functional programming languages are Turing complete", but maybe this is not what the OP had in mind.
    – Giorgio
    Commented Jun 17, 2012 at 17:59
  • You can think that I'm finding the relationship between concepts, from Turing Machine applied to programming language, and functional programming language as an example. I'm not sure my thinking is correct, so I ask to verify and having additional info. The link on cstheory is pretty good for me.
    – Amumu
    Commented Jun 17, 2012 at 18:11

2 Answers 2


What experience with other programming languages do you have which make you feel the idea of TM and the ideas of Computer Science in general? Can you specify how you think?

There is the structured program theorem, which ties pretty much any procedural programming language directly to Turing Machines. As you hinted, functional languages are tied to TMs via lambda calculus. And there rather few languages that are Turing-complete and can't be trivially translated into either procedural or functional programming (hi there, Prolog).

For me, the main implication is that independently of technology and programming language, there are very few problems that can't be solved. This makes me hate people who say that something is impossible :)

  • I have little experience with functional programming. But after studying about Turing Machine, I feel there is close relationship with functional language. Now I know it is tied via lambda. I will take time to learn lambda calculus carefully in my free time.
    – Amumu
    Commented Jun 17, 2012 at 18:22
  • 6
    Very few problems that can't be solved? Actually, there are uncountably many: just compare the cardinality of all functions f : N -> N (N is the set of natural numbers) with the cardinality of all programs written in a given programming language.
    – Giorgio
    Commented Jun 17, 2012 at 19:39

The reason I bring function in functional programming because I think it's closer to the idea of TM.

I'm not sure that I agree with that. It's very easy to overthink the issue and try to apply modern computer science concepts to what is, after all, a foundation. Turing described a stateful, imperative machine. I've always thought that Church's approach was more the genesis of FP.

If you want to get a "feel" for Turing machines, I suggest that you reflect upon complex mechanical automata and, in software, work with state machines.

  • Yes, the lambda calculus is the genesis of functional programming. However, even Turing machines are naturally expressed in terms of functions; the formal definition of a Turing machine is just a tuple of some sets, symbols and a transition function. Commented Jun 17, 2012 at 20:18
  • 1
    I consider Turing's original paper to be definitive, not Wikipedia. His paper uses a tape and transition tables: cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf Commented Jun 17, 2012 at 22:52
  • 2
    @LarryOBrien The tuple definition is not Wikipedia. I read it in Hopcroft & Ullman's book. I think it's a good formal definition.
    – Amumu
    Commented Jun 18, 2012 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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