# Introduction to the Theory of Computation

All Stack Overflow 7
This Month Stack Overflow 2

I recommend this book. It's used for the CMU course.

http://www.amazon.ca/Introduction-Theory-Computation-Second-Michael/dp/0534950973

but this one is the gold standard

http://en.wikipedia.org/wiki/File:Hopcroft-ullman-79-cover.jpg

The meaning of these terms varies depending upon your context. If we were discussing them purely from the standpoint of writing programs then recursive sets don't make much sense; however, it might just be that I have encountered it yet. That said, recursive functions are functions that call themselves in their execution. The calculation of a nth Fibonacci number is the classic example that is commonly presented:

``````/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
if (n <= 2) {
return 1;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
``````

That said, the other context for these terms in the context of computer science and specifically the theory of computation is when discussing of formal languages. In this context, a recursive set is defined to be a set for which there is a solvable membership problem. For example, we know that the set of all natural numbers ℕ is a recursive set because we can define a recursive function as follows:

Let f be defined as a function where f(x) = 1 if x ∈ ℕ and f(x) = 0 if x ∉ ℕ

The concept of a recursive set is important for the concept of computability because it leads to the recursively enumerable set which is a language that can be recognized by a Turing machine (i.e. Turing-recognizable). These are languages for which a Turing machine may or may not be able to determine if a given string is a member of a language, or in other words, the machine may either accept, reject, or loop. This is in contrast to a Turing-decidable language for which a the machine will enter into either the accept or reject state for a given input string.

This where the concept of a recursive function comes in play, as a recursive function (or total recursive function) can be computed by a Turing machine and halts for every input. Where as a partial recursive function can only be computed for a Turing machine with no guarantee in regard to halting behavior. Or in essence the recursive function is the counterpart to the recursive set.

So to bring things back around to your original question, in the context of the theory of computation, a recursive set is what can be generated (i.e. enumerated) or have membership tested by a recursive function on a Turing machine.

I'd recommend a good textbook on computer science (In my Uni course, I'm studying from Sipser's Introduction to the Theory of Computation, which is very good in my opinion. You might also find a free textbook which teaches the same, but I don't have any experience with one so I can't recommend).

The other approach would probably be just to read up on Wikipedia. You can actually get a lot of mileage out of the Wikipedia articles, if you know what you're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject.

Of course, this will not be as good as a real textbook, but it's a good place to get started right now, and it's free.

As a starting point, I'd recommend reading about the following topics (in the order listed):

1. Deterministic Finite Automaton
2. Nondeterministic Finite Automaton, and their equivalence to DFAs.
3. Regular Languages, and their equivalence to DFAs.
4. Pushdown Automata
5. Context-free Grammars, and their equivalence to Pushdown Automata.
6. Chomsky Hierarchy
7. Turing Machines

That should provide a very brief introduction to most of the computational models people talk about. 2: I'd recommend a good textbook on computer science (In my Uni course, I'm studying from Sipser's Introduction to the Theory of Computation, which is very good in my opinion). The other approach would probably be just to read up on Wikipedia. You can actually get a lot of mileage out of the Wikipedia articles, if you know what you're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject. As a starting place, I'd recommend reading about the following topics (in the order listed): 1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Write Code:

In this article Jeff Atwood talks about how to become better at designing and writing software by designing and writing a lot of software. His is stated more elegantly, but it is a valid point. The more you do something, the better you will get at it.

Hardware:

Any modern PC/Mac hardware should suffice. If you plan to run Windows or Linux I would use a PC over Mac. There is a lot of clamor over which is better, but use the one you like the best.

It should be a moot point in this day and age, but make sure you have some sort of reliable internet connectivity (cable, dsl, whatever...). Then you will have access to Google and stackoverflow; both good resources for programmers.

Make sure you have a keyboard and mouse which are comfortable to you. This includes setting up your desk and chair to accommodate your height and hand position. You will be at the computer for long stretches of time, and you want to be comfortable.

Editor/IDE:

Choose an editor: Vim, EMACS, KATE, Eclipse, whatever. It doesn't really matter which one, but whichever one you do pick learn it well. The editor is your main tool and you want to be comfortable and knowledgeable when using it. The better you know your editor the faster you can create/edit code.

It helps to have an editor that runs on all platforms you may be developing on, but it is not necessary.

Build Tools:

At some point you will find your self face to face with having to create or fix a build stystem. Make is pretty standard for *nix and C/C++, but for your own personal projects find the one that suits you best. There are a lot to choose from: Scons, Ant, Make, Jam, ...

I personally use SCons, since it is python based, and I like python.

Books:

When learning a new topic I would recommend getting a good book on it. This will generally give you a good overview of what you are getting into, and give you a good foundation to learn from. Google and Stackoverflow are good for specific questions, but a general overview of a topic is harder to get.

This of course assumes you have the luxury of time and money. For the monetarily constrained you can often find free versions of electronic books online.

Languages:

I used to have strong feelings about which languages to learn, but now I realize you should write in the language you enjoy most. However don't be afraid to try new languages. I personally like C++, python, and C# in no particular order.

Since you are just starting out pick the languages which you can get for free, which I actually think is most languages these days.

In the business world the language of choice tends to fluctuate on about a 5-7 year cycle. However you can find a job (at least currently) in all the "big" languages (C++, JAVA, C# VB.net, python, ruby, perl, ...). If you learn one of the modern languages well, it is typically not a problem to transition to another language quickly. The libraries tend to take longer to learn than the language itself. So pick a language you like learning in and learn it.

Miscellaneous Thoughts:

As Marc Charbonneau said set up source control. There are plenty of free source control offerings, so pick the one you like best. Personally I use Perforce, which is free for two or less people. I ahve heard good things about Subversion and git as well. The specific one is not as important, but choose one of them.

If you want to get a deeper knowledge of computing I would recommend Sipser's Book and Knuth.

Whichever language you choose I would spend time learning the debugger for it as well.

If you are doing web development, then make sure you know how to minimally setup and run Apachie (or IIS).

Avoid holy wars if you can. They are a waste of time, and you don't learn anything from it except that people are stubborn. Some Holy war topics (bracket style, editors, endianess, "best" language, "best" OS, ...).

My personal setup:

Standard PC (Windows XP Pro)

• Visual Studio 2007 (a little behind).
• VIM
• Python
• C/C++
• C#
• Scons

Standard PC (FreeBSD runs headless: no GUI)

• gnu tool chain (Make, C/C++ etc)
• VIM
• python
• Scons