Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 376: Foundations of Computer Science

Winter 2024

Homework 6

Due 8:00pm, February 22

(0 pts) 0. Before you start; before you submit.

If applicable, state the name(s) and uniqname(s) of your collaborator(s).

(10 pts) 1. Self assessment.

Carefully read and understand the posted solutions to the previous homework; you may also find the video “walkthroughs” on Canvas helpful. Identify one part for which your own solution has the most room for improvement (e.g., has unsound reasoning, doesn’t show what was required, could be significantly clearer or better organized, etc.). Copy or screenshot this solution, then in a few sentences, explain what was deficient and how it could be fixed.

(Alternatively, if you think one of your solutions is significantly better than the posted one, copy it here and explain why you think it is better.)

If you didn’t turn in the previous homework, then (1) state that you didn’t turn it in, and (2) pick a problem that you think is particularly challenging from the previous homework and explain the answer in your own words. You may reference the answer key, but your answer is to be in your own words.

2. A powerful diagonalization.

Use diagonalization to prove that for any countably infinite set A, the power set P(A) is uncountably infinite.

Hint: View each subset as an infinite binary sequence representing whether each element of A is included in the subset or not.

(6 pts) (b) Prove that any infinite language L ⊆ Σ* has an undecidable subset L′ ⊆ L.

Hint: Part (a) will be useful.

3. Turing machines.

(7 pts) (a) Go to https://turingmachine.io/ and step through the example code that adds 1 to an input integer (represented as a binary string). Modify this machine to add 2 instead of 1 (scroll down on the page for instructions on how to write the code). Give a picture or screenshot of your new machine as your solution. You do not need to provide justification.

(8 pts) (b) Let L be the language of all binary strings that represent non-negative integers that are divisible by 4:

L = {⟨s⟩ : s mod 4 = 0} ∪ {ε}.

Note that leading zeroes in the representation are acceptable, i.e., 000101010 and 101010 both represent 42. Also, we define ε to represent 0.

Draw a state-machine diagram for a Turing machine that decides L. This drawing can be done however you like (hand-drawn, using https://turingmachine.io/, drawn in latex, etc.), as long as it is readable. No justification is necessary.

Hint: How is the last bit of the binary representation of an integer related to whether the integer is divisible by 2? Can you extend this observation to divisibility by 4?

4. Decidability.

Note: A \ B := {x ∈ A : x /∈ B} denotes the set difference between A and B.

5. Haltchecker. (Warning: This problem is related to material from the lecture on 2/19.)

(8 pts) (a) Recall from lecture the definition LHALT := {(⟨M⟩, x) : M halts on input x}. In class you saw a Turing reduction from LACC to LHALT, proving that LHALT is undecidable. This linked video describes a different argument that LHALT is undecidable, without using a reduction.

Formalize the argument in the video as a rigorous proof.

(7 pts) (b) Consider the following language:

LHALT<2|x| = {(⟨M⟩, x) : M(x) halts within 2|x| steps} .

Prove or disprove: LHALT<2|x| is decidable.

6. Turing reductions. (Warning: This problem relies on material from the lecture on 2/19.) Before embarking on this problem, read Handout 2: Turing Reductions.

(7 pts) (a) Prove or disprove: if L ≤T L ′ for some language L ′ , then L is decidable.

(5 EC pts) 7. Optional extra credit: An interesting language.

Recall that a language L is recognizable if there is a Turing machine that accepts every string in L, and either rejects or loops on every string not in L.

Prove that there exists a language L where neither L nor its complement L is recognizable.