Gödel Incompleteness for Startups (2013)

As far as I recall, this was written in the specific historical context almost a decade ago. Back then "Lean Startup" and "4 Steps to Epiphany" were all the rage in Silicon Valley. Shitty copy cats of YC were springing up left and right in the Valley and other locations. A number of people (with a lot of financial self-interest at stake) were pushing hard the narrative that creating new unicorn can be industrialized like a factory and they already figured out the magic formula - no risk, all reward - just sign here under the dotted line and give me your funds.

The essay publication was quite impactful in middle of that insanity. It uses Gödel analogy to demonstrate that no amount of formalization (that helps reduce human/team/org risks) will in any meaningful way reduce the systemic risk of a new startup. It placed Gödel formalism straight on the path of hustler/carpetbaggers who were trying to launch new funds and incubators at that time "well, go ahead and prove to your LPs you have Gödel-like formalism that detects great startups at an early stage and you do it better than YC".

Right now most of the essay conclusions are self-evident, "lean startup" is an insult, so it does seem like the author spending a lot of pages and energy on proving something plain obvious.

That wasn't that clear and that obvious many years ago when it was written.

Godel's incompleteness is not that complicated. The main insight Godel had was that proofs as well as provable statements can be encoded in numbers. This is obvious to everyone reading HN -- all computing works by encoding things into numbers. And it's easy to see how you'd encode proofs, proof rules etc. into numbers. (hint: as flattened ASTs!)

The thing is, Godel didn't live in an era of pervasive computing so he came up with a wonky encoding based on products of powers of primes. This makes the proof technically challenging, but the fundamental idea is not that complex. What he was able to eventually do was encode a recursive statement of the form "this statement is not provable" where the "this" is kind of like a pointer back to the full statement. The rest is straightforward.

The article strikes at the right general idea: that a startup that grows large quickly must have executed an idea that was not widely known (e.g. being exploited well, or in the natural adjacent competency of a current large company).

Peter Thiel's analogy of this is "what's true but few people agree with you on" and pg's version is "the best ideas look like jokes / bad on first glance". There's a popular venn diagram that's almost analogous to the one in the article: the best startups are at the intersection of true and not obvious.

This article maps "obvious good ideas" to "provable in a formal system", which makes the Godel analogy work, but the Godel analogy seems like a worse analogy.

Analogies are supposed to put a new concept (startup ideas) in terms of more accessible concept (Godel statements?). The analogy target (Godel statements) was so obtuse that the author needed to spend pages explaining it.

Also, the Godel analogy is misleading. The canonical Godel sentence is self referential and also refers to the formal logic system -- a good startup doesn't need to be self referential or refer to the formal system. Besides generating Godel's incompleteness theorem, I don't think Godel statements are "interesting", unlike the most recent successful startups. (In fact, what's interesting are simple yet difficult theorems that were totally provable within Peano arithmetic to begin with, like Fermat's Last Theorem.)

Very interesting article and I enjoyed reading it. Obviously, it is complete bullocks :-) If a startup would have to rely on finding interesting Gödel statements, there would be no successful startup. Even in the much cleaner world of mathematics, basically all interesting work is done within the realm of formally provable statements.

Also, the ultimate monopolist would not play by the formal rules of the game. He would make the rules so simple, that now he indeed can formally derive all truths and exploit these.

Actually I love reading an article about Gödel and I like perspectives on startups, I think this article would be best if it were not one but two (only focussing on one subject). I really think using Gödels theorem as a metapher is by far overstretching it.

Curious. I've noticed a number of people using Gödel's incompleteness theorem as a ridiculously stretched metaphor for some idea they're trying to get across. At this point it's gotten utterly cringey to me. It reeks of someone who only recently heard about it, got a conceptual understanding for what it's about, and now want to show off and force the comparison in the first conversation they have. Seems like a more obscure version of the meme that Heisenberg's uncertainty principle has become.

This one is the most egregious case I've seen though. It seems like it would be a waste of time to read, so I closed out fairly quickly. Have I misjudged the article?

"Most startup ideas are bad - Paul Graham empirically classified these as “good ideas that look like bad ideas initially”. From Gödel’s model we can draw even more precise distinction. These ideas look “bad” because they are unprovable ideas in composite formal system “everything we know so far”. Bad ideas that are actually bad are usually provably bad even in current system. "

