2
$\begingroup$

I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural programming (any problem you can solve with one can be solved with another).

I'm curious as to how this conclusion was originally derived, and whether there is a conclusive proof as to this (preferably one that a bit of a newb to lambda calculus like me can understand)

Related: Why are functional languages Turing complete

$\endgroup$
4
  • $\begingroup$ Doesn't the linked question answer your question? Perhaps I'm not understanding what your question is or why the answers there didn't meet your needs. $\endgroup$ – D.W. Jan 4 at 6:42
  • $\begingroup$ From what I could understand, they were mostly talking about why people use Turing completeness as a basis of computation, but I'm curious as to how this was proven/supposed. It may answer that question, but I certainly didn't understand the answer :) $\endgroup$ – Java Machine Jan 4 at 14:40
  • $\begingroup$ Are you asking how to prove that a particular functional programming language is Turing-complete? If so it would help to tell us which one you want to see a proof for. Have you looked at turing-completeness to look through the resources there? It basically amounts to writing code for a simulator of a Turing machine (or of any other Turing-complete language), which can get a little bit boring... $\endgroup$ – D.W. Jan 4 at 20:25
  • $\begingroup$ thanks, thats very helpful, can u put it as an answer so I can accept $\endgroup$ – Java Machine Jan 5 at 0:06
1
$\begingroup$

One standard way to prove that a language is Turing-complete is to implement a simulator for a Turing machine (or for any other Turing-complete language) in that language. That is typically straightforward but boring, for most general-purpose languages.

You can find more resources on Turing-completeness in ; see especially, e.g., Is there an algorithm for converting Turing machines into equivalent Lambda expressions?. You might also be interested in Which calculus is based on first-order functions and is Turing complete?, Are there minimum criteria for a programming language being Turing complete?, What does being Turing complete mean?, Are all turing complete languages interchangeable, Clear, complete, proof that a language is Turing Compete?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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