Program Synthesis Specification

This post will be a small note on program specifications. One of my long-term goals is that of a bootstrapping program synthesizer. That is, a program synthesizer that can synthesize better program synthesizers. One important step is specifying, formally, what this means. I’ve recently figured out how to properly formulate... [Read More]

My (mis)adventures With Algorithmic Machine Learning

Introduction Why Not Use Ordinary Compression? Methods for Approximating Kolmogorov Complexity Approximating Conditional Kolmogorov Complexity using CTM Block Decomposition Spit-balling ways to improve DBM and CTM Algorithmic Loss Algorithmic Optimization Final Thoughts [Read More]

Datatypes As Dialgebras

I’ve known for a while that dependent types can be defined as initial and final dialgebras. This is a somewhat obscure fact; but an important generalization of the more commonly referenced fact that non-dependent types are initial and final (co)algebras of specific endofunctors. The only thorough source of this fact... [Read More]

Sorting Lists Recursively; The Easy Way

In this post, I will show a nice, clean, organized, schematic, and theoretically well-justified approach to sorting. I’ll implement it in Python because of my target audience, but there’s no significance to the choice beyond that. I’m going to describe and implement Merge Sort and Quicksort via hylomorphisms. That may... [Read More]