## The Turing Machine vs. Lambda Calculus

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

### The Turing Machine vs. Lambda Calculus

The Turing Machine vs. Lambda Calculus, which is the superior formal model of computing? Yes, I know they are equivalent in power but which is superior in style and general amzingness.

I have to go with The Turing Machine.

It's very intuitive and you can explain it to a layman in less than 5 minutes. Further, it's amazing to me that such a simple concept is so deep. The idea of formalizing an abstract machine for the purpose of studying computation is just really cool and was fairly revolutionary at the time. Also, it forms the theoretical basis for operations at the actual hardware level.

It's just one of those really cool thought-experiments that bore some amazing fruits.

Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

### Re: The Turing Machine vs. Lambda Calculus

Turing Machines blow. Doing *anything* with them is stupid.

Lambda calculus is better, but not by much. Depending on how pure you're being, it can be just as stupid.

BRAINF*CK is the best trivial model of computation.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4021
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: The Turing Machine vs. Lambda Calculus

Xanthir wrote:BRAINF*CK is the best trivial model of computation.

+1 for brainfuck as a model of computation.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
stephentyrone

Posts: 779
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

### Re: The Turing Machine vs. Lambda Calculus

Lambda calculus for me. In fact I'm just working on a Haskell program to translate stuff into lambda for the giggles.

Turing machines are nice and revolutionary for their time, but pretty much the same as any computer that any of us could use; no really novel concepts for anyone who's done any programming.

TNorthover

Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

### Re: The Turing Machine vs. Lambda Calculus

The lambda calculus, because it's (structurally) simpler. And more abstract.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

Briareos

Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

### Re: The Turing Machine vs. Lambda Calculus

Lambda calculus, for actually being useful instead of just another turing tarpit.

You all probably know, but for thoroughness, here's the definition:

• Variables: I'll write these with lowercase letters
• Abstraction: \lambda and .
• Grouping: Parenthesis
• Expressions: Defined by the set \Lambda
• x is a variable \rightarrow x \in \Lambda
• x is a variable \wedge M \in \Lambda \rightarrow (\lambda x.M) \in \Lambda
• M, N \in \Lambda \rightarrow (M N) \in \Lambda

I'll be using usual shorthand when writing expressions.
In addition, I'm going give names to some expressions. These are purely shorthand, meaning the expression can be substituted for the name anywhere in another expression, alpha-converting variables in case of any clashes. Substitution can always be performed and will always terminate, meaning a name will never appear on the right-hand-side of its definition, no matter how often you substitute any other names appearing there.

The definition of the lambda calculus is only seven lines long, but is it useful? Indeed it is. In fact, it's a fully fledged programming language despite being completely abstract and without any relation to any real-world machine, or even mathematics outside of its definition.

So what can we program?

Well, let's start with some simple definitions and see where they take us.

Here's part of a nice abstraction. I like to call it boolean algebra.
TRUE = \lambda x y. x
FALSE = \lambda x y. y

Some syntactic sugar:
IF = \lambda p t f. p t f

- IF TRUE TRUE FALSE -> TRUE TRUE FALSE -> (\lambda x y. x) TRUE FALSE -> TRUE

AND = \lambda x y. IF x y FALSE
OR = \lambda x y. IF x TRUE y
NOT = \lambda x. IF x FALSE TRUE
BOOLEQ = \lambda x y. IF x y (NOT y)

- AND TRUE FALSE -> IF TRUE FALSE FALSE -> TRUE FALSE FALSE -> FALSE
- OR TRUE FALSE -> IF TRUE TRUE FALSE -> TRUE TRUE FALSE -> TRUE
- NOT TRUE -> IF TRUE FALSE TRUE -> TRUE FALSE TRUE -> FALSE
- BOOLEQ FALSE TRUE -> IF FALSE TRUE (NOT TRUE) -> NOT TRUE -> FALSE

