Hacker News new | past | comments | ask | show | jobs | submit login
The Director’s Cut: On Gödel’s first incompleteness theorem (inference-review.com)
46 points by lordgrenville 8 months ago | hide | past | favorite | 26 comments



The logical formulae are outside my learning, at this point in my life, but I do understand the general gist of the theorems from prior exposure and discussion.

If this were my first exposure, the overly florid, 'artsy' presentation would have sent me packing before the end of the first section, thinking "Oh, great, now I'm going to have to unpack his prose before I can even follow the discussion".


...to have the privilege of walking home with Gödel

Albert Einstein, on why he still went in to work at Princeton.


my favorite Gödel, Einstein story is when he was prepped by Einstein for an US immigration hearing, and then told the judge he found some loopholes in the constitution. Was it his character shaping his work, or his work and surrounding shaping (making) him, and if so what shapes a man like Gödel (or Freud, Einstein, Popper, Russel, ...) many others of that time. It seems there was a huge density of brilliant people concentrated in Europe at the time. Hardly anyone who died within the past 30 years will be remembered as those from that generation I'm sure.

Now everyone is writing AI papers which all look identical. Sure academia has changed.

A Contradiction in the U.S. Constitution https://jeffreykegler.github.io/personal/morgenstern.html

Gödel’s Loophole https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2010183


The fact that we are overlooking our Einsteins and Gödels says more about us than about them. For a moment in history scientists were looked up to and mythologized. Today they're doing the same work, but they've been put in a different place in society.


Examples?


I don't think that there are fewer gifted/hard working people today than there were 80 years ago. It is simply that the problems that science deals with today are much more complex, because the low hanging fruits were all picked by the Einsteins.


People pre Einstein's time probably said that about the Newtons.

Has there ever been any lower hanging fruit than the fact 95% of our universe is unexplained, and the tiny bit that is is described by two mutually incompatible theories?


Low hanging fruit can be fairly precisely defined. Human brains have finite memory and finite processing power. Relative to that, every year, a new scientist has to learn more about what others have done before him, before he can create something new. So, it becomes harder and harder every year to make a super contribution.

What Einstein had to study before superseding Newton could probably be put into a 10-20K page book. What a scientist has to study before superseding quantum is probably closer to a 50-100K page book.


Yes, I understand the argument - but it doesn't alter the fact that those excuses can always be used, and probably always have been.

Quantum mechanics was more revolutionary than general relativity, but came almost immediately after and was simpler (after the conceptual leap) to study, which rather undermines the low-hanging fruit excuse.


I agree. You look at that extraordinary flowering of genius in the early 20th century in both science and the arts, and it's difficult to see the equivalents in the last few decades.


Oh god, just read Nagel and Newman instead!


This was awful to read.


ah, another generation bites down hard on Gödel, without even a citation of Hofstadter. Too pop-science? Too "overly florid, 'artsy' presentation"? Or just too good, too deep, too wide to make it worth revisiting this topic in a blog post measured in a few pages of printed text?


A bit too much inscrutable math here, but something every AI/ML researcher should know by heart.

Imagine today we make the perfect modeling machine for reality.

Now imagine that machine has to model not only reality yesterday, but today, now that we have the machine.

Additionally, it will have to model the fact that humans are going to change their behavior based on the fact that this machine is modeling reality...

[Machine Halts...]

aka, all of these problems below from seemingly different domains are actually isomorphic (aka the same problem in different shapes)

https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... https://en.wikipedia.org/wiki/Uncertainty_principle https://en.wikipedia.org/wiki/Lucas_critique https://en.wikipedia.org/wiki/Halting_problem


>A bit too much inscrutable math here, but something every AI/ML researcher should know by heart.

If it's inscrutable to you how do you know it's important enough for every AI/ML researcher to understand?


[flagged]


Posting like this will get you banned here. We've already had to ask you not to post flamebait and/or unsubstantive comments to HN. Would you mind reviewing https://news.ycombinator.com/newsguidelines.html and sticking to the spirit of this site? We'd be grateful.


Incompleteness is implied by the Halting Problem, but the latter is the deeper result, despite being easier to express. Or maybe because?


Turing’s halting problem and Gödel’s incompleteness theorems are closely related, but how do you make the link to Heisenberg?


Because op is just posting a laundry list of things they think are sophisticated to seem impressive.


Heisenberg (simplified) - you can know position exactly or you can know velocity exactly but you can’t know both.

Lucas critique - there are limits to formal understanding, because by observing, and modeling something, you end up changing it - especially in a system made up of sentient agents.

See the parallels to heisenberg?

There are limits? The best way to run afoul of them are to not acknowledge they exist!

*edit: iPhone autocorrect


"For all natural numbers, m = n if and only if S(m) = S(n)."

Hmm, er, ah, ... That's an odd way to put it.


The purpose of this is to make the successor function S an injection. That is, it assures us that all natural numbers are the successor to exactly one other natural number, except that zero is first and so it isn't the successor to anything (in the natural numbers). The number line you saw in primary school is fundamental to arithmetic.

Without this rule we might worry that perhaps there can be other numbers between five and six, or that if we all count up from one some of us might never reach a hundred because we inadvertently divert and get to six million early. These concerns seem intuitively nonsensical, but Peano doesn't want to rely on intuition, he wants to use logic.


But normally it would be written "For all natural numbers, S(m) = S(n) if and only if m = n."

"if and only if" is symmetric, but English isn't, really.


Lucky 10000: "If and only if" [0] is a particular phrase in English with a particular meaning. It is symmetric, so that your version has the same logical content as the original.

[0] https://en.wikipedia.org/wiki/If_and_only_if


The same logical content, yes, but...

Do you write the Fibonacci function as "n * (n-1) = fib(n)"?


I don't know why you think it's backwards.

It makes lots of sense to put "m=n" first. It's giving the definition of equality. "[term] is [definition]".




Applications are open for YC Winter 2021

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: