tag:blogger.com,1999:blog-3722233.post6748297921609096715..comments2022-12-07T07:34:35.444-06:00Comments on Computational Complexity: Mathematics is not commutative Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-5056271090278432802021-03-03T13:32:17.338-06:002021-03-03T13:32:17.338-06:00If Turing had come before Cantor, then modern math...If Turing had come before Cantor, then modern mathematics would not use a set theory like ZFC as its foundation. As in, imagine the 2 were reversed: Cantor comes up with the theory of computation in the late 1800s (perhaps inspired by machines like Babbage's) and it is Turing who later comes up with infinite sets, "Turing" normal forms, ordinals, etc. <br /><br />I contend that in that universe modern math would've adopted a very different foundation, one based around concepts of computability and complexity. Cantor's set theory was only adopted as the foundation of 'pure' math because it lacked any better competitor in the early 1900s, despite already growing awareness of the ambiguities and paradoxes it contains. In the alternate world Hilbert and co. would not only not have Cantor's set theory (Turing wouldn't invent it for another 10-20 years), but would arguably have a superior alternative right in front of them. <br /><br />Such a change would have profound implications for the last 100+ years of mathematics. Pure math would be far less comfortable with infinities and non=constructive (or overly abstract) constructs than it really is. Putting computation and algorithms at the center would've been a big boost to things like combinatorics and complexity theory itself, but also potentially forced things like real analysis and topology to either A) come after Turing or B) adopt a very different foundation. I think the upshot would be a universe where a lot more of "pure" math is something you can do on a physical computer, but a fair amount of OUR pure math either never exists or looks very different. zyezeknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72976783711952171242020-09-08T16:20:21.866-05:002020-09-08T16:20:21.866-05:00Here's another potential example of non-commut...Here's another potential example of non-commutativity that I just learned about. In a remarkable lecture, Brendan Guilfoyle speculates that if Simon Donaldson's work on smooth 4-manifolds had come out before Michael Freedman's paper on the 4-dimensional Poincare conjecture, then Freedman's paper in its current form would never have been accepted for publication, because its consequences would have seemed so absurd that referees would have demanded a much more detailed and careful argument. https://youtu.be/VZs1UG2Wtn8?t=2220Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12737691376390596112020-08-24T09:44:45.457-05:002020-08-24T09:44:45.457-05:00I have wondered if the mathematical community had ...I have wondered if the mathematical community had early on adopted dependent choice (DC) rather than the full-blown axiom of choice, and conjectured that "all sets of reals are Lebesgue measurable" (LM), would we now regard ZF + DC + LM (rather than ZFC) as the standard foundation of mathematics? See this answer by Andreas Blass on MathOverflow: https://mathoverflow.net/a/34863Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9119162994934745422020-08-19T08:28:38.677-05:002020-08-19T08:28:38.677-05:00@Lance: Good point. I had almost wanted to say tha...@Lance: Good point. I had almost wanted to say that had we just come up directly with the deterministic version (for Primes), we would not have all these probabilistic results hinging on 'randomness'. This didn't fly quite as well :)Enoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82121164078855544122020-08-17T22:21:26.716-05:002020-08-17T22:21:26.716-05:00AH- excellent point.
I wonder- is coding `M_e(0) d...AH- excellent point.<br />I wonder- is coding `M_e(0) does not halt' into an arithmetic<br />statement hard? So could we NOW give an easier proof of Godel?<br />I think so.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58705821289372835432020-08-17T14:34:52.788-05:002020-08-17T14:34:52.788-05:00I disagree somewhat that if it had been known firs...I disagree somewhat that if it had been known first that HALT is undecidable then Godel's theorem would have been easy. The proof you gave is implicitly using the fact that statements about Turing machines are equivalent to statements in the language of arithmetic. This may seem obvious now, but I think it was genuinely novel at the time and was considered a major part of Godel's breakthrough. It may seem more obvious to us now because working with computers has given us lots of practice translating statements between different languages (e.g. writing compilers and interpreters or even just various kinds of parsers).Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91721500115496954812020-08-17T10:28:20.463-05:002020-08-17T10:28:20.463-05:00Evidence for integer factorization is in P: https:...Evidence for integer factorization is in P: https://mathoverflow.net/questions/79366/Steve Huntsmannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81547661754834865152020-08-17T09:01:06.829-05:002020-08-17T09:01:06.829-05:00My favorite example is Primes in P. If it was prov...My favorite example is Primes in P. If it was proven in the 70's instead of the 2000's we wouldn't have had all those partial results (Primes in RP, co-RP, UP, and in P if the generalized Riemann Hypothesis held).Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.com