1
$\begingroup$

So I'm currently taking discrete math II at my university and I came across a somewhat philosophical question (so I apologize if this is question is hard to answer precisely) of whether mathematicians and computer scientists view computation in the same way.

We computer scientists define computation with the Turing machine and/or lambda calculus. I was simply wondering if there is some language/notation (lambda calculus??) that allows a mathematician to write a computable (i.e. Turing computable) program using only one mathematical expression.

Again, I apologize if that's a bit of an abstract question (I'm new to these concepts and my terminology isn't great) but let me try to clarify: in math (or at least when I did math in school), there isn't the notion of control flow over time with different statements--there is only a single expression that evaluates to a value. Evaluating the expression may involve partially evaluating nested expressions in a certain order but the end result and the expression itself represented computation in some sort.

So now my question is this:

(Through the use of lambda calculus) is it possible to write any program (i.e. Turing complete) using only one expression with no more than one statement? Is lambda calculus set up in a way that removes or hides the notion of control flow?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ The lambda calculus doesn't have any notion of "statement". There are only expressions, so every program is a single expression in the lambda calculus. $\endgroup$ – Derek Elkins left SE Jan 25 '18 at 7:40
  • $\begingroup$ @DerekElkins thanks! that's what I thought and exactly what I wanted to hear. Post that as an answer and I'll accept it. I'm writing a paper so if you could possibly provide a source for that info, I'd be very grateful! $\endgroup$ – Rico Kahler Jan 25 '18 at 7:45
2
$\begingroup$

I think that your general question is pretty broad, because you'd need to specify what you consider a program (e.g. is the identity function that outputs the input it receives a program?).

It is possible to have some sort of control flow in lambda expressions (there are only expressions in lambda calculus); consider e.g. Church Booleans that enable conditionals.

If you would like to see examples of lambda calculus expressions put to work like regular programs, I can recommend John Tromp's binary lambda calculus. I have been able to evaluate some of his programs using plain β-reductions (examples), so I can say it's definitely possible to write programs even with pure lambda calculus.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry for not specifying more explicitly but by "any program" I meant Turing complete $\endgroup$ – Rico Kahler Jan 25 '18 at 8:05
  • $\begingroup$ @RicoKahler Turing completeness is not a feature of programs, but programming languages... unless you mean a program simulating a Turing machine (e.g. a brain**** interpreter), but I have seen those written in different variations of lambda calculus too (e.g. in the binary lambda calculus link in the answer) :). $\endgroup$ – ljedrz Jan 25 '18 at 8:09
  • $\begingroup$ Ah I see. that makes sense but by "program" I think I meant the actual 'source code' not the abstract idea of a program. I guess I'm specifically asking for two things now: 1) is lambda calculus "source code" one big expression (i.e. no assignment or statements) 2) is lambda calculus (the programming language??) turing complete. oh man terminology is tough. thanks for you help! $\endgroup$ – Rico Kahler Jan 25 '18 at 8:16
  • $\begingroup$ @RicoKahler yes, lambda calculus programs are just single (not necessarily big; I was amazed at how small they can be) expressions and lambda calculus itself is indeed Turing-complete. $\endgroup$ – ljedrz Jan 25 '18 at 8:22
  • $\begingroup$ very interesting. side question: I'm looking to get more into pure functional programming. would you recommend learning haskell or some lambda calculus first? $\endgroup$ – Rico Kahler Jan 25 '18 at 8:30

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.