Code Compression

The Code Compression Bibliography

The work of Gregory Chaitin on program size

Gregory Chaitin has published, since 1966, several theoretical papers on program size. In fact, Chaintin's main work is on program size -- his latest publication, at the 2003 Estonian Winter School, (Chaitin at the 2003 Estonian Winter School), states that program-size complexity, compared to time-complexity, has "greater philosophical significance". Is that work relevant to the size reduction of programs running on commercial -- e.g. Intel x86 -- processors? Chaintin himself answers by the negative. Despite that, we refer the reader to his work on program-size:

Related Links