CSC 463S Midterm Test February 26, 2020
Last Name First Name Student No. Instructions:
• Answer the questions in the spaces provided on the question sheets. Use the backs of sheets for rough work.
• No aids (notes, textbooks, electronic devices) are allowed.
• If you use results discussed in lecture, tutorial, or assignments in your
solutions to the questions, cite what you are using precisely.
• You have 50 minutes to complete the exam once time starts.
• Good luck on the test!
Total Marks: 3 questions worth 30 marks + 3 marks extra credit
1. (15 points) Determine whether the statements below are true or false. If true, provide a proof. If false, explain why the statement is false. Recall that a language L is non-trivial if L ̸= ∅ and L ̸= Σ∗.
(a) (5 points) For any non-trivial semi-decidable language A, there is a computable mapping reduction A ≤m A where A is the complement.
(b) (5 points) For any non-trivial decidable language B, there is a computable mapping reduction B ≤m B.
Page 2
(c) (5 points) If A is an infinite non-trivial decidable language, there is a subset B ⊆ A that is not decidable.
Page 3
2. (10 points) Consider the language
SEP = {⟨M1, M2⟩ : L(M1) = L(M2)}
consisting pairs of Turing machines ⟨M1 , M2 ⟩ where for every string x ∈ Σ∗ , exactly one of M1 or M2 accepts x. Is SEP semi-decidable? Prove your answer.
Page 4
3. (5 points) Recall the definition of the Kolmogorov complexity K(x) of a string and recall that the set of Kolmogorov-incompressible strings is defined as
I ={x∈{0,1}∗ :K(x)≥|x|}. (a) (5 points) Show that I is co-semidecidable.
(b) (3 points) EXTRA CREDIT (do only if you have finished all other problems!): Let A be a decid- able language where An = A ∩ {0, 1}n are its elements of length n. Suppose |An| ≤ 2εn for some 0 ≤ ε < 1. Show that A can have only finitely many incompressible strings (i.e. |A ∩ I| < ∞).
Page 5
This page may be used to continue solutions from previous pages in case there is no space. If you are finished writing all your solutions, you may use this space to draw a meme or otherwise write about your feelings about CSC 463.
Page 6