Well, they’re computer sciencey, but they are definitely geared to approaching from the programming, even “Von Neumann machine” side, rather than Turing machines and automata. Which is a useful, reasonable way to go, but is (in some sense) considered less fundamental. I would still recommend them.
Well, they’re computer sciencey, but they are definitely geared to approaching from the programming, even “Von Neumann machine” side, rather than Turing machines and automata. Which is a useful, reasonable way to go, but is (in some sense) considered less fundamental. I would still recommend them.
Turing Machines? Heresy! The pure untyped λ-calculus is the One True Foundation of computing!
You seem to already know Lisp, so probably not. Read the table of contents. If you haven’t written an interpreter, then yes.
The point in this context is that when people teach computability theory from the point of view of Turing machines, they wave their hands and say “of course you can emulate a Turing machine as data on the tape of a universal Turing machine,” and there’s no point to fill in the details. But it’s easy to fill in all the details in λ-calculus, even a dialect like Scheme. And once you fill in the details in Scheme, you (a) prove the theorem and (b) get a useful program, which you can then modify to get interpreters for other languages, say, ML.
SICP is a programming book, not a theoretical book, but there’s a lot of overlap when it comes to interpreters. And you probably learn both better this way.
I almost put this history lesson in my previous comment: Church invented λ-calculus and proposed the Church-Turing thesis that it is the model of all that we might want to call computation, but no one believed him. Then Turing invented Turing machines, showed them equivalent to λ-calculus and everyone then believed the thesis. I’m not entirely sure why the difference. Because they’re more concrete? So λ-calculus may be less convincing than Turing machines, hence pedagogically worse. Maybe actually programming in Scheme makes it more concrete. And it’s easy to implement Turing machines in Scheme, so that should convince you that your computer is at least as powerful as theoretical computation ;-)
Um… I think it’s a worthwhile point, at this juncture, to observe that Turing machines are humanly comprehensible and lambda calculus is not.
EDIT: It’s interesting how many replies seem to understand lambda calculus better than they understand ordinary mortals. Take anyone who’s not a mathematician or a computer programmer. Try to explain Turing machines, using examples and diagrams. Then try to explain lambda calculus, using examples and diagrams. You will very rapidly discover what I mean.
Are you mad? The lambda calculus is incredibly simple, and it would take maybe a few days to implement a very minimal Lisp dialect on top of raw (pure, non-strict, untyped) lambda calculus, and maybe another week or so to get a language distinctly more usable than, say, Java.
Turing Machines are a nice model for discussing the theory of computation, but completely and ridiculously non-viable as an actual method of programming; it’d be like programming in Brainfuck. It was von Neumann’s insights leading to the stored-program architecture that made computing remotely sensible.
There’s plenty of ridiculously opaque models of computation (Post’s tag machine, Conway’s Life, exponential Diophantine equations...) but I can’t begin to imagine one that would be more comprehensible than untyped lambda calculus.
I’m pretty sure that Eliezer meant that Turing machines are better for giving novices a “model of computation”. That is, they will gain a better intuitive sense of what computers can and can’t do. Your students might not be able to implement much, but their intuitions about what can be done will be better after just a brief explanation. So, if your goal is to make them less crazy regarding the possibilities and limitations of computers, Turing machines will give you more bang for your buck.
A friend of mine has invented a “Game of Lambda” played with physical tokens which look like a bigger version of the hexes from wargames of old, with rules for function definition, variable binding and evaluation. He has a series of exercises requiring players to create functions of increasing complexity; plus one, factorial, and so on. Seems to work well.
You realize you’ve just called every computer scientist inhuman?
Turing machines are something one can easily imagine implementing in hardware. The typical encoding of some familiar concepts into lambda calculus takes a bit of a getting used to (natural numbers as functions which composes their argument (as a function) n times? If-then-else as function composition, where “true” is a function returning its first argument, and “false” is a function returning its second? These are decidedly odd). But lambda calculus is composable. You can take two definitions and merge them together nicely. Combining useful features from two Turing machines is considerably harder. The best route to usable programming there is the UTM + stored code, which you have to figure out how to encode sanely.
If-then-else as function composition, where “true” is a function returning its first argument, and “false” is a function returning its second? These are decidedly odd)
Of course, not so odd for anyone who uses Excel...
Booleans are easy; try to figure out how to implement subtraction on Church-encoded natural numbers. (i.e., 0 = λf.λz.z, 1 = λf.λz.(f z), 2 = λf.λz.(f (f z)), etc.)
And no looking it up, that’s cheating! Took me the better part of a day to figure it out, it’s a real mind-twister.
Maybe pure lambda calculus is not humanly comprehensible, but general recursion is as comprehensible as Turing machines, yet Gödel rejected it. My history should have started when Church promoted that.
I think that λ-calculus is about as difficult to work with as Turing machines. I think the reason that Turing gets his name in the Church-Turing thesis is that they had two completely different architectures that had the same computational power. When Church proposed that λ-calculus was universal, I think there was a reaction of doubt, and a general feeling that a better way could be found. When Turing came to the same conclusion from a completely different angle, that appeared to verify Church’s claim.
I can’t back up these claims as well as I’d like. I’m not sure that anyone can backtrace what occurred to see if the community actually felt that way or not; however, from reading papers of the time (and quite a bit thereafter—there was a long period before near-universal acceptance), that is my impression.
Actually, the history is straight-forward, if you accept Gödel as the final arbiter of mathematical taste. Which his contemporaries did.
ETA: well, it’s straight-forward if you both accept Gödel as the arbiter and believe his claims made after the fact. He claimed that Turing’s paper convinced him, but he also promoted it as the correct foundation. A lot of the history was probably not recorded, since all these people were together in Princeton.
It’s also worth noting that Curry’s combinatory logic predated Church’s λ-calculus by about a decade, and also constitutes a model of universal computation.
It’s really all the same thing in the end anyhow; general recursion (e.g., Curry’s Y combinator) is on some level equivalent to Gödel’s incompleteness and all the other obnoxious Hofstadter-esque self-referential nonsense.
I know the principles but have never taken the time to program something significant in the language. Partly because it just doesn’t have the libraries available to enable me to do anything I particularly need to do and partly because the syntax is awkward for me. If only the name ‘lisp’ wasn’t so apt as a metaphor for readability.
Are you telling me lambda calculus was invented before Turing machines and people still thought the Turing machine concept was worth making ubiquitous?
I’m betting it was hard for the first computer programmers to implement recursion and call stacks on early hardware. The Turing machine model isn’t as mathematically pure as lambda calculus, but it’s a lot closer to how real computers work.
Why not? People have a much easier time visualizing a physical machine working on a tape than visualizing something as abstract as lambda-calculus. Also, the Turing machine concept neatly demolishes the “well, that’s great in theory, but it could never be implemented in practice” objections that are so hard to push people past.
Because I am biased to my own preferences for thought. I find visualising the lambda-calculus simpler because Turing Machines rely on storing stupid amounts of information in memory because, you know, it’ll eventually do anything. It just doesn’t feel natural to use a kludgy technically complete machine as the very description of what we consider computationally complete.
Oh, I agree. I thought we were talking about why one concept became better-known than the other, given that this happened before there were actual programmers.
Elsewhere wnoise said that SICP and Knuth were computer science, but additional suggestions would be nice.
Well, they’re computer sciencey, but they are definitely geared to approaching from the programming, even “Von Neumann machine” side, rather than Turing machines and automata. Which is a useful, reasonable way to go, but is (in some sense) considered less fundamental. I would still recommend them.
For my undergraduate work, I used two books. The first is Jan L. A. van de Snepscheut’s What Computing Is All About. It is, unfortunately, out-of-print.
The second was Elements of the Theory of Computation by Harry Lewis and Christos H. Papadimitriou.
Turing Machines? Heresy! The pure untyped λ-calculus is the One True Foundation of computing!
You probably should have spelled out that SICP is on the λ-calculus side.
Gah. Do I need to add this to my reading list?
You seem to already know Lisp, so probably not. Read the table of contents. If you haven’t written an interpreter, then yes.
The point in this context is that when people teach computability theory from the point of view of Turing machines, they wave their hands and say “of course you can emulate a Turing machine as data on the tape of a universal Turing machine,” and there’s no point to fill in the details. But it’s easy to fill in all the details in λ-calculus, even a dialect like Scheme. And once you fill in the details in Scheme, you (a) prove the theorem and (b) get a useful program, which you can then modify to get interpreters for other languages, say, ML.
SICP is a programming book, not a theoretical book, but there’s a lot of overlap when it comes to interpreters. And you probably learn both better this way.
I almost put this history lesson in my previous comment:
Church invented λ-calculus and proposed the Church-Turing thesis that it is the model of all that we might want to call computation, but no one believed him. Then Turing invented Turing machines, showed them equivalent to λ-calculus and everyone then believed the thesis. I’m not entirely sure why the difference. Because they’re more concrete? So λ-calculus may be less convincing than Turing machines, hence pedagogically worse. Maybe actually programming in Scheme makes it more concrete. And it’s easy to implement Turing machines in Scheme, so that should convince you that your computer is at least as powerful as theoretical computation ;-)
Um… I think it’s a worthwhile point, at this juncture, to observe that Turing machines are humanly comprehensible and lambda calculus is not.
EDIT: It’s interesting how many replies seem to understand lambda calculus better than they understand ordinary mortals. Take anyone who’s not a mathematician or a computer programmer. Try to explain Turing machines, using examples and diagrams. Then try to explain lambda calculus, using examples and diagrams. You will very rapidly discover what I mean.
Are you mad? The lambda calculus is incredibly simple, and it would take maybe a few days to implement a very minimal Lisp dialect on top of raw (pure, non-strict, untyped) lambda calculus, and maybe another week or so to get a language distinctly more usable than, say, Java.
Turing Machines are a nice model for discussing the theory of computation, but completely and ridiculously non-viable as an actual method of programming; it’d be like programming in Brainfuck. It was von Neumann’s insights leading to the stored-program architecture that made computing remotely sensible.
There’s plenty of ridiculously opaque models of computation (Post’s tag machine, Conway’s Life, exponential Diophantine equations...) but I can’t begin to imagine one that would be more comprehensible than untyped lambda calculus.
I’m pretty sure that Eliezer meant that Turing machines are better for giving novices a “model of computation”. That is, they will gain a better intuitive sense of what computers can and can’t do. Your students might not be able to implement much, but their intuitions about what can be done will be better after just a brief explanation. So, if your goal is to make them less crazy regarding the possibilities and limitations of computers, Turing machines will give you more bang for your buck.
A friend of mine has invented a “Game of Lambda” played with physical tokens which look like a bigger version of the hexes from wargames of old, with rules for function definition, variable binding and evaluation. He has a series of exercises requiring players to create functions of increasing complexity; plus one, factorial, and so on. Seems to work well.
Alligator Eggs is another variation on the same theme.
You realize you’ve just called every computer scientist inhuman?
Turing machines are something one can easily imagine implementing in hardware. The typical encoding of some familiar concepts into lambda calculus takes a bit of a getting used to (natural numbers as functions which composes their argument (as a function) n times? If-then-else as function composition, where “true” is a function returning its first argument, and “false” is a function returning its second? These are decidedly odd). But lambda calculus is composable. You can take two definitions and merge them together nicely. Combining useful features from two Turing machines is considerably harder. The best route to usable programming there is the UTM + stored code, which you have to figure out how to encode sanely.
Just accept the compliment. ;)
Of course, not so odd for anyone who uses Excel...
Booleans are easy; try to figure out how to implement subtraction on Church-encoded natural numbers. (i.e., 0 = λf.λz.z, 1 = λf.λz.(f z), 2 = λf.λz.(f (f z)), etc.)
And no looking it up, that’s cheating! Took me the better part of a day to figure it out, it’s a real mind-twister.
It’s much of a muchness; in pure form, both are incomprehensible for nontrivial programs. Practical programming languages have aspects of both.
Maybe pure lambda calculus is not humanly comprehensible, but general recursion is as comprehensible as Turing machines, yet Gödel rejected it. My history should have started when Church promoted that.
I think that λ-calculus is about as difficult to work with as Turing machines. I think the reason that Turing gets his name in the Church-Turing thesis is that they had two completely different architectures that had the same computational power. When Church proposed that λ-calculus was universal, I think there was a reaction of doubt, and a general feeling that a better way could be found. When Turing came to the same conclusion from a completely different angle, that appeared to verify Church’s claim.
I can’t back up these claims as well as I’d like. I’m not sure that anyone can backtrace what occurred to see if the community actually felt that way or not; however, from reading papers of the time (and quite a bit thereafter—there was a long period before near-universal acceptance), that is my impression.
Actually, the history is straight-forward, if you accept Gödel as the final arbiter of mathematical taste. Which his contemporaries did.
ETA: well, it’s straight-forward if you both accept Gödel as the arbiter and believe his claims made after the fact. He claimed that Turing’s paper convinced him, but he also promoted it as the correct foundation. A lot of the history was probably not recorded, since all these people were together in Princeton.
EDIT2: so maybe that is what you said originally.
It’s also worth noting that Curry’s combinatory logic predated Church’s λ-calculus by about a decade, and also constitutes a model of universal computation.
It’s really all the same thing in the end anyhow; general recursion (e.g., Curry’s Y combinator) is on some level equivalent to Gödel’s incompleteness and all the other obnoxious Hofstadter-esque self-referential nonsense.
I know the principles but have never taken the time to program something significant in the language. Partly because it just doesn’t have the libraries available to enable me to do anything I particularly need to do and partly because the syntax is awkward for me. If only the name ‘lisp’ wasn’t so apt as a metaphor for readability.
Are you telling me lambda calculus was invented before Turing machines and people still thought the Turing machine concept was worth making ubiquitous?
Wikipedia says lambda calculus was published in 1936 and the Turing machine was published in 1937.
I’m betting it was hard for the first computer programmers to implement recursion and call stacks on early hardware. The Turing machine model isn’t as mathematically pure as lambda calculus, but it’s a lot closer to how real computers work.
I think the link you want is to the history of the Church-Turing thesis.
The history in the paper linked from this blog post may also be enlightening!
Why not? People have a much easier time visualizing a physical machine working on a tape than visualizing something as abstract as lambda-calculus. Also, the Turing machine concept neatly demolishes the “well, that’s great in theory, but it could never be implemented in practice” objections that are so hard to push people past.
Because I am biased to my own preferences for thought. I find visualising the lambda-calculus simpler because Turing Machines rely on storing stupid amounts of information in memory because, you know, it’ll eventually do anything. It just doesn’t feel natural to use a kludgy technically complete machine as the very description of what we consider computationally complete.
Oh, I agree. I thought we were talking about why one concept became better-known than the other, given that this happened before there were actual programmers.
Any opinion on the 2nd edition of Elements?
Nope. I used the first edition. I wouldn’t call it a “classic”, but it was readable and covered the basics.