Best book about Goedel’s theorem

Ever heard people misquoting Goedel’s theorem? Or, more disquietingly subtly, not known whether the quote was appropriate or not? Ever wondered about why (first order) predicate logic is complete, PA/ZFC are incomplete, but both PA and ZFC are first order logics that use predicate connectives? I did, and this weekend I found the most wonderful book about these issues: Torkel Franzen, Goedel’s Theorem: an Incomplete Guide to its Use and Abuse. A small note by Franzen, which might serve as an extended abstract to his book, is available here:

http://www.ams.org/notices/200604/fea-franzen.pdf

A comment from Oct. 12th

“Je ne vais pas en amphi prcq je ne comprends rien et que j’arrive quand meme a faire les TD”

Uhm. So. Well, the purpose of the TD is really to teach you Java. If you can code the practical exercises in the TD it probably means you can program in Java at a reasonable level. It doesn’t mean that your programs will be efficient though. The simple ones will (because of common sense), but some less simple ones may be much slower than is actually possible (and perhaps buggier, too). If your aim is to pass the exam and never ever program on a computer again, then doing the TDs and nothing else is probably an acceptable way to optimize your time (not from my point of view, but I can see that it could be so from your point of view). If you plan to ever code a computer again in the future, going to TDs and doing well is only half of the story, and you’re doing yourself a disservice by neglecting to turn up.

Why Java?

I read a comment about the TD after the sixth lecture (stacks and recursion):

Juste une question qui n’a pas de relation avec la TD dernière: Pourquoi on programme forcément avec Java? Pourquoi on ne programme pas avec C++ et C# qui sont à mon humble opinion mieux. Par exemple, en Java il n’ y a même pas de pointeur.

I totally agree with you. Myself, I’m a C++ coder. I’ve actually had to learn Java to teach INF421, and I’m less than impressed. Yes, it takes out some of the difficulties (pointers can be harmful), but even from a didactical point of view, it prevents you from actually seeing what’s inside the real (rather than virtual) machine. When I teach my C++ course (INF585), I always define what parts of the language actually mean (e.g., a program variable) by actually showing how memory changes when language instructions are executed. I use the symbol table (the map between symbols in the program and the memory storing their values) as a very real semantic map that can be shown to the students through a debugger. All of this is barred to me when I teach Java. The net result is that I can’t show the real link between the abstraction represented by the program and what actually physically happens inside the machine. This, I think, is detrimental to teaching computer programming.

So, you might wonder, well: you’re the professor, just switch! No, dear students: I can’t. Our department is organized in such a way that courses in first and second year must be coordinated. The Java choice was made long before I came to Polytechnique, and I believe it would almost take a revolution to change it. Since I’m 100% sure that revolutions are almost never beneficial for any entire population, I believe I’m not entitled to impose it upon you.

So, although I agree with you, I’m sorry but I shan’t be able to comply. If you really want to make a difference, put this request (Java -> C++) in a petition, sign it (the more signatures you collect, the better), and send it to me. I’ll forward it to the comité d’enseignement of our department. This might just spawn enough reforms to gradually get from Java to C++ without hurting anyone.

No comment?

I only had 5 comments for my last lecture, two of which simply notified an absence and one was happy about the slides. This left two minor criticisms, one saying I hadn’t detailed the notion of “trie” (very true), and the other lamented some boredom because he/she had already seen the concepts I taught in INF311/INF321 (good for you). 

In short, I think these 5 comments reduce to zero. I’m going to be positive about this and think that an absence of criticisms means “everything’s OK”. 

Let me just remind you that next friday afternoon you have the “pale machine” (a practical programming test: you will receive an exercise such as those you have during TD, and will have to solve it by yourselves; the “pale” will be marked). 

Answers to comments on fourth lecture

– “Euh… culturellement interessant, mais… il faudrait peut-etre plus de programmes Java et non des idees de programme…“. I tried, honestly. Last year I coded live and commented my code as it grew. Not a good idea. You should all have computers in front of you, test it as I go along, and then it would be a TD. But you already do TDs in the afternoon. Believe me, the role of a lecture is to give ideas; the role of a TD is to give practical insight (in the case of computer science, programs).

– “Pour bien comprendre l’informatique, il faut voir la vie à l’envers (comme les arbres)“. How I agree with you. I have been studying mathematics and computing for so long, that now I have to see life upside down to understand it. People, for example, don’t seem to react deterministically to external stimuli. You tell them something and they like it, so you tell them again, and again, and again, and suddenly they find it boring. I can’t make heads or tails of it. If they were like deterministic Turing machines, they should like it a countably infinite amount of times! How much simpler life would be!

