> let’s assume that there exists a universal language U
Why not specify it?
> That gives us the true language-agnostic definition of Kolmogorov Complexity as follows:
Choosing the language of Turing Machines does not make the definition language agnostic.
Aiming for the simplest definition of description complexity, I instead based my definitions on the older computational model of lambda calculus in [1].
Unlike the assumed UTM above, the universal lambda machine is easy to describe in detail:
(λ 1 1) (λ λ λ 1 (λ λ λ λ 3 (λ 5 (3 (λ 2 (3 (λ λ 3 (λ 1 2 3))) (4 (λ 4 (λ 3 1 (2 1)))))) (1 (2 (λ 1 2)) (λ 4 (λ 4 (λ 2 (1 4))) 5)))) (3 3) 2) (λ 1 ((λ 1 1) (λ 1 1)))
Furthermore, it allows almost identical definitions of various variations of descriptional complexity, namely
1) plain complexity
2) prefix complexity
3) monotone complexity
all of which have their application in Algorithmic Information Theory [2].
[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
[2] https://homepages.cwi.nl/~paulv/kolmogorov.html
Why not specify it?
> That gives us the true language-agnostic definition of Kolmogorov Complexity as follows:
Choosing the language of Turing Machines does not make the definition language agnostic.
Aiming for the simplest definition of description complexity, I instead based my definitions on the older computational model of lambda calculus in [1].
Unlike the assumed UTM above, the universal lambda machine is easy to describe in detail:
Furthermore, it allows almost identical definitions of various variations of descriptional complexity, namely1) plain complexity
2) prefix complexity
3) monotone complexity
all of which have their application in Algorithmic Information Theory [2].
[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
[2] https://homepages.cwi.nl/~paulv/kolmogorov.html