Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New math book rescues landmark topology proof

quantamagazine.org

Post reply on HN
Print view View original

161–170 of 171 posts

Re: New math book rescues landmark topology proof

#161

Post by EamonnMR »

hansvm wrote: post #140
EamonnMR wrote: post #82

Earlier quoted context omitted.

I like to think of the halting problem as similar to the inability to predict the future. In order to predict the future you'd need a model of the whole universe, including the model. Once you think of it like that you realize that you can't beat halting in the classical universe.

The halting problem has that same style of thinking, but the universe doesn't necessarily play by such rules. For one, it's still an open question whether the universe could properly contain a model of itself (hence, needing a model of the universe plus the model isn't a guaranteed absurdity).

It is an absurdity though. You would need a material that can encode more information than it takes to physically represent it.

Re: New math book rescues landmark topology proof

#162

Post by unanswered »

srcreigh wrote: post #156
unanswered wrote: post #129

Earlier quoted context omitted.

Your "growing program" can (presumably, since we don't have a formal definition) be interpreted by a finite program; i.e. which can treat unlimited memory as instructions to execute. This means, in a very strict and formal sense, that it is not a more powerful model of computing. Therefore it is subject to the halting problem. But even if it were a more powerful model, it would still be subject to an analogous haltin…

Thanks, I read the proof [1] again a lot more carefully last night, and really failed to formalize my point. I tried to reason about it in different ways. Such as, for case 1, considering Z(Z) halts. I don't think it's unreasonable to say that H(Z,Z) could in fact return true. It could read the code for Z, determine that Z(Z) will loop since H(Z,Z) would return false, return true, and then Z(Z) would halt since H(Z,Z…

> Such as, for case 1, considering Z(Z) halts. I don't think it's unreasonable to say that H(Z,Z) could in fact return true. It could read the code for Z, determine that Z(Z) will loop since H(Z,Z) would return false, return true, and then Z(Z) would halt since H(Z,Z) returned true. No immediate contradiction.

This doesn't make sense. You said in the same case both that "Z(Z) halts" and "Z(Z) will loop" and then "Z(Z) would halt". So there is a contradiction here.

One assumption that you may not realize without the necessary background is that (a) "Z" is fixed in any particular case, we don't consider counterfactual "Z"; and similarly (b) "Z(Z)" must either always halt or always not halt, by the relevant definition of "program".

Re: New math book rescues landmark topology proof

#163

Post by qweqwweqwe-90i »

lou1306 wrote: post #146
qweqwweqwe-90i wrote: post #130

Earlier quoted context omitted.

If you could prove the ABC conjecture then Fermat's last theorem becomes much less than a page of proof :)

Speaking of ABC, some years ago HN was all abuzz with inter-universal Teichmuller theory, did that fizzle out or what?

https://www.math.columbia.edu/~woit/wordpress/?p=12220

Re: New math book rescues landmark topology proof

#164

Post by alisonkisk »

moomin wrote: post #139
lou1306 wrote: post #72

Earlier quoted context omitted.

Godel's theorem is actually not that complex. Sure, you may think of "Godel, Escher, Bach", but that book is stuffed with sooo much material that is only tangentially related to the theorem. Of course the consequences of that theorem are legion, and they do warrant many books worth of discussion. But the proof itself can fit in a long-ish blog post, I think. Fermat's last theorem, on the other hand...

For those interested: Assume a formal language that can model the natural numbers. Consider the set of all provable statements. This is countable because it’s a subset of the list of strings of a finite number of characters, which is countable. Consider the statement “Statement N is false”. This is both a valid statement and cannot appear in the list. Godel proved significantly more than that, but that’s the basic re…

It's "This cannot be proved.", where "this" is defined via the mathematical coding system he created.

The intuitive idea is very simple, but Godel's achievement in this theorem was in finding a way to rigorously define the word "this".

Re: New math book rescues landmark topology proof

#165

Post by alisonkisk »

zarzavat wrote: post #120
Denvercoder9 wrote: post #93

Earlier quoted context omitted.

I don't wanna know how much books the classification of finite complex groups is gonna take.

Not very much actually. Finite simple groups are kind of like prime numbers: any finite group can be broken down into simple subgroups similar to how any natural number can be broken down into a multiset of prime number factors. That's why the classification of finite simple groups is so important, it's essentially a classification of all finite groups. https://en.wikipedia.org/wiki/Composition_series#Uniqueness:...

Someone should make a modern recording of "Finite Simple Group of Order 2"

https://m.youtube.com/watch?v=UTby_e4-Rhg

Re: New math book rescues landmark topology proof

#166

Post by [deleted] »

roywiggins wrote: post #36
lostmsu wrote: post #31

Earlier quoted context omitted.

This sounds like a very dangerous attitude, considering that making any tiny mistake will cause you to be able to prove any statement. Of all people mathematicians should understand that.

Empirically, proofs with bugs get ironed out into proofs with less bugs, and the results almost always end up standing. Why mathematical proof seems to be as good as it is at avoiding proving false statements is a matter of contention, but practically speaking it works . There's very little incentive to computer check proofs because, as a practical matter, mathematics is not plagued with false "theorems." Computing,…

[deleted]

Re: New math book rescues landmark topology proof

#168

Post by srcreigh »

unanswered wrote: post #162
srcreigh wrote: post #156

Earlier quoted context omitted.

Thanks, I read the proof [1] again a lot more carefully last night, and really failed to formalize my point. I tried to reason about it in different ways. Such as, for case 1, considering Z(Z) halts. I don't think it's unreasonable to say that H(Z,Z) could in fact return true. It could read the code for Z, determine that Z(Z) will loop since H(Z,Z) would return false, return true, and then Z(Z) would halt since H(Z,Z…

> Such as, for case 1, considering Z(Z) halts. I don't think it's unreasonable to say that H(Z,Z) could in fact return true. It could read the code for Z, determine that Z(Z) will loop since H(Z,Z) would return false, return true, and then Z(Z) would halt since H(Z,Z) returned true. No immediate contradiction. This doesn't make sense. You said in the same case both that "Z(Z) halts" and "Z(Z) will loop" and then "Z(Z…

Thanks for the response. I was trying to illustrate why my argument doesn't work, but you did a much better job at that.

I may have found what I've been looking for in a related topic called Oracle machines for the halting problem. Part of its definition is that it can't solve problem for machines equivalent to itself, which, I believe, would exclude Z-type programs from the domain.

To put my plea into some formal jargon, "Just because the halting problem is undecidable doesn't mean oracles Turing machines for the halting problem don't exist." Kind of a simple and obvious point in hindsight, but I'm happy with it.

Re: New math book rescues landmark topology proof

#169

Post by [deleted] »

moomin wrote: post #139
lou1306 wrote: post #72

Earlier quoted context omitted.

Godel's theorem is actually not that complex. Sure, you may think of "Godel, Escher, Bach", but that book is stuffed with sooo much material that is only tangentially related to the theorem. Of course the consequences of that theorem are legion, and they do warrant many books worth of discussion. But the proof itself can fit in a long-ish blog post, I think. Fermat's last theorem, on the other hand...

For those interested: Assume a formal language that can model the natural numbers. Consider the set of all provable statements. This is countable because it’s a subset of the list of strings of a finite number of characters, which is countable. Consider the statement “Statement N is false”. This is both a valid statement and cannot appear in the list. Godel proved significantly more than that, but that’s the basic re…

[deleted]

Re: New math book rescues landmark topology proof

#170

Post by moomin »

harmoat wrote: post #141
moomin wrote: post #139

Earlier quoted context omitted.

For those interested: Assume a formal language that can model the natural numbers. Consider the set of all provable statements. This is countable because it’s a subset of the list of strings of a finite number of characters, which is countable. Consider the statement “Statement N is false”. This is both a valid statement and cannot appear in the list. Godel proved significantly more than that, but that’s the basic re…

Since these 3 results are so similar are they a subset of a more general concept?

Arguably the halting problem is just a subset of Godel where every theorem is "This does or does not halt". Someone's written a paper going the other way: https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf

The crucial trick is that you can plug in an entry as data to another "program/theorem". This is extremely interesting, because there are limited logics and limited computation models where Godel and the Halting Problem do not apply.

Not so sure about the diagonal argument.

Post reply on HN