– “J’ai trouvé ce cours un peu complexe, quand on a perdu le fil du raisonnement il est difficile de rattraper et de suivre la suite du cours.“. It happens to me too. I listen to other people’s lectures (at conferences, for example, or when I was a student), I get distracted for just a few seconds, and there’s no way to understand anything anymore. I totally get you. But this is why I would react really nicely if you stopped me and asked me to repeat. I know it’s difficult to raise your hand and speak publically in this huge, scary amphitheatre (it’s intimidating to me too sometimes), but that’s the only way for you to get back on the logical track of the reasoning. There’s not much I can do about it otherwise. Computer science (and mathematics) consists of many interconnected statements. There’s just no way to skip one and hope to understand the next.

– “Interessant pour les algorithmes presentes. Les demos ne sont pas toujours utiles.” Jeez! And I spend so much time latexing these bleedin’ demos! If you don’t want them, I’d gladly give them up. But I suspect they might be useful to some people at least. If a majority writes to me to suspend the demos, I will.

Thank you to all those who tell me the course is nice (in varying degrees of enthusiasm).

Answer to comments on third lecture

– “Il est impossible de suivre sur le poly, car le professeur traite de parties totalement dissociees dans le livre”. Exactly. There is more than one logical way to learn the notions I’m teaching; I’m presenting one in the lectures, and another in the lecture notes – and there’s several more. This is again my attempt to arouse your scientific curiosity and stimulate your intelligence. By contrast, you’ll certainly have noticed that I’m almost always using the same terminology, so you can simply look terms up in the extensive index of the lecture notes, and find the correct page. I never thought I’d have to teach a university student how to use an index in a book: is this a Google effect?

– “trop de notation”. I totally agree with you here. When one starts studying graph theory, one has to digest a lot of notation before even considering interesting results. On behalf of this beautiful mathematical theory, I present you my apologies. There’s nothing much to do but studying hard until all the definitions are fresh in memory!

– A few students lament the complication of the graph theory lecture. Again, I invite you to get in touch with me by email and write your questions, even though very vague. Lamenting without doing anything about it is simply useless. Lament on, if it makes you feel better, but this won’t solve your troubles. 

Answer to comments on second lecture

Some more answers to selected comments.

– “beaucoup trop abstrait, incomprehensible”, feel free to contact me to arrange a catch-up session.

– “il manquait dans le poly le BFS”: it is actually there, did you try looking on the table of contents or in the index? 

– “difficile de faire le lien avec le poly immediatement”: YES! I’m successful in my attempt to try and make you establish links yourselves!

 

Answer to comments on first lecture

Dear students,

thank you for your 30 comments on the first lecture of the INF421 course. Many of you said the course was a little slow because it was a recap of notions you already knew. Sorry about that, but many of the 250 enrolled students do not necessarily come from the same “école preparatoire” specialties, so I have to keep the course at a level I believe to be good for the majority. When I receive more than 125 comments that the course is slow, I’ll pick up the pace.

One comment was about the discrepancy between lectures and TDs. I wrote on the course website, on this blog, on the slides, and I said orally, that disconnections are good for students, because they force them to create links where they are missing. “Intelligence” comes from “establishing links” (in latin), so a good quantity of unclear or missing links is essential to a good course. Accordingly, I shall see any comment about discrepancies between lectures and TDs as a sign that I’m attaining my “intelligence development” goals.

One comment was about the order of the notions on the slides being different from the order on the polycopié. The implication seemed to be that this is a “bad thing” that should be improved. Well, first of all, with a table of contents and an analytical index in the polycopié, I don’t think this is troublesome at all. My second point goes deeper: during my career, I taught university courses in the UK (Imperial College), Italy (Politecnico di Milano), and France (Ecole Polytechnique). Drawing a comparison between the educational systems, it appears clear that students at X possess a lot of notional knowledge, but sometimes lack independence. For example, they often expect their teachers to provide them with minute details about how to learn or study, such as what should be learned first, at what level of depth, and so on. I think this is bad. I think students at university should develop their own methods of learning, which will be useful to them in the rest of their professional lives. By presenting notions in slightly different ways on different supports, I am hoping to help making steps in what I believe to be the correct direction.

Next lecture: queues, Breadth-first search, and hashing.

Back to class!

