I am a graduate student taking a course in theory of computation and I have seri

Question

I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of Computation by Michael Sipser) and lectures; however when asked to prove something or come up with a formal description of a specific TM, I just choke. What can I do in such situations? I guess my issue is with fully comprehending abstract concepts to the point I can actually use them. Is there a structured way to approaching a new, abstract concept and eventually build intuition?

Explanation / Answer

I sometimes find out that people that doesn't do well in theory, just have the basics wrong (on the first 1-3 lectures, they thought the material is very easy, so they didn't pay too much attention, but then, at lecture 5-7 things speed up and it's too late to recap).

As @fbernardo said, it might be a good idea to start from the beginning. NOT as far as FLA (there is no use in that when studying TC, IMHO), but definitely open Sipser and start solving the questions one by one, by their order. With the experience you'll get intuition and basic tools that are imperative for more advanced concepts.

If you cannot cope with Sipser's basic questions of the first chapter (not the automata chapters, if you study on TMs), then you might be lacking even more fundamental concepts, such as basic proof methods (induction, etc.) or basic set-theory and discrete math.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.