Posts | Theory of Computation

Class 18: Review for Exam 2

4 November 2019 by David Evans

Exam 2 Practice Problems
Exam 2 Preparation

Practice Problems for Exam 2

2 November 2019 by David Evans and Nathan Brunelle

By popular request, here are some practice problems for preparing to Exam 2: [PDF]

We won’t be providing written solutions to these problems, but are happy to answer questions about them (including during office hours). If you would like any particular problems to be included in the review class (Monday), let us know.

PS4 Grades Posted

2 November 2019 by David Evans and Nathan Brunelle

The grades for PS4 are now posted in Assignments on Collab. You will find your grades, comments, and an attached pdf of solutions with PS2 assignment Our grading policy for PS4 was the same as for PS1, PS2, and PS3, but we reserve the right to change this policy for future assignments. To calculate your grade we first computed the following: five_count = the count of problems for which you earned a 5 or above sum = the sum of the scores earned on all problems non_star_count = the number of non-starred problems in the assignent score_by_fives = five_count / non_star_count score_by_average = sum / non_star_count That policy was:

Preparing for Exam 2

1 November 2019 by David Evans and Nathan Brunelle

Exam 2 will be Wednesday, 6 November at the normal class time in the normal classroom. We will aim to start the exam right at 3:30pm, so you will benefit from arriving early for class Wednesday to be settled and ready to start the exam. Exam 2 will cover material from Classes 1-16 (through 28 October) (so the new material introduced on Rice’s Theorem in Class 17 is not covered in this exam), Problem Sets 1-6 (comments for PS4 and PS5 are now available in collab, sorry it has taken so long to get the grading done for these, but you can see our solutions and comments in collab now; we will post comments for Problem Set 6 on Sunday afternoon), and the textbook chapters 0-6 and parts of 8 (8.

Class 17: Rice's Theorem

31 October 2019 by Nathan Brunelle

Slides
Video

TCS Chapter 8: Universaility and Uncomputability

Class 16: Reductions

28 October 2019 by Nathan Brunelle

Slides
Video

TCS Chapter 8: Universaility and Uncomputability

Problem Set 6

26 October 2019 by David Evans and Nathan Brunelle

Problem Set 6: Dodge Duck Dip Dive Decide

Problem Set 6 is available here: ps6.pdf (you will also need the ps6.zip file). It is due on Friday, 1 November at 4:19pm.

These is no Jupyter part for PS6, so your submission can be just one ps6.pdf file.

This assignment covers Turing Machines from Chapter 6, and undecidability (including the halting problem, reductions, and Rice’s theorem) from Chapter 8.

Class 15: Universality and Uncomputability

23 October 2019 by David Evans

Slides Video TCS Chapter 8: Universaility and Uncomputability Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. 1936. (bug fix) (You missed your chance to by an original printing for GBP 30,000.) According to Scott Aaronson, Dori-Mic and the Universal Machine! A Tragicomic Tale of Combinatorics and Computability for Curious Children of All Ages is “The BEST babies’ book about computational universality I’ve read.". I have free copies available for anyone who needs a holiday present for a young sibling/cousin/nibling/other person who is behind in her theoretical computer science education and needs a holiday present for any cs3102 students who ask.

Problem Set 5 Update

23 October 2019 by David Evans and Nathan Brunelle

Two more updates to PS5: Problem 7 considered adding an array but not loops to NAND-CIRC. But, it doesn’t make sense to have arrays without any way to update the index used to access them. So, for this to make sense we need to also have an instruction to update i. So, we have modified this question to add conditional increment and decrement instructions: CINC v takes a regular variable as its input, and if the value of v is 1 it updates the value of i to be i + 1.

Problem Set 5 Update

22 October 2019 by David Evans

There were several mistakes in PS5, Problem 1, which are now corrected (updated ps5.pdf, ps5.zip). Problem 1a should be: Prove that when $f^*(i) = 0$, $f_{i+1} = f_i$. That is, the two functions denoted by $f_{i + 1}$ and $f_i$ are actually the same function. Thanks to Joey Rudek for noticing the problem! Problems 6 and 7 mixed up NAND-CIRC and NAND-TM. Problem 6 should be asking if NAND-LOOP is more powerful than NAND-CIRC (it would be silly to ask if it is more powerful than NAND-TM, since NAND-TM has everything in NAND-LOOP plus arrays, so there’s no way NAND-LOOP could be more powerful than NAND-TM).

All Posts by Category or Tags.