5 ms·
Elegant Lisp programs
- ramidarigaz 17y agoMy highschool math teacher spent two classes proving Goedel's incompleteness theorem to us, so this was really cool to see in programming form. Besides that though, I finally understand what LISP is all about. I've never worked with LISP before, and his explanation of LISP as manipulating sets blew my mind! Does anyone have any LISP tutorials they recommend? I did a quick search and came up with loads, but it's hard to tell if they're good right off the bat.
- phsr 17y agoMIT's Structure and Interpretation of Computer Programming is in LISP (Scheme to be exact) All the lectures and course materials are under Creative Commons. http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/CourseHome/index.htm http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...
- ramidarigaz 17y agoI can't believe I didn't think of OpenCourseWare. Thanks!
- gruseom 17y agoThere was a concerted effort by Lispers a year or two ago to get it so that Peter Seibel's book would come up first if you Google for "lisp tutorial". I believe it still does, and it's very good.
- zck 17y agoNot to pg-fanboy out too much, but I really like his ANSI Common Lisp: http://www.paulgraham.com/acl.html http://www.paulgraham.com/acl.html . It's not the newest thing on the market, but is quite good. Obviously, it's a book, so you'd have to buy or borrow it. Also, Arc has a tutorial online: http://ycombinator.com/arc/tut.txt http://ycombinator.com/arc/tut.txt
- benmathes 17y agoAfter a cursory glance this just looks like a restatement of Kolmogorov Complexity: "...the complexity is the length of the string's shortest description in some fixed universal description language." Traditionally a Turing Machine is used as the fixed universal description language. This paper just substituted scheme. http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity
- btilly 17y agoThey are tied, but it is being restated by one of the independent discoverers of the concept. Furthermore the theorem he is talking about is original to him. There is no "just" to it.
- benmathes 17y agoAh, my mistake. I didn't read the dates on the link, and assumed it was recently created.
- dasht 17y agoChaitin gave a not very formal but very nice and informative talk about omega at CMU in 200. Here is part 1 (the other parts should be easy to find). http://www.youtube.com/watch?v=HLPO-RTFU2o http://www.youtube.com/watch?v=HLPO-RTFU2o Someone above asked if this is just a restatement of Kolmogorov complexity. I'm not good enough at the technical details to say precisely yes or no but, basically: "yes" - they are regarded as simultaneous and independent discoveries. Kolmogorov complexity is also sometimes called Kolmogorov-Chaitin complexity. -t
- sb 17y agoThanks for the video, I will watch it. The interested readers might want to try the book "An Introduction to Kolmogorov Complexity and its Applications" by Li and Vitanyi (the 3rd edition came out recently). It is comparatively expensive, but Vitanyi's CWI site holds additional material.
- dasht 17y agoAlso, keep in mind that it's not just a result about programming / halting problem. It has implications for the foundations of mathematics. For example, if you formalize math such that you can measure the bit-length of theorems about numbers, you'll find that in the limit, to have a theory of all true theorems up to length N-bits, you'll need O(N) bits of axioms. (I'm probably not saying that in the best possible way: again, I'm no technician in these matters.)
- benmathes 17y agoOne of the conclusions you can draw from this that I love is that there are exponentially more complex things than there are simple things. The number of unique, 'elegant' programs short enough to store in 32 bits is 2^32, but the number of unique, 'elegant' programs you can store in 100 bits is 2^100.
- btilly 17y agoExplain those estimates, please. And do recall that not all programs are elegant.