Question

2. Let L-M M): M is a Turing machine that accepts at least two binary strings. a) Define the notions of a recognisable language and an undecidable language. [5 marks [5 marks] b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Prove that L is undecidable. (Hint: use Rice's theorem.) [20 marks] 20 marks] d) Bonus: Justify with a formal proof your answer to b).

Answer 1

a)When a turing machine is given an input , it can do three things.

i)Accept the input by reaching accept state.

ii)reject the input by reaching reject state.

iii)In a loop.

A language is known as turing recognizable if some language accepts it. A language of a turing machine is simply the set of

all strings that are accepted by the turing machine. In this case, we say that the language is recognized by the turing

machine.

Consider the set of strings that are not acceptable by language L. So machine M doesnot accept these strings.So when we

simulate a string , there are two chances.

1.M ends up on reject state.

2.M keeps computing forever(goes in a "loop").

Thus, we can say that for any input , the turing machine M decides whether to accept or reject the input in a

finite number of steps. The machine M is called a decider.

A Language is called turing Decidable if some turing machine decides it.

b) Here is what happens on input 0011100111

Initial state: 0001100011.

Mark the first unmarked zero: A0111A0111.

Mark the first unmarked one: A0B11A0B11.

Mark the first unmarked zero: AAB11AAB11.

Mark the first unmarked one: AABB1AABB1.

There are no unmarked zeroes but there is an unmarked one, so crash (reject) - Not recognizable.

d)Here is what happens on input 0001100011

Initial state: 0001100011.

Mark the first unmarked zero: A0011A0011.

Mark the first unmarked one: A00B1A00B1.

Mark the first unmarked zero: AA0B1AA0B1.

Mark the first unmarked one: AA0BBAA0BB.

Mark the first unmarked zero: AAABBAAABB.

Crash (reject) since there are no remaining unmarked ones.