HNHacker News
TopNewBestAskShowJobs

ionfish

2,889 karma · joined February 27, 2008

submissionscomments
ionfish··on Facebook forces all users over to Facebook.com e-mail addresses
Explanations are not justifications.
ionfish··on Gödel and the limits of logic
If it's a biography you want, you'd be better off with John Dawson's one (he is, of course, the author of the article linked at the root).
ionfish··on Gödel and the limits of logic
Knowing computer science stuff like regular languages is really not required to understand the incompleteness theorems; grasping first order logic, a little arithmetic and some elementary recursion theory is sufficient.

I repeat my objection to the Goldstein book raised elsewhere in this discussion.

ionfish··on Gödel and the limits of logic
Do you have a decent understanding of first order logic? If not, sort that out first. Peter Smith has a good list of books to choose from:

http://www.logicmatters.net/2012/05/teach-yourself-logic-1-f...

Then get Smith's book An Introduction to Gödel's Theorems. It explains Gödel's results in great detail and doesn't assume too much background knowledge. A certain amount of perseverance will, of course, be required…

There's some supplementary material on his website: http://www.logicmatters.net/igt/

ionfish··on Gödel and the limits of logic
One of the features of first order logic is that the provability relation is recursively enumerable: given any recursive first order theory, there is a Turing machine that can list every theorem of that theory (although of course it will run forever).

Additionally, first order logic is complete: for every statement true in all models of a theory, there is a proof of the statement from the theory.

These two constraints cannot both be satisfied in a sound deductive system for second order logic. To see that this is so, consider that in second order logic we can prove Dedekind's categoricity theorem: there is only one model (up to isomorphism) of the second order Peano axioms (PA2). Let's assume that the provability relation for second order logic is recursively enumerable. We know from Gödel's incompleteness theorem that the set of first order sentences true of the natural numbers is not recursively enumerable. So take a sentence of the form "If PA2 then _" for some sentence _ which is in that set but not in the extension of the provability relation (this is a legitimate statement since the PA2 axioms are finite so we can just take their conjunction). This should be a logical truth of second order logic, but it's not provable (by the argument just given), so second order logic is incomplete: there are statements which are logical consequences yet are unprovable. So in other words, yes, the incompleteness theorem is very much at play in this limitation of second order logic.

For the technical details I very much recommend chapters 3 and 4 of Shapiro's book; it's not terribly expensive, and any decent university library should have a copy.