I think this was a very long and drawn out way of saying that there are an infinite number of ideas, most of which will fail, but some will be successful. The successful ones typically aren't created at big companies because there's no way to truly know which ones are going to wind up being the extreme moneymakers, and at some point, the estblished systems of those big companies make them inherently selective in taking on new things.

You need a sea of risk takers and tinkerers (entrepreneurs and hobbyists) to bring the best ideas to life.

It would be really good to have some TLDR, abstract or summary.

Ever since Gödel proved his theorem, people have used it as a metaphor for all kinds of things, from new age mysticism to psychology, biology, quantum physics, AI etc.

It's a very worn metaphor and mostly used by people who don't actually understand the theorem precisely, just the imagined "gist", often with fundamental misunderstandings. A bit how people use Eistein's relativity theory to then derive moral relativism because "everything's relative".

This blog post may actually provide insight, but it's too long to see.

Given the prior that Gödel is often used just to borrow the prestige and aura of mathematics and to sell insight porn, I cannot justify reading it without seeing a summary.

I start to appreciate the rigid form of scientific articles more and more. People often say it's too rigid, too contorted, we'd be better if people just wrote blog posts in plain language, but then you get unstructured page after page, where you don't know where to look. With some training one can quickly assess the importance/relevance of scientific articles, exactly due to the rigid format. Here I have no idea where I can find the main idea. It is important to be effective in getting ideas across.

Okay I'll take a stab at the TL;DR: The author posits that great startup ideas are like Godel's unprovable, but true statements. These startup ideas cannot be valued using the experience one has with valuing existing successful companies. They tend to look like bad ideas in any valuation, but are in fact good ones. The search for such a startup ideas also cannot be formalised into a procedure (like say 4 Four steps to epiphany, or the Lean startup) Finally, author posits that the space of great startup ideas is infinite, even as the technology landscape grows ever more complex. There is no end to innovation. Godel's theorem in this article is used as a metaphor, and no more.

Applying Gödel's incompleteness theorem to search for unprovably, would-be, successful companies requires the searcher to develop axioms and rigorous math to know "This startup is an unprovable case and should be tested".

I really doubt axioms have even been assigned to this problem.

If anyone is looking for a relatively simpler explanation of GIT than Gödel's own work, I suggest the beautiful but sometimes inscrutable book "Gödel, Escher, Bach" by Douglas Hofstadter. Hofstadter draws lines between the math, art, and music of these three giants of human creation, and it's a lot easier to read than anything written directly by Gödel.

Roger Penrose's "The Emperor's New Mind" also has some good material on GIT.

I tried to write a Tl;Dr for this - i don't think I can.

It seems to be good start up ideas exist in the 'one step removed' phase space of all possible startups - not so far advanced that you need to teach Henry Ford about computers, but just one extra 'twist'.

This seems to be however leading to startups should iterate through 'Facebook but for [dogs,cats,fish,mobile phones]" which I am not sure wins.

But I loved the history of Godel etc.

for the author: "Weather" - "Whether"

I tried getting through this blog but it was just way to much effort to learn the actual idea.

Can anybody give me an TL;DR?

The hard part in the proof for Gödel's first incompleteness theorem is what would later become known as Carnap's diagonal lemma:

https://en.wikipedia.org/wiki/Diagonal_lemma#Proof

This proof consists of just 7 lines, but these 7 lines are considered to be fiendishly unreadable. The lemma itself says otherwise something very understandable and perfectly relatable:

logicSentence <-> prop(%logicSentence)

Meaning of the lemma: If prop(%s) is a predicate property of any logic sentence s, then there exists at least one true sentence for which this property is true and/or one false sentence for which it is false. The expression %logicSentence is the (numerical) description (encoded as a number) of the logicSentence. The remainder of Gödel's proof is just endless bureaucracy to establish completely precisely in/from what type of theory it occurs/can be derived.

If you leave out the bureaucracy, Gödel's first incompleteness theorem follows almost trivially from the lemma:

logicSentence <-> isNotProvable(%logicSentence)

Hence, according to the expression above, there exists at least one false sentence that is not isNotProvable (and is therefore provable) [a] or at least one true sentence that isNotProvable [b]. Hence, the theory in which this situation occurs is inconsistent [a] or incomplete [b].

Now, the bureaucracy in Gödel's full proof actually does matter, because his theorem holds for the Peano and Robinson formalizations of arithmetic theory but not for the Skolem and Presburger ones. The reasons for that can only be found in the bureaucracy of Gödel's proof.