For a string s ∈ {0, 1} let denote the number represented by in the binary * s2 s numeral system. For example 1110 in binary has
a value of 14 . Consider the language: L = {u#w | u,w ∈ {0, 1} , u } , * 2 + 1 = w2 meaning it contains all strings u#w such that u + 1 = w holds true in the binary system. For example, 1010#1011 ∈ L and 0011#100 ∈ L . Construct a TM that decides this language.
