Scott Aaronson - Why Philosophers Should Care About Computational Complexity

This follows nicely from Jenann Ismael's talk  Jenann Ismael - Laplace meets Godel: How Self reference Foils Prediction and also Edward Frenkel's talk Norman Wildberger and Dean Rubine Rewriting History and Edward Frenkel Offering Free Psychoanalysis.

32:33 There's an interesting observation about the Ackermann function and addition, multiplication and exponentiation here. See Philip Wadler's talk "Categories for the Working Hacker" in Philip Wadler - Propositions as Types.

46:11 Interesting thing about over-parametrised LLMs.

51:17 on MP*=RE see https://pirsa.org/20050011 and this mathoverflow discussion MIP*=RE theorem and its impact on logic and proof theory.

1:06:41 Interesting thing about non-linearity in quantum mechanics which I'd never heard of before. See Daniel S. Abrams and Seth Lloyd's Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems  (1998).

1:18:55 On quantum computing and AI hype. His blog is here: https://scottaaronson.blog/.

1:25:25 Question "How do we trust space and time?" His answer seems quite apposite to the whole AI/Quantum Computing thing as a whole!

1:31:57 On randomness and pseudo-randomness and the definition in terms of computational complexity: See Andrew Yao's 2000 Turing Award citation. 

The (60 page!) paper is here: Why Philosophers Should Care About Computational Complexity. 

Subscribe to  ekkolápto.

Here's a talk by Ewin Tang on Quantum Linear Algebra for Machine Learning:


The (2021) paper by  Shao and Montanaro is this one, I guess:  Faster quantum-inspired algorithms for solving linear systems.

Subscribe to UCLA IPAM.

Comments

Post a Comment

Popular posts from this blog

How Could One Unify CMU and MIT

Image
I mean, how to get the best of the two different philosophies of computation. One is based on typed programming languages and the other on engineering with diagrams . This is about practical computing and the cost and feasibility of software development in general. Here is the problem: We have a lot of algorithms which can all be described abstractly using some sort of pseudocode, or perhaps using some particular language (usually Python!). These algorithms are often well-studied and a lot is known about them in terms of their computational complexity in time and space. Substantive practical software systems invariably employ many such algorithms, often implemented in libraries with more or less well-specified APIs. But very few of these libraries are capable of interoperating because they are either packages written in some specific programming language like Java or Haskell, say, or they are written in C and used as object code, or they are written in an interpreted language like Sc...
Read more

Tensor Fields and Simplicial Complexes

Image
Listening to Freya Holmér last night I started to get glimmers of an idea I had long ago about how to represent vector spaces in computational processes using this recursive abstract type :  abstype 'a point = POINT   of {getx :  'a vector,       diff :  'a point -> 'a point,       move :  'a point -> 'a point,       scale : 'a -> 'a point,       proj :  'a point -> 'a} with    fun new i (op +) (op -) (op * ) dot =    let fun self x =  POINT       {getx = x,        move = fn (POINT pr) =>           (self (x + (#getx pr))),        diff = fn (POINT pr) =>          self (x - (#getx pr)),        scale = fn i =>          (self (x * i)),        proj = fn (POINT pr) =>     ...
Read more

HTML in Blog Posts

Just testing stuff: SVG You can click on the blue circle: MathML There is not much you can do with this. See Mathematical Markup Language 1.01 Specification   7.1.5 Mixing and Linking MathML and HTML . It's the big problem  of how you compose languages.   a x 2 + b x + c = 0 You can click on the discriminant: x = − b ± b 2 − 4 ⁢ a ⁢ c 2 ⁢ a 2D Canvas Sound  Beep! WebGPU Next level Parser expression grammar compiler:  https://peggyjs.org/online.html Devine Lu Linvega's unxtal assembler/debugger:  https://wiki.xxi...
Read more