Computer Science

Assignment: Write a compiler that compiles all programs that can't compile themselves.
Extra Credit: Use the compiler to compile assignment.

At this point we’ve developed a complete, though very simple, interpreter and runtime environment.  To some degree, this interpreter is all we need.  It can express any function, it can easily be extended, it has a simple parser, and it has a working garbage collector.  What more could we ask for?  Life is good.

Life is good, that is, until we ask somebody else to use it.  Their first response is probably an annoyance at the syntax — it’s a little surprising to have to write (+ 1 1) after grade school has burned 1 + 1 into our minds — and, truth be told, the S-Expression syntax isn’t the most natural or compact for every problem.

Luckily we can, with a little work, entirely eliminate this complaint by creating a parser generator — a function that takes as input a grammar (a formal description of a language), and produces as output a parser for that language.

Read the rest of this entry »

Building sophisticated educational tools out of cheap parts, Johnny Lee demos his cool Wii Remote hacks, which turn the $40 video game controller into a digital whiteboard, a touchscreen and a head-mounted 3-D viewer.

to read more about Johnny Lee, visit his website

In the previous articles of this series we’ve seen how to create a simple Scheme interpreter, then how to write an S-Expression parser to feed the interpreter, and in the last article we saw how to most conveniently bind C++ functions to our interpreter with the strategic application of template classes and a “meta-circular” code-generator that built up a vital part of our interpreter (using our interpreter to do it).

Though we’ve come a long way, there’s still one glaring hole in our interpreter design: we’ve left the allocate<T> function unspecified.  This function is meant to allocate a garbage collected value of type T, which implies that we’ve got to write a garbage collector.  In this article, that’s exactly what we’ll do.

Read the rest of this entry »

The most embarassing memory I have about my intellectual development as a computer scientist was the day I decided that maybe Turing got that halting problem thing wrong. I know, I know, what was a thinking! Blame it on youth. But I also blame it on a gap in my education on the theory of computation. See, I was taught about Turing Machines (TM) but was never exposed to Busy Beavers (BB) until much later.

My thinking at the time was that Turing pulled out a very contrived type of TM in his halting problem proof. He made the TM self referential to achieve the proof. So my thinking was that perhaps the only class of TM that could evade a halting detection algorithm was the class offered by Turing in his proof. I thought it was possible for the vast majority of other TM to be shown to halt algorithmically. My thinking went as follows:

1. A TM is a deterministic device.
2. If a TM goes through a sequence of states and at some point returns to a state already visited without halting then that TM will never halt. Here it is important to relaize I am including the tape in the state specification.

My "algorithm" for detecting a TM that did not halt was simply to run a TM in a simulator that at each step would save a snapshot of the entire state and compare to previous snapshots to find a duplicate. If a duplicate was found then it would declare the TM would not halt. For this to actually work the algorithm would have to set some bounds on how long it would run the simulation. I did not think this was a problem because I thought there was obviously a linear or at worst quadratic function based on the number of possible states in the input TM. And, of course, this is where I was wrong. Had I known about Busy Beavers I would not have gone down this road.

It turns out the the Busy Beaver function looks something like this for a two symbol TM:

States	Steps
1	1
2	6
3	38
4	>=3,932,964
5	>=1.9 × 10^704

Linear indeed!

The silver lining for me is that I learned a very important lesson (besides the one about not doubting a mathematical proof by someone of Turing's stature that withheld the scrutiny of thousands of individuals of similar stature). I learned that human intuition about the emergence of complexity from simple mechanisms is woefully poor. This lesson is repeated when we look at Cellular Automata in NKS. Its also repeated when we compute the number of possible configurations of a chessboard and compare that the estimates of the number of atoms in the known universe.

Luckily I learned my lessons while I was still quite young. Many individuals who believe themselves to be intellectuals have never learned to not always trust what they believe is intuitively reasonable. That not so bad except they use the web to infect the gullible with their intuitions. So, be careful out there! There are a lot of busy beavers with bad intuition.