The Turing Machine vs. Lambda Calculus
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 thoughtexperiments that bore some amazing fruits.
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 thoughtexperiments that bore some amazing fruits.
 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
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.
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)))

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
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.
 TNorthover
 Posts: 191
 Joined: Wed May 06, 2009 7:11 am UTC
 Location: Cambridge, UK
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.
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.
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.
 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
Lambda calculus, for actually being useful instead of just another turing tarpit.
You all probably know, but for thoroughness, here's the definition:
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, alphaconverting variables in case of any clashes. Substitution can always be performed and will always terminate, meaning a name will never appear on the righthandside 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 realworld 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 turingcomplete!
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 sumofalist in a couple of them and lambda calculus.
 Haskell first:
 How about Java?
 And lambda calculus?
SUM = [imath]\lambda[/imath] list. FOLDL PLUS ZERO list
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]
 x is a variable [imath]\rightarrow x \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, alphaconverting variables in case of any clashes. Substitution can always be performed and will always terminate, meaning a name will never appear on the righthandside 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 realworld 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 turingcomplete!
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 sumofalist 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.
 TNorthover
 Posts: 191
 Joined: Wed May 06, 2009 7:11 am UTC
 Location: Cambridge, UK
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.

 Posts: 111
 Joined: Wed Sep 30, 2009 2:26 am UTC
 Location: Lima, Perú
 Contact:
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 . ) ???
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!
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 ChurchTuring 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.
As to implementing a machine that "natively" deals with the lambda calculus: who cares? The ChurchTuring 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.
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 [imath]\lambda[/imath]calculus, then this paper describes just such a machine:
http://dspace.mit.edu/handle/1721.1/5731

 Posts: 111
 Joined: Wed Sep 30, 2009 2:26 am UTC
 Location: Lima, Perú
 Contact:
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!

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
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.
Re: The Turing Machine vs. Lambda Calculus
Skip the lambda calculus and go straight to lisp.
 phillipsjk
 Posts: 1213
 Joined: Wed Nov 05, 2008 4:09 pm UTC
 Location: Edmonton AB Canada
 Contact:
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?

 Posts: 43
 Joined: Thu Jun 04, 2009 5:40 pm UTC
Re: The Turing Machine vs. Lambda Calculus
lambda calculus
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.
 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
There's lots of research still going on in Lambda Calculus. Especially when it comes to types, LC is pretty much the goto 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...
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.
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 goto 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: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
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.
 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
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.

 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
I am pretty shocked a little that so little teaching resources concerning Lambda Calculus can be found on the Internet. Considering how mindbogglingly 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.
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 mindbogglingly 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 midway 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.
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
factorial = product . enumFromTo 1
isPrime n = factorial (n  1) `mod` n == n  1

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

 Posts: 69
 Joined: Sat Nov 21, 2009 5:31 pm UTC
Re: The Turing Machine vs. Lambda Calculus
Please compose your next post on a machine designed around Lambda Calculus. Thank you.
 Meteorswarm
 Posts: 979
 Joined: Sun Dec 27, 2009 12:28 am UTC
 Location: Ithaca, NY
Re: The Turing Machine vs. Lambda Calculus
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 machinelike computers, I don't think we ever will.
The same as the old Meteorswarm, now with fewer posts!
Re: The Turing Machine vs. Lambda Calculus
Turing machines are too boring; combinator calculus is much more interesting.
Re: The Turing Machine vs. Lambda Calculus
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 expressionthat'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.
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 expressionthat'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.
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?
 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
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 wellversed 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 bananashaped.
 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
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 wellversed in the lambda calculus explain what they does? It just looks like a mess to me.
I would hardly consider myself wellversed, 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.
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.
 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
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)⚠);}
Who is online
Users browsing this forum: No registered users and 3 guests