CONS = \lambda x y f. f x y
FIRST = \lambda p. p (\lambda x y. x)
SECOND = \lambda p. p (\lambda x y. y)
NIL = \lambda x. TRUE
NIL? = \lambda p. p (\lambda x y. FALSE)

- FIRST (CONS TRUE FALSE) -> CONS TRUE FALSE (\lambda x y. x) -> (\lambda x y. x) TRUE FALSE -> TRUE

Lists of bools are a little boring. Let's define numbers
ZERO = \lambda f x. x
ONE = \lambda f x. f x
PLUS = \lambda m n f x. m f (n f x)
SUCC = \lambda n -> PLUS n ONE
MULT = \lambda m n f x. m (n f) x
SHIFTINC = \lambda p. CONS (SECOND p) (SUCC (SECOND p))
- (P = (CONS ZERO ONE) in:) SHIFTINC P -> CONS (SECOND P) (SUCC (SECOND P)) -> CONS ONE (SUCC ONE)
PRED = \lambda n. FIRST (n SHIFTINC (PAIR 0 0))
SUB = \lambda m n. (n PRED) m
ZERO? = \lambda n. n (CONST FALSE) TRUE
NUMEQ = \lambda m n. AND (ZERO? (SUB m n)) (ZERO? (SUB n m))

Most of you should still be relatively unconfused, I think. Let's define a few more list function. Unfortunately, they're mostly recursive, since lists are a recursive datastructure. We need recursion! Fortunately, lambda calculus has recursion. Of course it does, or it wouldn't be turing-complete!

Y = (\lambda f. (\lambda x. f (x x)) (\lambda x. f (x x)))

Now then, the list functions we all know and love

MAP = Y (\lambda map f l.
IF (NIL? l)
NIL
(CONS (f (FIRST l))
(map f (SECOND l))))

FILTER = Y (\lambda filter p l.
IF (NIL? l)
NIL
(IF (p (FIRST l))
(CONS (FIRST l) (filter p (SECOND l)))
(filter p (SECOND l))))

FOLDL = Y (\lambda foldl f x l.
IF (NIL? l)
x
(foldl f (f x (FIRST l)) (SECOND l)))

I don't know about you, but to me this is starting to look very much like lisp...
Now, to compare what we've got to a few real languages, let's implement sum-of-a-list in a couple of them and lambda calculus.

Code: Select all
sum list = foldl (+) 0 list

Code: Select all
int sum(int[] nums){        int total = 0;        for(int i = 0; i < nums.length; i++){            total += nums[i];        }        return total;    }

- And lambda calculus?
SUM = \lambda list. FOLDL PLUS ZERO list
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Berengal
Superabacus Mystic of the First Rank

Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

### Re: The Turing Machine vs. Lambda Calculus

To be fair, a similar analysis could be applied to Turing machines, depending on the symbol set. The rules for combining two programs would be a little more complicated but really once you've got substitution useful programs arrive quickly.

TNorthover

Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

### Re: The Turing Machine vs. Lambda Calculus

The Turing Machine is nicer, because it's a lot like actual computers, while Lambda Calculus is "out of this world". I doubt you can implement a machine that evaluates lambda expressions natively.

Some things are nice in lambda calculus, though:

1. You can do this kind of elimination:

