HW#5 --- last modified May 04 2020 21:10:02.

Solution set.

Due date: May 11

Files to be submitted:
  Hw5.zip

Purpose: To learn more about reductions, completeness, and undecidability.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO10 -- State in precise mathematical terms what is meant by undecidability of the Halting Problem, and be able to show the undecidability of simple extensions of the Halting Problem, using the reduction technique.

Description:

This homework consists of the exercises below. Your work for all portions of this assignment should be submitted in the file Hw5.zip. Within this file, you should have a readme.txt listing each team mate. You should put the exercise solutions in the file Hw5.pdf.

1. Let a `k`-O Turing Machine be an offline Turing Machine (input tape is read-only) with a {0, 1, `\square`} tape alphabet which when it tries to write a 0 into a tape square writes with probability 0.5 a 0 and with probability 0.5 writes instead `k` 0's in the direction of motion with its tape head ending up moving k+1 squares in that direction. (a) Show how a `k`-O Turing Machine can simulate a usual Turing Machine over a {0, 1, `\square`} tape alphabet. Say a `k`-O Turing Machine `M` decides a language `L` if whenever `x in L` the machine on `x` accepts and whenever `x !in L` the machine `M` on `x` rejects. (b) Show if `L` can be decided by a `k`-O Turing Machine it can be decided by a regular Turing Machine.
2. (a) Give a RAM program which when on input two nonnegative integers `n, m` computes integers `q` and `r` such that `n = q \cdot m+r` where `0 leq r < m` and halts with `q` in its accumulator. Show how the TM simulation of this RAM behaves on inputs `14, 3`.
3. Carefully prove the following relaxed version of the space hierarchy theorem: If `f(n)` is a proper function, then `SPACE(f(n))` is a proper subset of `SPACE([f(n)]^3)`.
4. A `t`-write Turing Machine is a Turing Machine which can at most write a tape square `t` times before that square gets permanently changed to the symbol used the last time it was written. Let `t`- write LBA be the class of languages recognized by `t`-write TMs that are restricted so that the tape head isn't permitted to move off the portion of the tape containing the input. Determine, with proof, the values of `t` for which emptiness testing for `t`- write LBA is decidable and the values for which it is not decidable.
5. Let Never154 be the class of languages that have never been mentioned in any instance of a CS154 class. Prove the language `{ langle M rangle | L(M) in N\e\v\e\r154}` is undecidable.