HN Books @HNBooksMonth

See Ullman's book [1] for more details on formal proofs.

Basically you can emulate the Turing machine's tape on the left side of the head with one stack and on the right side with the second stack.

An important question to now ask would be what happens if the tape in the machine has more than two directions; say for example it has a two-dimensional tape. The head may move left, right, but also up and down. It can be proven that such a machine would not be any more capable than the Turing machine with a 1D tape. Again see Ullman's book for details.

[1] http://www.amazon.com/Introduction-Automata-Theory-Languages...

Man, don't let people discourage you.

I guess the thing that you should realize though is that this isn't a degree in computer programming, or IT - it's a more or less a mathematics degree. As the saying goes, "Computer Science is no more about computers than astronomy is about telescopes."

If you want to get ready for serious computer science, I'd recommend a few things which are what I think I got out of my undergraduate degree:

1. A solid understanding of algorithms and data-structures. To this end, topcoder.com/tc is invaluable and some serious study will quickly bring you up to speed. CLRS (Introduction to Algorithms) is a great resource, as is train.usaco.org.

2. A basic understanding of theoretical computer science. To that end, I found this a really useful book: http://www.amazon.com/dp/0321455363

3. Basic understanding of networking and operating systems. Not sure the best route here, there must be online courses. Not too many great self-study books in this area, unfortunately. So find some online courses.

4. A decent math background: linear algebra, calculus, combinatorics, and probability. For self study:

    Calculus: Stewart's Calculus is great.

    Linear Algebra: I've yet to meet a linear algebra text I liked, so not sure here.

    Probability: A First Course in Probability is an outstanding textbook.

    Other: Concrete Mathematics by Knuth is an incredible book, very VERY hard and took me a long time to get through, but packed with useful and interesting information. I'd recommend it after the rest of these.

5. Read Snow Crash and watch Hackers.

Also, keep writing lots of code. Daily practice is the secret to everything.