CS 301, Spring 2012, Problem Set 7

Due Friday, March 9 (yes, just 2 days)

1. Construct a Turing Machine in full detail to decide the language: Note: The point of Turing machines is actually not to learn how to program a Turing machine. However, I think it is useful for understanding the model to program one Turing machine in detail once in your life. You may give either a state-transition table or a transition diagram.
2. Read the very short intro and Section I of Turing's paper that I posted to Piazza. Then, write a short answer to the following question: Would you say that Turing was more concerned about whether a man could simulate his machine with pencil and paper, or whether his machine could simulate a man? Briefly cite a few lines from the article supporting your answer.

-- Main.sloan - 2012-03-07