There is a nice noncomputable Turing machine problem called
The Busy Beaver Problem that would make a nice presentation for 250.

I found 3 good links with a video and pictuers that will provide good visuals.
They are second from the top of the
applications link: http://cs.smith.edu/~jfrankli/250s11/applications.html


The problem:
What is the  smallest number of states  needed by a Turing machine
in order to output as much data as possible (as many ones), yet eventually halts on its own.

Another way to look at it is: given an n-state Turing machine with a two symbol alphabet
{0, 1}, what is the maximum number of 1s that the machine may print on an initially blank tape before halting?

This problem turns out to be non-computable, that is, for a small number of states an answer can be found, but in general it cannot be solved. The number of steps it takes to run to completion (halt) grows very rapidly as the number of states increase.


People actually write Turing Machine programs to try to "beat previous records" for particular ns.
In one of the links you'll see a visualization of one author's solutions for up to n=5 I think. They are very striking!

See what you think,

Judy F