Questions on Countability, Recognizability, and Decidability in Turing Machines

One-to-One functions in Turing Machines

• Notation: for any string W and any symbol x , we write #x (W )to represent the number of occur-rences of symbol x in W Examples: #0(")=0, #1(")=0, #0(0010)=3, #1(0010)=1, #0(111)=0
• In this assignment, if you need to prove something is recognizable or decidable, you should be us-ing ‘Turing machine pseudocode’ (as in Lectures 49 and after) instead of trying to draw a transitiondiagram.
• Recall the L notation as it relates to regular expressions: for any regular expression R, we write L(R)to represent the set of strings matched by the regular expression R.The assignment questions start on the next page.
1. Let function D : {0, 1}∗ →Zbe defined by D(W )=#1(W )−#0(W ).
(a)(2 pts) Is D one-to-one? Prove that your answer is correct.
(b)(2 pts) Is D onto? Prove that your answer is correct.
2. Let function C : {0, 1}∗ →{0, 1}∗ be defined by C (W )=1 ·W .
(a)(2 pts) Is C one-to-one? Prove that your answer is correct.
(b)(2 pts) Is C onto? Prove that your answer is correct.
(c)(3 pts) Let L ={0, 1}∗, that is, the set of all binary strings. Prove that L is a countable set.
3.(5 pts) Let S ={f | f : {0, 1}∗ → {0, 1}∗}. In other words, S is the set consisting of all functions whose domain and range are binary strings. Use the Diagonal Method to prove that S is uncountable.

(Drawing a table can be a useful visual tool, but your submitted solution should not contain one.) Side note: We can conclude from this result that, even if we were able to write out every possible Java program that takes in a binary string and outputs a binary string, there are still infinitely many such functions out there that we cannot implement. This is because the number of different Java programs is countably infinite, yet this question proves that the number of functions is uncountably infinite!
4.(8 pts) Prove: for all languages L, language L is decidable if and only if L ≤m L(000∗(11 +111))
5.(7 pts) Prove that the following language is decidable HighStepsTM ={W ∈{0, 1}∗ |W =?T ?and T is a TM that: no matter which input X ∈{0, 1}∗ is given, machine T takes at least 420 steps} Clarification: "takes 1 step" means "follows 1 transition"
6.(8 pts) Prove that EqualTM is unrecognizable by choosing an appropriate language L and proving that L ≤m EqualTM.

7.(10 pts) In this question, we’ll consider a new kind of Turing machine, that I call an "American Turing Ma-chine", or USTM. They are pretty much exactly the same as the Turing machines we’ve been using in this course (i.e., see Lectures 32-35), but with one difference: every state in the machine has a colour, Red or Blue.
Let L ={W ∈{0, 1}∗ |W =?T, c?where T is a USTM, c ∈{Red,Blue}, and:
there exists at least one binary input string X such that T executed on input X enters a state coloured c} Your task: Prove that L is undecidable.