HW#1 --- last modified February 10 2019 21:57:00..
Solution set.
Due date: Sep 12
Files to be submitted:
Hw1.pdf
Purpose: To refresh our memories with regard to TM, analysing algorithms, and proofs.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO1 -- Exhibit a simulation of one machine model with another.
Specification:
Do the following problems out of A & B: 1.1, 1.5, 1.10, 1.11.
In addition to these book questions, show the problem of determining whether the second work tape of a TM ever has the string 0110 on it during
the course of its computation is undecidable. Please put all your answers to the homework problems in a pdf file Hw1.pdf. Try to make the math equations you write you readable by using a tool like LaTeX.
On the day your homework is due I will ask each group to present one problem on the board.
Point Breakdown
| Five problems above (1.5 pts each - 1.5pts, completely correct; 1pt, missing minor details, 0.5pt, on the right track; 0 confused or wrong. |
7.5pts
|
| Class presentation (Write-up clear, 1.5pts; all group members could answer brief questions about the problem intelligently, 1pt). |
2.5pts
|
| Total | 10pts |
|