Hack of the Whenever I Get Around to It

January 26, 2009

Memory Restricted Brainfsck

Filed under: Uncategorized — Chris Merck @ 4:08 am

This past summer I had a rather crazy summer research semester. I kicked it off with a trip to Norway to take a course on Engineering Entrepreneurship and generally just see the beautiful country. By the time I returned to Hoboken my copy of Svozil’s Randomness and Undecidability in Physics had arrived via interlibrary loan. I got the book just to read his analysis of the logistic map, but then I fell in love with the whole thing. Reading this book opened my mind to some way-abstract modes of thought, for better or for worse. I will never think about physics and comp-sci the same way.

Although my summer research proposal was to build a digital attractive-maglev controller, and I actually spent most of my time setting up an ultimately flawed raman gain spectroscopy experiment, my most productive time was during the last week of the summer in which time I wrote A Paper on Memory-Restricted Brainfucks.

The basic idea is to see what happens when we take a simple machine model, like brainfuck, and restrict the memory to just a few cells which may take on only a few values. The result is a so-called “finite machine” which is, of course, not Turing-complete, but which may be provably complete in some analogous sense. The paper contains an exposition of the finite brainfuck (called Q), an outline of a finite-completeness proof, and results of some brute-force attempts to find the elegant and neat implementations for all functions of a particular order.


developing in mind/GVim/Scheme/Ubuntu/GNU/Linux/X86/Nature

All the source code implementing the Q interpreter and the experiments thereupon is written in Scheme and is included at the end of the paper.

Blog at WordPress.com.