The Turing Machine vs. Lambda Calculus

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

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

The Turing Machine vs. Lambda Calculus

Postby 0xBADFEED » Mon Oct 12, 2009 5:48 pm UTC

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.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby Xanthir » Mon Oct 12, 2009 9:15 pm UTC

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

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

Re: The Turing Machine vs. Lambda Calculus

Postby stephentyrone » Mon Oct 12, 2009 9:44 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby TNorthover » Tue Oct 13, 2009 1:55 pm UTC

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.

User avatar
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

Postby Briareos » Tue Oct 13, 2009 2:04 pm UTC

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.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby Berengal » Tue Oct 13, 2009 5:47 pm UTC

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: [imath]\lambda[/imath] and .
  • Grouping: Parenthesis
  • Expressions: Defined by the set [imath]\Lambda[/imath]
    • x is a variable [imath]\rightarrow x \in \Lambda[/imath]
    • x is a variable [imath]\wedge M \in \Lambda \rightarrow (\lambda x.M) \in \Lambda[/imath]
    • [imath]M, N \in \Lambda \rightarrow (M N) \in \Lambda[/imath]

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 = [imath]\lambda[/imath] x y. x
FALSE = [imath]\lambda[/imath] x y. y

Some syntactic sugar:
IF = [imath]\lambda[/imath] p t f. p t f

- IF TRUE TRUE FALSE -> TRUE TRUE FALSE -> ([imath]\lambda[/imath] x y. x) TRUE FALSE -> TRUE

AND = [imath]\lambda[/imath] x y. IF x y FALSE
OR = [imath]\lambda[/imath] x y. IF x TRUE y
NOT = [imath]\lambda[/imath] x. IF x FALSE TRUE
BOOLEQ = [imath]\lambda[/imath] 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

How about datastructures? We carry on and define linked lists:

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

- FIRST (CONS TRUE FALSE) -> CONS TRUE FALSE ([imath]\lambda[/imath] x y. x) -> ([imath]\lambda[/imath] x y. x) TRUE FALSE -> TRUE

Lists of bools are a little boring. Let's define numbers
ZERO = [imath]\lambda[/imath] f x. x
ONE = [imath]\lambda[/imath] f x. f x
PLUS = [imath]\lambda[/imath] m n f x. m f (n f x)
SUCC = [imath]\lambda[/imath] n -> PLUS n ONE
MULT = [imath]\lambda[/imath] m n f x. m (n f) x
SHIFTINC = [imath]\lambda[/imath] 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 = [imath]\lambda[/imath] n. FIRST (n SHIFTINC (PAIR 0 0))
SUB = [imath]\lambda[/imath] m n. (n PRED) m
ZERO? = [imath]\lambda[/imath] n. n (CONST FALSE) TRUE
NUMEQ = [imath]\lambda[/imath] 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 = ([imath]\lambda[/imath] f. ([imath]\lambda[/imath] x. f (x x)) ([imath]\lambda[/imath] x. f (x x)))

Now then, the list functions we all know and love

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

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

FOLDL = Y ([imath]\lambda[/imath] 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.

- Haskell first:

Code: Select all

sum list = foldl (+) 0 list


- How about Java?

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 = [imath]\lambda[/imath] 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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby TNorthover » Tue Oct 13, 2009 7:00 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby EduardoLeon » Tue Oct 13, 2009 10:08 pm UTC

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!

User avatar
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

Postby Briareos » Tue Oct 13, 2009 10:19 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby rabuf » Tue Oct 13, 2009 11:03 pm UTC

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 [imath]\lambda[/imath]-calculus, then this paper describes just such a machine:
http://dspace.mit.edu/handle/1721.1/5731

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

Re: The Turing Machine vs. Lambda Calculus

Postby EduardoLeon » Wed Oct 14, 2009 12:37 am UTC

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!

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

Re: The Turing Machine vs. Lambda Calculus

Postby stephentyrone » Wed Oct 14, 2009 12:54 am UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby qbg » Wed Oct 14, 2009 3:53 am UTC

Skip the lambda calculus and go straight to lisp.

User avatar
phillipsjk
Posts: 1213
Joined: Wed Nov 05, 2008 4:09 pm UTC
Location: Edmonton AB Canada
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby phillipsjk » Wed Oct 14, 2009 8:55 am UTC

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

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

Re: The Turing Machine vs. Lambda Calculus

Postby littlebuddy » Thu Oct 15, 2009 2:49 am UTC

lambda calculus

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

Re: The Turing Machine vs. Lambda Calculus

Postby 0xBADFEED » Thu Oct 15, 2009 2:31 pm UTC

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.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby Berengal » Thu Oct 15, 2009 2:43 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby 0xBADFEED » Thu Oct 15, 2009 2:53 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby stephentyrone » Thu Oct 15, 2009 3:37 pm UTC

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.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby Berengal » Thu Oct 15, 2009 4:09 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby LakatosIstvan » Mon Oct 19, 2009 6:32 pm UTC

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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby bieber » Wed Oct 21, 2009 9:05 pm UTC

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.

User avatar
hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: The Turing Machine vs. Lambda Calculus

Postby hotaru » Thu Oct 22, 2009 2:22 am UTC

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

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

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

Re: The Turing Machine vs. Lambda Calculus

Postby LakatosIstvan » Wed Nov 04, 2009 7:16 pm UTC

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

But thanks for the hint. A++ now became my favorite programming language :D
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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby MadRocketSci2 » Sat Feb 06, 2010 4:11 pm UTC

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

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: The Turing Machine vs. Lambda Calculus

Postby Meteorswarm » Sun Feb 07, 2010 3:18 am UTC

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


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!

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

Re: The Turing Machine vs. Lambda Calculus

Postby qbg » Sun Feb 07, 2010 3:44 am UTC

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

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

Re: The Turing Machine vs. Lambda Calculus

Postby afarnen » Thu Feb 11, 2010 3:02 pm UTC

My vote is with the Lambda Calculus.

First of all, I just find this to be pretty:[math](\lambda mnfx.mf(nfx))(\lambda fx.f(f(fx)))\lambda fx.(f(f(f(f(fx)))))[/math]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.

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

Re: The Turing Machine vs. Lambda Calculus

Postby ochuckles » Wed Apr 13, 2011 7:49 am UTC

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

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: The Turing Machine vs. Lambda Calculus

Postby Robert'); DROP TABLE *; » Wed Apr 13, 2011 5:52 pm UTC

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:[math](\lambda mnfx.mf(nfx))(\lambda fx.f(f(fx)))\lambda fx.(f(f(f(f(fx)))))[/math]

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.

User avatar
scarecrovv
It's pronounced 'double u'
Posts: 674
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: California

Re: The Turing Machine vs. Lambda Calculus

Postby scarecrovv » Wed Apr 13, 2011 6:48 pm UTC

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

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
[math]\lambda fx.(f(f(f(f(f(f(f(fx))))))))[/math]
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.

User avatar
Ptolom
Posts: 1559
Joined: Mon Mar 24, 2008 1:55 pm UTC
Location: The entropy pool
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby Ptolom » Wed Apr 13, 2011 10:17 pm UTC

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.

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: The Turing Machine vs. Lambda Calculus

Postby phlip » Thu Apr 14, 2011 5:29 am UTC

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 - [imath]\lambda m n f x. m f (n f x)[/imath] is addition, in that if you apply it to two Church numerals, it'll evaluate to the Church numeral representing their sum.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]


Return to “Religious Wars”

Who is online

Users browsing this forum: No registered users and 3 guests