Welcome back to class! The INF421 course starts its 2012/2013 edition on Friday, 31 August 2012. Here’s the official website. News for this year: I wrote some lecture notes. My original idea, when I accepted to do this course, we to refer to some (excellent) existing book, such as Mehlhorn and Sanders’ Algorithms and Data Structures. But it appears X students are miffed about buying a book (or even downloading it and printing it, since the book can legally be downloaded and printed for free), and want their teachers to write them the infamous polycopié. So, this I did. Not that I’m particularly proud of the result; my research and knowledge lie in a neighbouring field (Mathematical Programming). I still think Mehlhorn and Sanders’ book is better. The style of my polycopié is a mixture of formal and informal. I used an informal style whenever I felt that the material should be known as background but not necessarily mastered in depth. I used a formal style whenever I wanted the material to be properly known and studied. Every reader must bear in mind that this polycopié is not a book, but rather some lecture notes, and, as such, is not to be considered complete without coming to the lecture and practicals of INF421.

Some information on this year’s course.

1. The examination consists of a practical session and a written exam. We have yet to decide when the practical session will be. The exam is a contrôle classant, and is conceived, run and marked officially by a team of teachers that do not take part in the course. The mark of the practical session counts less than the mark of the written exam.
2. Because this course is oversubscribed, we won’t have much free space in the salles informatiques, so no change request will be considered. Don’t even ask.
3. This course aims to give you some knowledge of computer science (both theoretical and practical), but also to develop your intelligence. The lectures are not meant to help you do better in the TD: it is your business to find out just how the lectures will actually help you do better in the TD, and vice-versa (how the TD will provide a working example to the knowledge taught in the lectures). In other words, the link between lectures and TD is not always crystal clear, and this is precisely what I consider to be didactically valid: “intelligence” comes from the latin verb interligo, which literally means “to establish links”. Don’t go telling me there’s a disconnection between lectures and TD: I know this. And it provides didactical value to the course.

Pudding al cioccolato

Lo scorso dicembre mia moglie preparò un pudding al cioccolato che era un po’ come il libro di sabbia di Borges: tra una fetta e l’altra c’è sempre una terza fetta, non si arriva mai all’unità fettuale minima. Dal punto di vista matematico, le fette sono dense nel cilindro ciocco-latteo che le contiene, e dal punto di vista fisico il dolce ha densità infinita. Ma la misura è assai limitata: quando l’ho visto uscire (dalla pentola – non dal forno – ulp) mi sono detto: me lo sbafo tutto in un boccone.

Poi purtroppo mi hanno buttato fuori casa prima che potessi dar fondo alle fauci, in modo da poter scattare delle foto (non commestibili e quindi inutili). Al mio rientro, ne era stato mangiato un quarto, e gli astanti si trovavano in stato di coma cacao-favico… dicevano che erano pieni di cioccolato fino al gargarozzo. Ho pensato: “puah!, che mammalucchi”… E ho preso una fettonzola, che corrispondeva a un millesimo delle mie voglie cacaiche: dopo, con mia massima sorpresa, mi son detto, beh, sì, mi ci sta forse un’altra fetta. Ne ho preso un’altra (più fine), dopodiché in effetti ho cominciato a capire che avevo davanti a me un miracolo di sinergie molecolari.

Il secondo e il terzo giorno abbiamo intaccato appena un ulteriore terzo del microcilindro accioccolattato. Le fette si facevano sempre più fini, ci riempivano come non mai, ci soddisfacevano al massimo, ci fibrillavano di ciocchendorfine, eppure un bel terzo abbondante (non sono forte in aritmetica) restava sempre lì, a ridacchiare di noi babbei.

Alla fine quello che restava è stato regalato. Stamattina mi manca la dose, dovrò ripiegare sui miei cereali al cioccolato, che hanno la proprietà inversa: finiscono subito. Prevedo che il terzo restante verrà azzannato dalle fauci dei nuovi proprietari, che ne intaccheranno circa la metà, e poi lo regaleranno a loro volta, e così via in una ridda zenonica in cui il coltello non raggiungerà mai la fine del pudding.

E questo è uno dei motivi per cui i pudding inglesi vengono deplorati dalla maggior parte di quei bizzarri isolani: se fosse stato non al ciocciolato fondente, bensì al sapore di mattonella e uvette di plastica, come sono quelli inglesi, l’avremmo solo potuto usare da mettere al collo di un manichino pseudo-voodoo per annegarlo, quasi come in quella storia d’orrore di Guy de Maupassant.

Uso consigliato: soluzione del problema della fame nel mondo.

Uso alternativo: creazione di un buco nero portatile ad usum studiorum per i fisici delle alte energie.