CS 301, Spring 2012, Problem Set 11

  1. Please read the article Computing Machinery and Intelligence, by Alan Turing, which appeared in Mind in 1950. You can find it in HTML at at http://cogprints.org/499/1/turing.html or http://www.abelard.org/turpap/turpap.php, and I will post a PDF of the actual journal article to our Piazza page. (I have the right to share that with UIC students but not the world.) There are some typos in the HTML versions that probably come from scanning, such as a prediction of a machine with 109 states that should be a prediction of a machine with 10 to the power 9 states. Please write 300–600 words in which you
    1. Summarize Turing's argument
    2. Discuss whether you think he gave a good test for an intelligent machine
    3. Discuss briefly the accuracy of his predictions for the general power of year 2000 machines
    4. Give your opinion on how close we are today to having computing machinery that is intelligent in the way that Turing defined it.
  2. Turing's paper gives hints about how we could model the combination of a computer plus its program as a DFA. Explain briefly what that model would look like, and why a Turing machine might be a better model.
  3. Prove that for any decidable language L other than the empty set or the set of all strings, it is always true that L \leq_m \bar{L} .
  4. For each of the following, tell us (1) whether Rice's Theorem applies, and (2) wheher the language is decidable. For parts 3 and 5, if the language is not decidable, tell also whether it is Turing-recognizable. If it is Turing-recognizable, briefly describe the Turing machine recognizing it. Otherwise, no justifications required.
    1. {<M> : M is a Turing machine accepting at least 37 odd length strings}
    2. {<M> : M is a Turing machine with |L(M)| = 37}
    3. {<M> : M is a Turing machine that accepts all strings that begin with the symbol 1}
    4. {<M> : M is a Turing machine that halts on input the empty string after at most 37 steps}
    5. {<M, w> : M is a Turng machine and M rejects w}
-- Main.sloan - 2012-04-09
Topic revision: r2 - 2012-04-13 - 13:32:03 - Main.sloan
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF