Lecture Notes on Algorithmic Information Theory
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916707809886208 |
|---|---|
| author | Bédard, Charles Alexandre |
| author_facet | Bédard, Charles Alexandre |
| contents | Algorithmic information theory roots the concept of information in computation rather than probability. These lecture notes were constructed in conjunction with the graduate course I taught at Università della Svizzera italiana in the spring of 2023. The course is intended for graduate students and researchers seeking a self-contained journey from the foundations of computability theory to prefix complexity and the information-theoretic limits of formal systems. My exposition ignores boundaries between computer science, mathematics, physics, and philosophy -- an approach I consider essential when explaining inherently multidisciplinary fields. Lecture recordings are available online. Among other topics, the notes cover bit strings, codes, Shannon information theory, computability theory, the universal Turing machine, the Halting Problem, Rice's Theorem, plain algorithmic complexity, the Invariance Theorem, incompressibility, Solomonoff's induction, self-delimiting Turing machines, prefix algorithmic complexity, the halting probability Omega, Chaitin's Incompleteness Theorem, The Coding Theorem, lower semi-computable semi-measures, and the chain rule for algorithmic complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18568 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lecture Notes on Algorithmic Information Theory Bédard, Charles Alexandre Information Theory Logic in Computer Science Algorithmic information theory roots the concept of information in computation rather than probability. These lecture notes were constructed in conjunction with the graduate course I taught at Università della Svizzera italiana in the spring of 2023. The course is intended for graduate students and researchers seeking a self-contained journey from the foundations of computability theory to prefix complexity and the information-theoretic limits of formal systems. My exposition ignores boundaries between computer science, mathematics, physics, and philosophy -- an approach I consider essential when explaining inherently multidisciplinary fields. Lecture recordings are available online. Among other topics, the notes cover bit strings, codes, Shannon information theory, computability theory, the universal Turing machine, the Halting Problem, Rice's Theorem, plain algorithmic complexity, the Invariance Theorem, incompressibility, Solomonoff's induction, self-delimiting Turing machines, prefix algorithmic complexity, the halting probability Omega, Chaitin's Incompleteness Theorem, The Coding Theorem, lower semi-computable semi-measures, and the chain rule for algorithmic complexity. |
| title | Lecture Notes on Algorithmic Information Theory |
| topic | Information Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2504.18568 |