Skip to content
Back to the collection

From Philosophy to Program Size

G. J. Chaitin

2003 · arXiv

Read the paper
HN score
0
Mentions
3
Readers
3
Months
3
What’s in a score?

From the abstract

Most work on computational complexity is concerned with time. However this course will try to show that program-size complexity, which measures algorithmic information, is of much greater philosophical significance. I'll discuss how one can use this complexity measure to study what can and cannot be achieved by formal axiomatic mathematical theories. In particular, I'll show (a) that there are natural information-theoretic constraints on formal axiomatic theories, and that program-size complexity provides an alternative path to incompleteness from the one originally used by Kurt Godel. Furthermore, I'll show (b) that in pure mathematics there are mathematical facts that are true for no reason, that are true by accident. These have to do with determining the successive binary digits of the precise numerical value of the halting probability Omega for a "self-delimiting" universal Turing machine. I believe that these meta-theorems (a,b) showing (a) that the complexity of axiomatic theories can be characterized information-theoretically and (b) that God plays dice in pure mathematics, both strongly suggest a quasi-empirical view of mathematics. I.e., math is different from physics, but perhaps not as different as people usually think. I'll also discuss the convergence of theoretical computer science with theoretical physics, Leibniz's ideas on complexity, Stephen Wolfram's book A New Kind of Science, and how to attempt to use information theory to define what a living being is.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

3 selected excerpts · 3 total mentions

ttctciyf
Neutral mention · rule
I've long admired Chaitin for his original thinking and especially his ability to clearly convey his ideas about foundations, complexity and information in concise and digestible short proofs. I'm a little surprised, however, to see him here proselytizing for a particular side in the constructivism debate. I associate him more with what he has described as a "quasi empirical" approach to mathematics[0] where the adoption of new axioms (such as for example the axiom of choice) is justified by their resulting in new, interesting mathematics. But here, it seems his goal is to arrive at a somewhat Platonic conclusion, that either the reals are valid numbers or (seemingly he…
Read the full comment
prefers) not. My lay and naive take would be: if you adopt these rules (this Formal Axiomatic System) then you can have Big Fun in the playground of ever more esoteric and complex infinite cardinals, or if you adopt this other FAS you get to discover which results can and can't be obtained under a strict constructivist regime, and whichever FAS you choose it's just the same process of choosing axioms and applying valid deductive steps to arrive at a result you find interesting, with no more "existence" implied than the thoroughly non-Platonic existence of a solution to a problem, which can be demonstrated by solving it: if you take such-and-such steps then such-and-such result will follow. I suppose the point being made is that avoiding axioms which imply the "existence" of the reals is more useful for doing physics, but that seems non-obvious in a field which for the last 200 years has seemingly sought to progressively make more and more phenomena intelligible by means of differential equations from infinitesimal calculus! 0: see, for example: https://arxiv.org/pdf/math/0303352, 1.9 Is Mathematics Quasi-Empirical
pizza
Neutral mention · rule
allow me to make your day: - Computational trinitarianism, or how 1.) propositions as types, 2.) programs as proofs, and 3.) the relation between type theory and category theory are one and the same thing [0] - Scott aaronson's excellent "Why Philosophers Should Care About Computational Complexity" [1] - "From Philosophy to Program Size" by Greg Chaitin. Arguably Chaitin's work (notably Chaitin's omega) is a quintessential example of what lies at the intersection of mathematics, computation, and philosophy.[2] - From the inimitable Juergen Schmidhueber, "Driven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise,…
Read the full comment
Interestingness, Attention, Curiosity, Creativity, Art, Science, Music, Jokes" [3] - A computational biology paper that presents a meta-learning scheme for cognition and emotion. This paper's idea has really stuck with me.. That and the whole notion of the "Dark room problem" (you could, probably, really easily come up with a strategy for living life according to a hybrid of what this article presents + any kind of philosophy there is) - "Emotional Valence and the Free-Energy Principle" [4] [0] https://ncatlab.org/nlab/show/computational+trinitarianism [1] https://www.scottaaronson.com/papers/philos.pdf [2] https://arxiv.org/abs/math/0303352 [3] https://arxiv.org/abs/0812.4360 [4] http://journals.plos.org/ploscompbiol/article?id=10.1371/jou...

Keep following the thread.

More in Mathematics

More from the same topics.

1994arXiv

On proof and progress in mathematics

William P. Thurston

In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.

29 mentions21 months
9HN score