( λ abc...xyz . (expression that doesn't involve x y z) x y z ) = ( λ abc... . (expression) )

Examples:

MULT = ( λ mnfx . m (n f) x ) = ( λ mnf . m (n f) )
EXP = ( λ mnfx . (n m) f x ) = ( λ mn . n m )

2. The Church numeral 1 is nothing but an empty lambda; when it's evaluated, it just disappears without affecting the rest of the expression:

1 = ( λ fx . fx ) = ( λ f . f )
1 = ( λ . ) ???

3. The Church numeral 0, when evaluated, has the only effect of disappearing the next symbol:

0 = ( λ fx . x )
0 = ( λ f . ) ???
Last edited by EduardoLeon on Tue Oct 13, 2009 10:29 pm UTC, edited 3 times in total.
Gott weiß ich will kein Engel sein!
EduardoLeon

Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú

### Re: The Turing Machine vs. Lambda Calculus

As usual, Berengal is at least twelve times as eloquent as I am when making a point in the C.S. fora.

As to implementing a machine that "natively" deals with the lambda calculus: who cares? The Church-Turing thesis says the two models are equal in power, as the OP already mentioned. The lambda calculus is the better abstraction of computation. I think it makes it easier and nicer to think about computation. Implementation isn't relevant.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

Briareos

Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

### Re: The Turing Machine vs. Lambda Calculus

EduardoLeon wrote:The Turing Machine is nicer, because it's a lot like actual computers, while Lambda Calculus is "out of this world". I doubt you can implement a machine that evaluates lambda expressions natively.

If you consider lisp (specifically scheme) sufficiently close to the \lambda-calculus, then this paper describes just such a machine:
http://dspace.mit.edu/handle/1721.1/5731
rabuf

Posts: 15
Joined: Thu Mar 20, 2008 2:30 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

rabuf wrote:If you consider lisp (specifically scheme) sufficiently close to the -calculus, then this paper describes just such a machine:
http://dspace.mit.edu/handle/1721.1/5731

At some lower level, perhaps at hardware level, computation must be dealt with in an imperative way. Or else, you should build a piece of electronics that can represent natively either a lambda expression or the symbols lambda expressions are made of.
Gott weiß ich will kein Engel sein!
EduardoLeon

Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú

### Re: The Turing Machine vs. Lambda Calculus

EduardoLeon wrote:At some lower level, perhaps at hardware level, computation must be dealt with in an imperative way.

Seriously? Did you even read the paper?

Also: even in a normal commercial hardware, at the lowest levels, there is rather little "imperative" structure. Big swaths of chip area are dedicated to functionality that allows a processor to behave as though it had cohesive state and acted in a strictly imperative fashion.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
stephentyrone

Posts: 779
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

### Re: The Turing Machine vs. Lambda Calculus

Skip the lambda calculus and go straight to lisp.
qbg

Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

Nitpick: True Turing Machines have unlimited memory and execution time. (Halting problem loophole!)
Did you get the number on that truck?

phillipsjk

Posts: 1215
Joined: Wed Nov 05, 2008 4:09 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

lambda calculus
littlebuddy

Posts: 43
Joined: Thu Jun 04, 2009 5:40 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

Lots of people seem to be talking about the relative usefulness of Lambda Calculus compared to the Turing Machine. In a matter such as this I think usefulness is highly overrated.

Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

### Re: The Turing Machine vs. Lambda Calculus

There's lots of research still going on in Lambda Calculus. Especially when it comes to types, LC is pretty much the go-to petri dish.

Also, the term language of statically typed functional languages (Haskell and friends) pretty much is LC with sugar on top.

It's not what I'd call useless.

Turing machines on the other hand...
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Berengal
Superabacus Mystic of the First Rank

Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

### Re: The Turing Machine vs. Lambda Calculus

Berengal wrote:There's lots of research still going on in Lambda Calculus. Especially when it comes to types, LC is pretty much the go-to petri dish.
...
It's not what I'd call useless.
Turing machines on the other hand...

Oh I'm not debating whether LC is more useful (in most ways) than the Turing Machine, it is. I was just saying I don't consider 'usefulness' to be one of the major criteria I use as to which one I think is cooler. Largely I like the TM for the historical aspects and ease of explanation. I would never 'use' it for anything (except maybe in the context of a proof).

One question I was thinking of is what would have happened if Turing had never created any of his works or any of his research and we were only left with LC at that time. How far back would that have set the arrival of actually usable computers, if at all? The TM is fairly obviously mappable to an actual machine, LC not so much.

Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

### Re: The Turing Machine vs. Lambda Calculus

0xBADFEED wrote:One question I was thinking of is what would have happened if Turing had never created any of his works or any of his research and we were only left with LC at that time. How far back would that have set the arrival of actually usable computers, if at all? The TM is fairly obviously mappable to an actual machine, LC not so much.

My money is on "not at all". Shannon and Von Neumann (and others) were much more directly responsible for the modern approach to mapping computation onto actual hardware. Complexity Theory would likely look entirely different as a field, though I suspect that many of the same results would have been derived, just with entirely different approaches.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
stephentyrone

Posts: 779
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

### Re: The Turing Machine vs. Lambda Calculus

stephentyrone wrote:
0xBADFEED wrote:One question I was thinking of is what would have happened if Turing had never created any of his works or any of his research and we were only left with LC at that time. How far back would that have set the arrival of actually usable computers, if at all? The TM is fairly obviously mappable to an actual machine, LC not so much.

My money is on "not at all". Shannon and Von Neumann (and others) were much more directly responsible for the modern approach to mapping computation onto actual hardware. Complexity Theory would likely look entirely different as a field, though I suspect that many of the same results would have been derived, just with entirely different approaches.

Agreed. The Turing Machine seems more like an accidental byproduct than an arche. Computers existed before the Turing Machine, and were well into their infancy before the Turing Machine was well known. So while the machine provides a succinct and easy to understand mapping between the physical devices and a mathematical concept, it wasn't the inspiration for either, and both existed before the machine did.

At least this is how I've interpreted the history. I don't have much hard evidence to back it up.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Berengal
Superabacus Mystic of the First Rank

Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

### Re: The Turing Machine vs. Lambda Calculus

I am pretty shocked a little that so little teaching resources concerning Lambda Calculus can be found on the Internet. Considering how mind-bogglingly useful it is it really amazes me...
Sir_Elderberry wrote:Cords are not just bendy cylinders. They are flexible, animate beings possessed by spirits whose intentions are beyond our ken. They are Cthulu's tentacles intruding on our reality.
LakatosIstvan

Posts: 87
Joined: Tue Jun 03, 2008 5:54 pm UTC
Location: Sector ZZ9 Plural Z Alpha

### Re: The Turing Machine vs. Lambda Calculus

LakatosIstvan wrote:I am pretty shocked a little that so little teaching resources concerning Lambda Calculus can be found on the Internet. Considering how mind-bogglingly useful it is it really amazes me...

Speaking of which, does anyone have a preferred resource they'd care to point me towards for learning more about the lambda calculus? I'm mid-way through my CS bachelors now, and I'm not entirely sure if we'll ever be covering it (we're doing the assorted categories of automota in Discrete Structures now, starting wih FSAs and working up towards the Turing machine), so a good read I can find online would be much appreciated.
bieber

Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Re: The Turing Machine vs. Lambda Calculus

bieber wrote:Speaking of which, does anyone have a preferred resource they'd care to point me towards for learning more about the lambda calculus?

Sushi's Universal Logic Catalogue – The Ultimate Lambda Pow(d)ers
Code: Select all
#include <stdio.h>int main(){ struct { unsigned a:3, b:3, c:2; } n = {0};  do do printf("%hhu\n", *&n);  while(!(n.a-- && !++n.b));  while(++n.c);  return 0; }

hotaru

Posts: 932
Joined: Fri Apr 13, 2007 6:54 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

hotaru wrote:
bieber wrote:Speaking of which, does anyone have a preferred resource they'd care to point me towards for learning more about the lambda calculus?

Sushi's Universal Logic Catalogue – The Ultimate Lambda Pow(d)ers

From what I understood, this is more about A++, you know, the implementation of the generalization of lambda calculus.

But thanks for the hint. A++ now became my favorite programming language
Sir_Elderberry wrote:Cords are not just bendy cylinders. They are flexible, animate beings possessed by spirits whose intentions are beyond our ken. They are Cthulu's tentacles intruding on our reality.
LakatosIstvan

Posts: 87
Joined: Tue Jun 03, 2008 5:54 pm UTC
Location: Sector ZZ9 Plural Z Alpha

### Re: The Turing Machine vs. Lambda Calculus

Please compose your next post on a machine designed around Lambda Calculus. Thank you.

Posts: 69
Joined: Sat Nov 21, 2009 5:31 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

Historical precedent is not proof of superiority. Just because the designers of circuits made processors act more similarly to Turing machines doesn't imply that Turing machines are somehow better. There's no reason we can't build a lambda calculator, it's just not what we've geared ourselves to do, and since there are lovely compilers for functional languages that work on Turing machine-like computers, I don't think we ever will.
The same as the old Meteorswarm, now with fewer posts!

Meteorswarm

Posts: 980
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

### Re: The Turing Machine vs. Lambda Calculus

Turing machines are too boring; combinator calculus is much more interesting.
qbg

Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

My vote is with the Lambda Calculus.

First of all, I just find this to be pretty:
(\lambda mnfx.mf(nfx))(\lambda fx.f(f(fx)))\lambda fx.(f(f(f(f(fx)))))
Second, the entire state of, and everything you need to know about the computer is recorded within a single algebraic expression--that's elegance that a Turing Machine can never possess.

Thirdly, the Lambda Calculus is useful, simple (and dare I say fun) as Berengal pointed out so well.
afarnen

Posts: 157
Joined: Mon May 05, 2008 12:12 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

Aren't LC and TM equivalent in power in precisely the same way that Lisp and Brainfuck are?
ochuckles

Posts: 8
Joined: Sun Nov 14, 2010 9:24 pm UTC

### Re: The Turing Machine vs. Lambda Calculus

ochuckles wrote:Aren't LC and TM equivalent in power in precisely the same way that Lisp and Brainfuck are?

Well, we're in for a shock if they aren't, since that's the Church Turing hypothesis.

afarnen wrote:
(\lambda mnfx.mf(nfx))(\lambda fx.f(f(fx)))\lambda fx.(f(f(f(f(fx)))))

Can someone well-versed in the lambda calculus explain what they does? It just looks like a mess to me.
...And that is how we know the Earth to be banana-shaped.

Robert'); DROP TABLE *;

Posts: 635
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

### Re: The Turing Machine vs. Lambda Calculus

Robert'); DROP TABLE *; wrote:
afarnen wrote:
(\lambda mnfx.mf(nfx))(\lambda fx.f(f(fx)))\lambda fx.(f(f(f(f(fx)))))

Can someone well-versed in the lambda calculus explain what they does? It just looks like a mess to me.

I would hardly consider myself well-versed, but it looks like the above expression is equivalent to
\lambda fx.(f(f(f(f(f(f(f(fx))))))))

which is the function that takes a function and a second argument, and applies the function to the second argument 8 times. Don't ask me why this is useful, though I'm sure it serves some purpose. Attaching some variable names would be nice.

And Lambda Calculus is better.

scarecrovv

Posts: 588
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: Massachusetts

### Re: The Turing Machine vs. Lambda Calculus

Has anybody read To Mock a Mockingbird by Raymond Smullian? It's an introduction to lambda calculus in the form of puzzles about birds. I've been enjoying working through it.
It Should Be Real wrote:Fuck the wizard.
We're doing this manually.

http://www.hexifact.co.uk - Hacking blog: in which I take some things apart, and put other things together.

Ptolom

Posts: 1428
Joined: Mon Mar 24, 2008 1:55 pm UTC
Location: The entropy pool (Leicester)

### Re: The Turing Machine vs. Lambda Calculus

scarecrovv wrote:which is the function that takes a function and a second argument, and applies the function to the second argument 8 times. Don't ask me why this is useful, though I'm sure it serves some purpose.

It's the Church numeral for 8. It's just a way of embedding arithmetic in lambda calculus (like how the finite ordinals are a way of embedding arithmetic in set theory).

Specifically, afarnen's lambda thing is representing 3+5 - \lambda m n f x. m f (n f x) is addition, in that if you apply it to two Church numerals, it'll evaluate to the Church numeral representing their sum.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia