= 27d567bc2d48d9f40e9ccc20ea370b15)
XiXiDu comments on Open Thread: March 2010 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (658)
I want to achieve an understanding of the basics without necessarily being able to be a productive programmer. I want to get a grasp of the underlying nature of computer science, not being able to mechanical write and parse code to solve certain problems. The big picture and underlying nature is what I'm looking for.
I agree that many people do not understand, they really only learnt how to mechanical use something. How much does the average person know about how one of our simplest tools work, the knife? What does it mean to cut something? What does the act of cutting accomplish? How does it work?
We all know how to use this particular tool. We think it is obvious, thus we do not contemplate it any further. But most of us have no idea what actually physically happens. We are ignorant of the underlying mechanisms for that we think we understand. We are quick to conclude that there is nothing more to learn here. But there is deep knowledge to be found in what might superficially appear to be simple and obvious.
Then you do not, in fact, need to learn to program. You need an actual CS text, covering finite automata, pushdown machines, Turing machines, etc. Learning to program will illustrate and fix these concepts more closely, and is a good general skill to have.
Recommendations on the above? Books, essays...
Sipser's Introduction to the Theory of Computation is a tiny little book with a lot crammed in. It's also quite expensive, and advanced enough to make most CS students hate it. I have to recommend it because I adore it, but why start there, when you can start right now for free on wikipedia? If you like it, look at the references, and think about buying a used or international copy of one book or another.
I echo the reverent tones of RobinZ and wnoise when it comes to The Art of Computer Programming. Those volumes are more broadly applicable, even more expensive, and even more intense. They make an amazing gift for that computer scientist in your life, but I wouldn't recommend them as a starting point.
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.
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.
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?
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.
I, unfortunately, am merely an engineer with a little BASIC and MATLAB experience, but if it is computer science you are interested in, rather than coding, count this as another vote for SICP. Kernighan and Ritchie is also spoken of in reverent tones (edit: but as a manual for C, not an introductory book - see below), as is The Art of Computer Programming by Knuth.
I have physically seen these books, but not studied any of them - I'm just communicating a secondhand impression of the conventional wisdom. Weight accordingly.
Kernighan and Ritchie is a fine book, with crystal clear writing. But I tend to think of it as "C for experienced programmers", not "learn programming through C".
TAoCP is "learn computer science", which I think is rather different than learning programming. Again, a fine book, but not quite on target initially.
I've only flipped through SICP, so I have little to say.
TAoCP and SICP are probably both computer science - I recommended those particularly as being computer science books, rather than elementary programming. I'll take your word on Kernighan and Ritchie, though - put that one off until you want to learn C, then.
Merely an engineer? I've failed to acquire a leaving certificate of the lowest kind of school we have here in Germany.
Thanks for the hint at Knuth, though I already came across his work yesterday. Kernighan and Ritchie are new to me. SICP is officially on my must-read list now.
A mechanical engineering degree is barely a qualification in the field of computer programming, and not at all in the field of computer science. What little knowledge I have I acquired primarily through having a very savvy father and secondarily through recreational computer programming in BASIC et al. The programming experience is less important than the education, I wager.
Yes, of course. Misinterpreted what you said.
Do you think that somebody in your field, in the future, will get around computer programming? While talking to neuroscientists I learnt that it is almost impossible to get what you want, in time, by explaining what you need to a programmer who has no degree in neuroscience while you yourself don't know anything about computer programming.
I'm not sure what you mean - as a mechanical engineer, 99+% percent of my work involves purely classical mechanics, no relativity or quantum physics, so the amount of programming most of us have to do is very little. Once a finite-element package exists, all you need is to learn how to use it.
I've just read the abstract on Wikipedia and I assumed that it might encompass what you do.
I thought computer modeling and simulations might be very important in the early stages. Shortly following field tests with miniature models. Even there you might have to program the tools that give shape to the ultimate parts. Though I guess if you work in a highly specialized area, that is not the case.
I couldn't build a computer, a web browser, a wireless router, an Internet, or a community blog from scratch, but I can still post a comment on LessWrong from my laptop. Mechanical engineers rarely need to program the tools, they just use ANSYS or SolidWorks or whatever.
Edit: Actually, the people who work in highly specialized areas are more likely to write their own tools - the general-interest areas have commercial software already for sale.
Bear in mind that I'm not terribly familiar with most modern programming languages, but it sounds to me like what you want to do is learn some form of Basic, where very little is handled for you by built-in abilities of the language. (There are languages that handle even less for you, but those really aren't for beginners.) I'd suggest also learning a bit of some more modern language as well, so that you can follow conversations about concepts that Basic doesn't cover.
'Follow conversations', indeed. That's what I mean. Being able to grasp concepts that involve 'symbolic computation' and information processing by means of formal language. I don't aim at actively taking part in productive programming. I don't want to become a poet, I want to be able to appreciate poetry, perceive its beauty.
Take English as an example. Only a few years ago I seriously started to learn English. Before I could merely chat while playing computer games LOL. Now I can read and understand essays by Eliezer Yudkowsky. Though I cannot write the like myself, English opened up this whole new world of lore for me.
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration." --Edsger W Dijkstra.
More modern versions aren't that bad, and it's not quite fair to tar them with the same brush, but I still wouldn't recommend learning any of them for their own sake. If there is a need (like modifying an existing codebase), then by all means do.
Dijkstra's quote is amusing, but out of date. The only modern version anyone uses is VB.NET, which isn't actually a bad language at all. On the other hand, it also lacks much of the "easy to pick up and experiment with" aspect that the old BASICs had; in that regard, something like Ruby or Python makes more sense for a beginner.