munchler 7 hours ago

This is an excellent talk by Scott Aaronson, although it's not something that can be digested as quickly as the typical HN post. The summary slide at the end is perhaps a good introduction to the scope of the topic:

* In math, we are finite beings trying to apprehend the infinite

* The Busy Beaver function actually quantifies that (!)

* Even the finite can exceed the scope of the cosmos. That's where we need physics and complexity theory

* Quantum computers look like they're already slightly expanding the scope of what mathematical statements we can know

* Can we know even more than that? Depends what the ultimate laws of physics are

  • jerf 6 hours ago

    "although it's not something that can be digested as quickly as the typical HN post"

    I really want a view of HN that is something like the upvotes divided by the number of comments (although, not necessarily linear). Those aren't necessarily the "best" by every metric, not saying this is the "best" view or anything, but it would be an interesting one.

    • nh23423fefe 41 minutes ago

      true. lots of comments is an indicator of low quality

    • gsf_emergency 5 hours ago

      Pretty sure dang (or other mods) has that view as a sidebar or something, maybe you can request that as an exclusive feature for top karmies. It would, as a bonus, already cover the edge cases you haven't thought about..

[removed] 7 hours ago
[deleted]
meroes 3 hours ago

Hoping to watch the video soon. What's still a mystery to me is how Turing Machines (infinite, abstract, non-physical) are so useful for us finite beings. Similar could be said for mathematical infinity.

calf 3 hours ago

What precisely is meant by simulating the laws of physics? There's a common understanding pitfall there, in that a lot of lay people quickly end up talking about "is the universe a computer" or "infinite Turing machines have nothing to do with the real world" sort of confusing arguments.

I liked how this talk addressed the topic yet have questions about this talk's overarching argument. It's kind of an argument yet more like a philosophical position about CS--I know at least one paper that critiques the philosophical commitments made in something like the Church Turing thesis, etc., that paper called Aaronson the strong American style perspective or something, I forget, at any rate the issue is how transparent these philosophical premises are which those of us from computer science may take for granted.

I also liked-disliked those one slide proofs. I couldn't follow them, I know they are right (and are great exercises for a student to go over offline) and that they are in service of showing that modern understanding can do the results in one slide and so forth, but yet there's an accepted style of academic presentation that kind of misleadingly "performs" in a way that is cognitively impossible for the audience to actually follow unless they already know it, technical talks are kind of a backwards lie in that way. There was a recent popular book by a French mathematician who said as much, that 99.9% of the time we can hardly understand mathematics talks and books and it's kind of an open secret how professionals deal with this phenomenon.

Edit: I took undergrad CS theory but never "got" the exposure/fascination with Busy Beaver, but after this talk it became clearer to me that the reason for the Busy Beaver function is that it's a meta-function, it is a function about Turing machines, which is how the BBF gets the special properties/results that it does. Which immediately reminds me of Chaitin's constant which also tries to encode/talk about the properties of Turing machines, e.g. Kolmogorov style complexity which was not explicitly mentioned in the talk.

  • tromp an hour ago

    > it is a function about Turing machines, which is how the BBF gets the special properties/results that it does.

    The properties of the Busy Beaver function carry over to any other computational model you could base it on. E.g. the lambda calculus based BBλ[1] shares most of its properties.

    > Which immediately reminds me of Chaitin's constant which also tries to encode/talk about the properties of Turing machines,

    Chaitin's work on Algorithmic Information Theory (aka Kolmogorov Complexity) was actually focussed on custom Lisp languages of his own design rather than Turing Machines. One could be confused though by some of his articles on LISP program-size complexity like [2] where he calls his LISP interpreter a UTM (Universal Turing Machine).

    [1] https://oeis.org/A33347

    [2] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...