Computer Science 4602, Fall 2016
Assignment 5
Assigned: |
Thursday, October 20 |
Due: |
Tuesday, October 25 at the beginning of class |
Exercises are from Sipser, third edition, beginning
on page 187 for Chapter 3 and page 210 for Chapter 4.
- 3.15(d,e)
- 3.22
- Prove that every finite language is Turing-decidable (computable).
- Are all infinite languages uncomputable? Explain why or why not.
- 4.3
- 4.30
(Hint: Write a program that takes integer inputs (so its
input alphabet consists of decimal digits). On
input i, it finds Mi and runs it on input i. What can
your program do to ensure that your program does not compute the same
language as Mi?