My AIT course is online

[Charles Alexandre Bédard]

Dear AIT enthusiasts,

The lecture recordings of my AIT course are now freely available: https://www.youtube.com/playlist?list=PLdL1rYhN7DtjGYIfKpQBUuzlUGGet4Fm8.

I haven't found many open-access AIT courses online (is there even one?), so I thought it worthwhile to make mine accessible.

Comments and criticisms are welcomed. 

Charles Bédard

[John Tromp]

> I haven't found many open-access AIT courses online (is there even one?), so I thought it worthwhile to make mine accessible.
> Comments and criticisms are welcomed.

Thanks for making your lectures available online, Charles!

I'd like to comment that the choice of computing formalism,
namely that of Turing machines, makes the theory less concrete than
one might like.

For instance, all upper bounds have this + O(1) term instead of a
concrete constant.
And even for the simplest machines, like the identity machine in lecture 13,
the machine is not explicit. We don't know how many states it has. We don't know
at what index it appears in the enumeration T1,T2,T3 of Turing machines.
In fact we don't know what T1. or any Ti is in that enumeration,
because it was never made
explicit. The universal machine itself was not made explicit.

It's true that none of these matter as long as we're happy with having
unknown O(1) terms.
But I think the ability to show explicit machines, and to provide
explicit constants
could make the theory more concrete and easier to grasp for students,
as well as more applicable.
They could actually write the programs that prove theorems and run
them on test data.
It allows for making the course hands-on.

I like Chaitin's work partly because he supported concrete definitions
of complexity,
and invited students to do some actual AIT programming.
I feel that nowadays we have even better languages available than
Chaitin's custom LISP variants [1].

I notice that in that same lecture 13, you try to make the identity
program more concrete by
showing the statement print "x", and try to argue about the length of
that statement.
The problem is that such statements are in fact not |x| + O(1) since
it uses " as a delimiter,
necessitating escape characters when x itself contains quotes.

I think the correspondence between binary strings and numbers should certainly
include the number 0, which is after all the length of the empty
string which you also include.

regards,
-John

