HW#5 --- last modified March 02 2019 21:29:18..
Solution set.
Due date: May 15
Files to be submitted:
Hw5.tex
Purpose: To learn about many-one reducibility, to learn how to show a problem is
undecidable, to learn about decidability of logics, and to learn about Komolgorov complexity.
Do problems 5.4, 5.13, 5.21, 5.34, 6.13, 6.22 out of Sipser and write up your solution in LaTeX as Hw5.tex.
Specification:
Point Breakdown
LaTeX file compiles |
1pt
|
Problems from the book (1.5pts each) |
9pts
|
Total | 10pts |
|