(A small footnote to my earlier post: Shapiro's book originally came out in 1991, not 2000—that's just the date of the paperback edition, and I'm unsure as to whether there are any substantial differences between the two.)

ionfish··on Gödel and the limits of logic
Right, but the point here is that we're not just talking about extensions of the system, we're talking about true but unprovable statements—that is, statements that are true in the standard model of arithmetic but not provable in PA (or whatever other arithmetic theory strikes your fancy). This is why Turing looked not at single formal theories but at a hierarchy of consistency extensions of the initial theory. In other words, the game changes from formal provability to informal provability, and from provability relative to a set of axioms to absolute provability. Turing showed (very roughly) that given a tree of consistency extensions (which branches only at limit stages) every Pi_1 sentence was decided at some point a with |a| = ω + 1. Feferman then proved in the 1960s that there is a path through the tree of ordinal notations that decides every Pi_2 sentence. These are completeness results, albeit for progressions of formal systems rather than individual systems. So certainly the puzzle can never be completed within a single formal system, but by restricting to sentences of limited complexity, there is an ordinal-time operation which decides each sentence (obviously there are numerous philosophical problems with this, although I'm afraid my expertise in this area is extremely limited so I can only give a sketch of the issues involved).
ionfish··on Gödel and the limits of logic
'Reducibility' in general is an informal notion, and as such there are many different technically precise ways of capturing aspects of it. Mutual interpretability and bi-interpretability are two of these, but they apply to formal systems with the same underlying logic (that is, the same semantics and proof theory). There are also many other notions of translation between different logics like Gödel–Gentzen negative translation between classical logic and intuitionistic logic. I'm not sure if there is a good introduction to all of these different ways of capturing reducibility, but you could try asking on math.stackexchange.com, there are usually helpful responses to reference requests there.

Second order logic does not have a complete proof theory, so your Turing machine will not be able to compute the consequences of a theory formulated in second order logic. This can be avoided by employing Henkin semantics, but then you're not working with full second order logic anymore. Stewart Shapiro's 2000 book, Foundations without Foundationalism: A Case for Second-Order Logic has the technical details should you be interested.

ionfish··on Gödel and the limits of logic
The Goldstein book is rubbish. Soloman Feferman destroys it in his LRB review.

http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unpro...

http://math.stanford.edu/~feferman/papers/lrb.pdf (full text)

"Those who are fascinated by Gödel's theorems—and the general idea of limits to what we can know—may still hunger for a more universal view of their possible significance. But they should not be satisfied with Goldstein's 'vast and messy' goulash, hers is not a recipe for true understanding."

ionfish··on Gödel and the limits of logic
The point must surely be that one can add the these true-but-unprovable statements to the original axioms without contradiction. They fit just fine: they're all elements of Th(N). It's a poor analogy because the natural way of thinking of a jigsaw puzzle is of a set of elements (pieces) that are consistent (every piece has a place), so if a piece doesn't fit then it's not consistent with the others. But this is false if the pieces are statements in the language of arithmetic that are true of the natural numbers.
ionfish··on Gödel and the limits of logic
"I think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent."

Eh? No it doesn't! If you add Con(PA) to the axioms of Peano arithmetic you obtain a stronger system. That system can't prove its own consistency, of course, but if you have a proof that the system PA + Con(PA) is inconsistent then you're probably in line for a Fields Medal.

Alan Turing worked on precisely this issue, developing ordinal logics in his PhD thesis (with Alonzo Church) to try to overcome incompleteness. Soloman Feferman, who in the 1960s proved a stronger result than Turing obtained, has written about this extensively. An accessible paper is this one:

http://math.stanford.edu/~feferman/papers/turingnotices.pdf

ionfish··on Gödel and the limits of logic
"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end."

I really don't understand this analogy. The first incompleteness theorem shows that there are statements true of the natural numbers which aren't provable from any sufficiently strong recursive theory. It's more like Th(N) (the set of statements true of the natural numbers) being a jigsaw puzzle from which many pieces will always be missing if you start with a recursive set of pieces and try to lay down only those pieces which a provable from your initial set. Nothing "won't fit": there aren't inconsistencies or incompatibilities at work here, but incompleteness.

ionfish··on Gödel and the limits of logic
Provability is relative to a formal system. Whether there are _absolutely undecidable_ statements is more controversial, and still an open question in the philosophy of mathematics. Gödel's disjunction is part of this literature: "Either … the human mind … infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems." Soloman Feferman has written about this, for instance in a 2006 Philosophia Mathematica paper.

http://math.stanford.edu/~feferman/papers/dichotomy.pdf

ionfish··on Yesod 1.0 - a robust, friendly, high performance web framework for Haskell
> Last time I looked at Snap, it seemed like variables captured from the url, got mixed into the same environment as key/value pairs from the QUERY_STRING and POST data.

This was fixed in the recent 0.8 release.

http://snapframework.com/blog/2012/03/16/snap-0.8-released

ionfish··on New fighter jet camouflage schemes
The rationale is closer to that behind dazzle camouflage, though—to confuse, rather than to conceal.
ionfish··on Show HN: my "My Latex resume" project
They do—yours looks unreadably compressed to me.
ionfish··on How I survived a plane crash
They did.

http://en.wikipedia.org/wiki/Wings_of_Hope

ionfish··on Raganwald's "How to Do What You Love" is free today
I paid $10, so you can consider me as having paid for you if it makes you feel better.
ionfish··on Stop reading this blog and learn something
Hindley and Seldin's Lambda-Calculus and Combinators: An Introduction is pretty solid.

http://www.cambridge.org/gb/knowledge/isbn/item1175709/?site...

ionfish··on Death to .DS_Store
They could have just made a static version with wget.
ionfish··on Superstitious users and the FreeBSD logo
> Don't let your fears and inhibitions turn you into a robot because some interview with Steve Jobs said not to put "powered by..." logos on stuff.

Steve Jobs appeared happy enough to have "Designed by Apple in California" inscribed on all Apple's products.

ionfish··on Even my grandmother got immutability
The position I'm attacking is the claim that it's just obvious that imperative programming is more intuitive, not that it is more intuitive. By exhibiting counterexamples to this supposedly obvious assertion, it's shown that it is not in fact obvious. Whether imperative or declarative programming is in fact more intuitive is, of course, not something to be settled by the anecdote give in the link.
ionfish··on Even my grandmother got immutability
Another nail in the coffin of the claim that imperative programming is more intuitive, persistently asserted without good evidence.

I submit that when people make claims of this sort, what they usually mean is actually "I'm used to doing it this way". Some actual studies of how new programmers learn would be valuable, and allow us to begin to evaluate claims like the above with at least a modicum of objectivity.

ionfish··on GitHub forking has one big flaw
"Would have". :)
ionfish··on Fermat's Unfinished Business
Another sense in which it's not over is the question of what the weakest system is which will prove FLT. Various people have suggested that it should be provable in PA. Colin McLarty has been working on this and has managed to reduce the requirements substantially. There's a preprint available of a paper to be published in the Bulletin of Symbolic Logic, although he may have progressed further since writing that.

http://www.cwru.edu/artsci/phil/Proving_FLT.pdf

ionfish··on The Power of Mathematics - John Conway [pdf]
I should probably point out that snobbery is very far from the actual attitude towards Tennenbaum, at least as far as logicians are concerned. For example, in 2006 there was a conference organised to celebrate his contribution to mathematical logic.

http://mamls.org/Tennenbaum

I recently attended a workshop devoted entirely to Tennenbaum's Theorem, his famous result that the only recursive model of PA is the standard model.

http://www.bbk.ac.uk/philosophy/our-research/ppp/tennenbaump...

ionfish··on Quantum theorem shakes foundations
Bohm's theory is a (non-local) hidden-variable interpretation of quantum mechanics with the same empirical predictions.

http://en.wikipedia.org/wiki/De_Broglie–Bohm_theory

ionfish··on WordPress To Jekyll And Back Again
http://www.idlewords.com/2009/09/using_wordpress_to_generate...
ionfish··on WordPress To Jekyll And Back Again
I can't tell from the site itself, since it's non-responsive (back to WordPress?), but from the comments here it appears the author objects to Jekyll regenerating the entire site every time.

If that's the case then I suggest he tries Hakyll, which has a dependency system built in so that it only rebuilds what it needs when files change.

http://jaspervdj.be/hakyll/

ionfish··on Paul Dirac: The unsung genius
I recommend Graham Farmelo's 2009 biography of Dirac, The Strangest Man.

http://www.guardian.co.uk/science/2009/apr/02/paul-dirac-str...

I once started a physics degree at Bristol, where Dirac was born and raised, and the department made a big show of 'their' man. The house he grew up in is a few minutes' walk from the department, and has a blue plaque indicating its status. It was some years before I discovered that Dirac had never been in the physics department at all, but in fact studied electrical engineering, before entering Cambridge, where he flourished as a physicist.

ionfish··on The Fans Are All Right
The really key underlying point here is that to make a web service that expands its audience beyond people would be likely to read Hacker News, one must consider the needs of other groups, especially those who will find the service useful without many changes, and reach out to those people. That it's the fandom community in this case is largely pertinent to Pinboard (and anyone else working on services which might benefit that community), but the wider point has relevance for everyone interested in more paying customers than just web nerds.
← PreviousPage 2 of 17Next →