Not sure about this specific paper, but I've been following John Tromp's work on this for a while. Its current homepage seems to be on GitHub https://tromp.github.io/cl/cl.html
The paper assumes knowledge of combinatory logic and lambda calculus, which you could probably find videos about. This paper uses pretty standard notation, so almost any video/course/book/blog/etc. should be OK. The main thing this paper does is to define a way to encode such programs as a string of bits.
Note that combinatory logic is one of the simplest Turing-complete programming languages, but it's so simple that it's basically unusable for anything more elaborate than toy examples (the paper actually has a quote from Chaitin saying this!). Once you're comfortable playing with little examples containing a handful of symbols, that's basically all you really need.
If you're familiar with other programming languages, it's usually pretty easy to implement combinatory logic and play with it. For example, here are 'S' and 'K' in Javascript:
function k(x, y) { return y; }
function s(x, y, z) { return x(z)(y(z)); }
This isn't quite right, due to most languages using strict evaluation, but the following Haskell is essentially correct:
k x y = y
s x y z = x z (y z)
There's also the esoteric language "unlambda" which implements these directly, including the "monadic IO" that the paper mentions https://en.wikipedia.org/wiki/Unlambda
Lambda calculus is more tricky than combinatory logic, since it contains variables. It's also more widely used (e.g. as the basis for many functional programming languages, like Haskell and Scheme), so there should be more material available. In essence, when you see something like:
λa b c.x y z
You can think of it as acting like this Javascript:
function(a, b, c) {
return x(y)(z);
}
When it comes to Kolmogorov complexity, maybe the Wikipedia page and its citations will help ( https://en.wikipedia.org/wiki/Kolmogorov_complexity )? Notice that all of the definitions, etc. on that page assume that we're talking about some particular programming language or machine, but the examples use pseudocode rather than a "real" programming language. This paper is basically saying that we should use lambda calculus as that language, and we can measure the size/length of a program by encoding it as binary according to the method given.
The paper assumes knowledge of combinatory logic and lambda calculus, which you could probably find videos about. This paper uses pretty standard notation, so almost any video/course/book/blog/etc. should be OK. The main thing this paper does is to define a way to encode such programs as a string of bits.
Note that combinatory logic is one of the simplest Turing-complete programming languages, but it's so simple that it's basically unusable for anything more elaborate than toy examples (the paper actually has a quote from Chaitin saying this!). Once you're comfortable playing with little examples containing a handful of symbols, that's basically all you really need.
There's a nice book of mathematical puzzles https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird which is actually based on combinatory logic. This is why combinatory logic terms are sometimes referred to as "birds", e.g. in this Haskell library: https://hackage.haskell.org/package/data-aviary-0.4.0/docs/D...
If you're familiar with other programming languages, it's usually pretty easy to implement combinatory logic and play with it. For example, here are 'S' and 'K' in Javascript:
This isn't quite right, due to most languages using strict evaluation, but the following Haskell is essentially correct: There's also the esoteric language "unlambda" which implements these directly, including the "monadic IO" that the paper mentions https://en.wikipedia.org/wiki/UnlambdaLambda calculus is more tricky than combinatory logic, since it contains variables. It's also more widely used (e.g. as the basis for many functional programming languages, like Haskell and Scheme), so there should be more material available. In essence, when you see something like:
You can think of it as acting like this Javascript: When it comes to Kolmogorov complexity, maybe the Wikipedia page and its citations will help ( https://en.wikipedia.org/wiki/Kolmogorov_complexity )? Notice that all of the definitions, etc. on that page assume that we're talking about some particular programming language or machine, but the examples use pseudocode rather than a "real" programming language. This paper is basically saying that we should use lambda calculus as that language, and we can measure the size/length of a program by encoding it as binary according to the method given.