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: \{ a^ n b^m : n \neq m \} 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

This topic: CS301 > WebHome > Syllabus > Homeworks > ProblemSet7
Topic revision: r1 - 2012-03-07 - 18:33:49 - Main.sloan
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF