6 ms·

Author here. The paper is currently in a state of flux, as I started adding material about the graphical notation, but didn't get very far before my attention d

by tromp 8y ago

Author here. The paper is currently in a state of flux, as I started adding material about the graphical notation, but didn't get very far before my attention drifted to other topics. So please have a look at the following page as well http://tromp.github.io/cl/cl.html http://tromp.github.io/cl/cl.html which links to an explanation of the graphical notation, to my corresponding IOCCC entry from 2012, and to a Wikipedia page on Binary Lambda Calculus that has since been deleted.

Verdex_3 8y ago
Is there a prose explanation or justification for Algorithm Information Theory. I think I first heard of it when I saw your IOCCC entry, but I was never able to get my mind wrapped around what the goal of the whole field was.
- antidesitter 8y ago
  The goal of AIT is to study the complexity of mathematical objects as defined through models of computation.
- jkabrg 8y ago
  I guess it provides an objective definition of when something is simple or complicated. This could have applications in statistics or machine learning, where "simpler" hypotheses could be less likely to overfit. There are computable measures of "simplicity" (unlike Kolmogorov complexity) based on compression algorithms or computation time (Levin complexity). There are also apparently connections to statistical mechanics, but I haven't looked into it and I don't know if it's useful. See this paper on how to cluster using compression: https://arxiv.org/pdf/cs/0312044.pdf https://arxiv.org/pdf/cs/0312044.pdf
joe_the_user 8y ago
Serious question. Is Lambda calculus a good match for algorithmic information theory. The versions of AIT I've read involved either Turing machines, hand-waving of computation or recursive function. Lambda calculus seems more complex and thus harder to integrate with an AIT that mostly needs to know that strings are programs, that not all programs terminate, that some programs can give a substring of their string as outputs and so-forth.
- tromp 8y ago
  In my view lambda calculus is a perfect match for AIT since the language is both so simple and so expressive. This should be readily apparent from the concise self-interpreter. The versions of AIT that you've seen based on TMs probably didn't have any explicit constants because determining them would be much too cumbersome. Chaitin was the first to prove theorems in AIT with actual programs and he resorted to LISP. I'm positioning lambda calculus as an even better choice.
- chriswarbo 8y ago
  Lambda calculus is certainly tricky for counting steps, since a single step of beta-reduction can actually do a lot of "work", unlike e.g. a Turing machine where each step takes constant resources. For AIT, the binary encodings used in this paper have the nice property that they're complete and prefix-free, meaning that every binary string either decodes to a term (perhaps using only an initial portion of the string), or can be extended (arbitrarily) until it gives rise to a term. At first glance, it feels like it would be hard for lambda terms to "give a substring of their string as outputs", since that would require re-encoding a subterm. However, I don't think that's as bad as it sounds. For example, consider that a Turing machine can only move its head along the tape one cell at a time (we could use any finite step size, but we usually stick to one), which makes it difficult/impossible to "preserve" a section of tape. Hence Turing machines which "give a substring of their string as outputs" might sound simple, but would probably be somewhat complicated to ensure that any "corruption" caused when traversing the tape gets "undone" afterwards. (Unless they're multitape machines, like monotone turing machines!)
- jandrewrogers 8y ago
  IMHO, function composition is a better computational model than function application for expressing algorithmic information theory. Concatenative languages (e.g. Joy) are probably the closest examples, though popular examples are not optimal by any means.
sagebird 8y ago
I am loving this paper so far, brings together some nice ideas with a good eye for knowing what sub topics to explore. The graphical notation is reminiscent of certain graphics that can be expressed with a recursive png tool at http://williamsharkey.com/PNG-Gen.html http://williamsharkey.com/PNG-Gen.html . This paper is the first time I took the effort to learn lambda calculus notation and work through to understand the examples so you deserve credit for motivating me.

by tromp 8y ago

Verdex_3 8y ago

Is there a prose explanation or justification for Algorithm Information Theory. I think I first heard of it when I saw your IOCCC entry, but I was never able to get my mind wrapped around what the goal of the whole field was.

antidesitter 8y ago
The goal of AIT is to study the complexity of mathematical objects as defined through models of computation.
jkabrg 8y ago
I guess it provides an objective definition of when something is simple or complicated. This could have applications in statistics or machine learning, where "simpler" hypotheses could be less likely to overfit. There are computable measures of "simplicity" (unlike Kolmogorov complexity) based on compression algorithms or computation time (Levin complexity). There are also apparently connections to statistical mechanics, but I haven't looked into it and I don't know if it's useful. See this paper on how to cluster using compression: https://arxiv.org/pdf/cs/0312044.pdf https://arxiv.org/pdf/cs/0312044.pdf

joe_the_user 8y ago

Serious question. Is Lambda calculus a good match for algorithmic information theory. The versions of AIT I've read involved either Turing machines, hand-waving of computation or recursive function. Lambda calculus seems more complex and thus harder to integrate with an AIT that mostly needs to know that strings are programs, that not all programs terminate, that some programs can give a substring of their string as outputs and so-forth.

tromp 8y ago
In my view lambda calculus is a perfect match for AIT since the language is both so simple and so expressive. This should be readily apparent from the concise self-interpreter. The versions of AIT that you've seen based on TMs probably didn't have any explicit constants because determining them would be much too cumbersome. Chaitin was the first to prove theorems in AIT with actual programs and he resorted to LISP. I'm positioning lambda calculus as an even better choice.
chriswarbo 8y ago
Lambda calculus is certainly tricky for counting steps, since a single step of beta-reduction can actually do a lot of "work", unlike e.g. a Turing machine where each step takes constant resources. For AIT, the binary encodings used in this paper have the nice property that they're complete and prefix-free, meaning that every binary string either decodes to a term (perhaps using only an initial portion of the string), or can be extended (arbitrarily) until it gives rise to a term. At first glance, it feels like it would be hard for lambda terms to "give a substring of their string as outputs", since that would require re-encoding a subterm. However, I don't think that's as bad as it sounds. For example, consider that a Turing machine can only move its head along the tape one cell at a time (we could use any finite step size, but we usually stick to one), which makes it difficult/impossible to "preserve" a section of tape. Hence Turing machines which "give a substring of their string as outputs" might sound simple, but would probably be somewhat complicated to ensure that any "corruption" caused when traversing the tape gets "undone" afterwards. (Unless they're multitape machines, like monotone turing machines!)
jandrewrogers 8y ago
IMHO, function composition is a better computational model than function application for expressing algorithmic information theory. Concatenative languages (e.g. Joy) are probably the closest examples, though popular examples are not optimal by any means.

sagebird 8y ago

I am loving this paper so far, brings together some nice ideas with a good eye for knowing what sub topics to explore. The graphical notation is reminiscent of certain graphics that can be expressed with a recursive png tool at http://williamsharkey.com/PNG-Gen.html http://williamsharkey.com/PNG-Gen.html . This paper is the first time I took the effort to learn lambda calculus notation and work through to understand the examples so you deserve credit for motivating me.