Putting together an indpendent study in CS

[Basu]

Hello all, I'm going to be a sophomore in college next semester looking at a double major in computer science and electrical engineering. Since I decided on the CS major later, I'm lagging a bit behind on my intro requirements. Normally Freshmen take a course in Logic, which I planned to take next semester. However looking on the topics covered and considering that I've already taken a course in discrete mathematics, I think it would be a bit of waste of time. Luckily the department is very accommodating. I'm trying to put together an independent study on the mathematical and theoretical foundations of computer science to take the place of the Logic course. Having never put together an independent study proposal, some help would be appreciated.
Firstly, we already have a higher level Theory of Computation course and I would prefer to keep overlaps to a minimum. Here is what that course contains:

1. Finite Automata
2. Regular languages
3. Context free languages
4. Turing Machines
5. Decidability
6. NP completeness


I'm considering focusing on the Turing Machine and Lambda calculus as models of computation, but I'm not sure f that is enough/too little. The way I see it, there are the following things I need to keep in mind while constructing this course:

1. What to study: Here is a rough outline of what I have in mind:
Turing Machines
The Church-Turing Thesis
Lamdda Calculus
Combinatory Logic
Curry-Howard correspondence
Functional Programming languages as Lambda calculus 'implementations'

2. What to produce: I don't want to just read up stuff on these subjects, I want to actually have something to show. I'm considering a series of mini papers (5-10 pages, every 2 weeks) summarizing what I have read and my thoughts on the subjects. At the same time, I want to do some programming. I would like to learn Lisp and maybe come up with a minimalistic Turing complete language, prove it to be such and perhaps build a simple interpreter for it. I already have some experience writing parsers from a research project at college and would like to expand on that.

I'm going to keep thinking about this and talk to my professors about it. Any advice would be appreciated. Thanks again for your help.

Basu

[Zeroth]

I would like to point out it can be difficult to prove a language is turing complete. At least to a degree that is accepted by CS professors. For example, it took a couple of years of effort to prove Python was turing-complete, iirc. I could be wrong here. Otherwise, that looks like a very interesting and full course of study. You don't need anything else, and you'll find you don't have the time for all of that, I suspect.

[rizzix]

The best advice is what you've already decided to do: talk to your prof. If your prof is involved with the kind of research you're interested in, then you're really really lucky; since he can guide you better than he could otherwise.

Also, talk to some post-docs/phds (non-profs) that have similar interests.

[Dragan]

Basu @ Sat Jul 05, 2008 7:09 am wrote:

I would like to learn Lisp

Why Lisp, Lisp is basicly for AI programming, but all serious AI projects are writen in "c". You can learn Lisp but don't lose much time for it, learn some more useful languages like c, c++, C#, java, php...

Decision is yours.

[Basu]

LISP may have been the favored language for AI for a long time, but it developed as a convenient expression for Lambda calculus. I think I might focus my study on Lambda calculus, its implementation and it's relation to the Turing Machine, rather than on Turing-completeness itself.
And I can always learn new languages and tools when I want/need to. I couldn't (and shouldn't) get a for-credit independent study approved for simply learning a new language.

[Basu]

So I just came back from a talk with my professor. He likes the idea of taking up lambda calculus and functional programming. He's suggested that I do the second half of SICP (I've gone through the first 2 chapters on my own). I will probably also incorporate elements from our programming languages and a general overview of some popular models of computations. Any suggestions are welcome.

[Prabhakar Ragde]

Zeroth @ Sat Jul 05, 2008 9:24 am wrote:

I would like to point out it can be difficult to prove a language is turing complete. At least to a degree that is accepted by CS professors. For example, it took a couple of years of effort to prove Python was turing-complete, iirc. I could be wrong here.

Citation, please. --PR