That’s the name of the book which I got today; and I feel this is one theory book which I might be able to read and understand at least a little bit. It goes into some deep issues (computability and complexity) without resorting to heavy-duty math and at the same time, not watering […]
Entries Tagged as 'CS Theory'
Algorithmics - the spirit of computing
April 1st, 2008 · No Comments
Tags: CS Theory · Mathematics
Simplest universal Turing machine proved!
October 25th, 2007 · No Comments
It seems bizarre that we should be able to achieve universal computation with a machine as simple as the one above–that we can find just by doing a little searching in the space of possible machines.
But that’s the new intuition that we get from NKS. That in the computational universe, phenomena like universality are […]
Tags: CS Theory
Teaching Theory of Computation
August 12th, 2006 · 2 Comments
TC (Theory of Computation) is an integral part of the CS curriculum - but most of it flies above the head of the average student. The reasons are: (a) the subject itself is hard and requires the students to have the ability to think deeply, (b) most of the prescribed text books have a […]
Tags: CS Theory · Favourite · Teaching CS
Factorial without recursion or iteration (or how TC can be fun)!
January 9th, 2006 · No Comments
TC = Theory of Computation
In the beginning, you thought you couldn’t do without iteration.
Then you realized that you can do away with iteration and do stuff recursively.
Then came the realization that what you call `iteration’ is just another form of `tail recursion’ (Lisp guys love to call it mere `syntactic sugar’)
The power of the […]
Tags: CS Theory · Favourite · Teaching CS