Theory of Computing project topics

Question

I am looking for project ideas in theory of computing that I can assign to my students in lieu of a final exam.

Answer 1

If you're looking for something much harder than my other answer, and your CT course has covered lambda calculus, you can have the students create an untyped lambda calculus REPL, with inputs/outputs that look like this:

> ; just a blank line
>
> justanatom
justanatom
> x;withcommentnospaces
x
> 0 = \f.\x.x
Added (λf.(λx.x)) as 0
> succ = \n.\f.\x.f (n f x)
Added (λn.(λf.(λx.(f ((n f) x))))) as succ
> 1 = run succ 0
Added (λf.(λx.(f x))) as 1
> + = λm.λn.λf.λx.(m f) ((n f) x)
Added (λm.(λn.(λf.(λx.((m f) ((n f) x)))))) as +
> * = λn.λm.λf.λx.n (m f) x
Added (λn.(λm.(λf.(λx.((n (m f)) x))))) as *
> 2 = run succ 1
Added (λf.(λx.(f (f x)))) as 2
> 3 = run + 2 1
Added (λf.(λx.(f (f (f x))))) as 3
> 4 = run * 2 2
Added (λf.(λx.(f (f (f (f x)))))) as 4
> 5 = (λf.(λx.(f (f (f (f (f x)))))))
Added (λf.(λx.(f (f (f (f (f x))))))) as 5
> 7 = run succ (succ 5)
Added (λf.(λx.(f (f (f (f (f (f (f x))))))))) as 7
> pred = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
Added (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u))))) as pred
> 6 = run pred 7
Added (λf.(λx.(f (f (f (f (f (f x)))))))) as 6
> - = λm.λn.(n pred) m
Added (λm.(λn.((n (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u)))))) m))) as -
> 10 = run succ (+ 3 6)
Added (λf.(λx.(f (f (f (f (f (f (f (f (f (f x)))))))))))) as 10
> 9 = run pred 10
Added (λf.(λx.(f (f (f (f (f (f (f (f (f x))))))))))) as 9
> 8 = run - 10 2
Added (λf.(λx.(f (f (f (f (f (f (f (f x)))))))))) as 8
> true = λx.λy.x
Added (λx.(λy.x)) as true
> false = 0
Added (λf.(λx.x)) as false
> not = λp.p false true
Added (λp.((p (λf.(λx.x))) (λx.(λy.x)))) as not
> even? = λn.n not true
Added (λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) as even?
> odd? = \x.not (even? x)
Added (λx.((λp.((p (λf.(λx.x))) (λx.(λy.x)))) ((λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) x))) as odd?
> run even? 0
true
> run even? 5
false
> run (λy.λx.(x y)) (x x) 
(λx.(x (x x)))
> run (\x. \x . x) y z
z

Fair warning: I do this with my students. The project can be devastatingly difficult for students at this level, and takes every bit of programming knowledge and computational theory know-how that they've developed to create. You'll want to create a gentle, alternate grading rubric for projects that don't really come together before the deadline.

Answer 2

Here are a few projects that you could use:

• A Turing Machine simulator that, given a specification of a machine and an input, finds some way to simulate the behavior of the machine and provide some sort of (compact) readout of the tape and final state.
• If you're looking for a bit of fun, use said TM simulator to enter into a contest (I do this with my own students): a variant of the Busy Beaver where the machine must halt on its own before a specified deadline. Students are free to take as many attempts as they'd like. However, velocity matters, because the final run must be complete by the deadline (typically at the start of class on a certain date), and you will examine all final readouts during that class. The person or team with the most "1"s on their tape is declared the winner. I call it the Daring Duck, and I have outlined details of the project here.
• A much harder project, if you're looking for that, is to have students create turing machine calculators. The TM should be able to perform any of the four basic arithmetic operations. For an activity like this, I would recommend using a tool like Turing Machine Simulator, as it provides excellent visualization of what the TM itself is doing.

Answer 3

Have them write a translator from non-deterministic automata to the equivalent deterministic ones. For regular languages you know that they recognize the same languages. I'd have to look up how that is for context-free/sensitive. ND Push-down automata with multiple stacks are more powerful than their D equivalent; let them test an example.