[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861

[Jean-Louis Dessalles]

Le 09/06/2025 à 21:15, Charles Alexandre Bédard a écrit :

I haven't found many open-access AIT courses online (is there even one?), so I thought it worthwhile to make mine accessible.

Thank you so much Charles Alexandre for sharing these lectures.

This gives me the opportunity to remind the list of the MOOC on AIT applied to AI (scroll down below).
The two resources complete each other well  (the MOOC is probably less formal).
I think both should be recommended to all our students.

jean-louis

Hi everyone,

The MOOC on Algorithmic Information & AI  is back online on EdX.
The current session will run until end 2025.
This is a self-paced course. Access is free, but students have to pay 55€ to get the certificate.

Please encourage your students to enroll.

Thanks,

jean-louis Dessalles

========================================

Dear colleagues,

The  MOOC "AIAI" offers a gentle introduction to Algorithmic Information and its applications to AI.
It's a great suggestion to give to your students before the end of the semester
and also a nice way to motivate them to follow Algorithmic information Theory (AIT) classes
and to question the theoretical foundations of machine learning.

• Title:
  Understanding Artificial Intelligence through Algorithmic Information Theory
• Main purpose:
  to bridge the gap between theory and applications
  Also: to make more people aware of AIT and of its importance
• Links:
  -> see the Presentation of the MOOC
  -> access to the MOOC on the EdX platform
  

We did our best to find a compromise between rigor and accessibility.
You might consider the MOOC as a tentative popularization of AIT for
students having a bachelor degree in math, computer science, engineering...

The MOOC consists of 5 chapters:

1. Describing data through compression (code length, Kolmogorov complexity)
   
2. Algorithmic Information and Data (complexity and frequency, 'Google' distance, Zipf's law)
   
3. Algorithmic Information and mathematics (Algorithmic probability, randomness, Gödel's theorem in three lines)
   
4. Algorithmic Information and machine learning (Induction, minimum description length, Analogy, ML as compression)
   
5. Algorithmic Information and cognitive AI (subjective information, subjective probability, relevance)
   

I hope you'll be curious about the MOOC's content,
and that you will welcome its existence.

When applicable, please recommend the MOOC to your students and friends.
And your advice on how to improve the MOOC will be appreciated!

        jean-louis Dessalles

    

    Visit this MOOC: Understanding AI through Algorithmic Information Theory.

            

    "A very interesting course that definitely changed how I see the world. Thank you so muchhh." (Hanady, 2021, betatester)
    "Very interesting course. It opens a lot of prospects. Thank you very much." (BORG_92, MOOC user)

    "Enlightening. Thank you for organizing this amazing course. I learned a lot! [...]
    After completing the course I’m now contemplating the final chapter on complexity+cognition.
    This chapter was so intuitive and provided such elegant explanations of human behavior."    (Palmaya, MOOC user)

--

jean-louis Dessalles

________
________ Visit Simplicity Theory to read ST's predictions
________ about relevance, interest, emotion, responsibility, creativity.

[Charles Alexandre Bédard]

Thank you John for the precious comments.

If I understand correctly, in binary lambda calculus (BLC), you exhibit an additively optimal concrete computer, and all of it is in bits. Is this right?

I notice that in that same lecture 13, you try to make the identity
program more concrete by
showing the statement print "x", and try to argue about the length of
that statement.
The problem is that such statements are in fact not |x| + O(1) since
it uses " as a delimiter,
necessitating escape characters when x itself contains quotes.

You are right.

Isn't that bringing up the fact that actual programs must be self-delimited?

[John Tromp]

> If I understand correctly, in binary lambda calculus (BLC), you exhibit an additively optimal concrete computer, and all of it is in bits. Is this right?

Yes, the Universal Lambda machine is given in [3]
and fits on two lines. It is a lambda term which translates almost
directly into 232 bits of blc code.

Implementations in many other languages can be found at
https://rosettacode.org/wiki/Universal_Lambda_Machine

Someone even wrote a Turing Machine interpreter of BLC, so that they
could translate
my lambda Busy Beaver lower bound BBλ(1850) > Loader's number [1]
to a TM Busy Beaver lower bound BB(1015) > Loader's Number [2].

> Isn't that bringing up the fact that actual programs must be self-delimited?

This particular theorem is about delimited, not self-delimiting programs.
It's also the first theorem I show in
https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#complexity-concretely
as 𝐾𝑆(𝑥) ≤ ℓ(𝑥)+4
So this program for x consists of a self-delimiting 4-bit code of the
identity function,
following by the ℓ(𝑥) bits of x.

regards,
-John

[1] https://oeis.org/A333479
[2] https://github.com/CatsAreFluffy/metamath-turing-machines/tree/master
[3] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#lambda-encoding

[jabowery]

On Tuesday, June 10, 2025 at 6:49:47 AM UTC-5 john.tromp wrote:

...

But I think the ability to show explicit machines, and to provide
explicit constants
could make the theory more concrete and easier to grasp for students,
as well as more applicable.

Hence DCGs of universal logic gates (such as NOR or NAND) and the admission that any applied theory of computation must be within the set of finite state machines.

I find the absence of literature on this approach to measures of complexity quite puzzling.  This gap can't be as trivially explained as people getting confused about the difference between DAGs and DCGs.  That's much too obvious a difference for people to ignore for a half century during which boolean networks have been in the literature.

They could actually write the programs that prove theorems and run
them on test data.

And with DCGs of logic gates they could implement the machines in hardware as well.
 

It allows for making the course hands-on.

For example, here's a browser-based digital circuit emulator that permits students to create computer hardware:

https://circuitverse.org/simulator

I like Chaitin's work partly because he supported concrete definitions
of complexity,

It would be interesting to see some trivial examples of bit sequences ask students to make "simple" circuits to output them.  Then it becomes interesting to study various complexity bounds:

* What exactly does it mean for one DCG of universal gates to be simpler than another?
* At what point is it "simpler" to include addressable memory elements?
* At what point is it "simpler" to include RW addressable memory elements?

and invited students to do some actual AIT programming.
I feel that nowadays we have even better languages available than
Chaitin's custom LISP variants [1].

An obvious question arises:

What is the simplest DCG of universal gates that can support binary lambda calculus (understanding, of course, that RW addressable memory elements would entail encode/decode trees that grow as log of the addressable memory space).

This gets back my Gödelesque approach to all of this in what I called "NiNOR Complexity" as a top-down approach to reducing the freedom to choose that pesky "O(1) parameter.  Being "top down" it doesn't satisfy the desire for an applicable definition, which kicked this off, but it should make my reasoning for that approach more relevant to applicability.