Question

Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA with a FIFO queue is Turing universal (i.e equivalent in computational power to a Turing machine). You should regard this machine as being formally defined in a way that is very similar to a PDA, except that on each transition, instead of pushing and/or popping a character, the machine may remove an element from the head and/or insert an element at the tail of the queue. (Must be explained clearly) 1101 In the following problems, A and B denote arbitrary languages. b. Prove that if both A and B are Turing-recognisable, then An B is also Turing- recognisable 151 c. Prove that if A is Turing-recognisable and B is decidable then A-B is also Turing recognisable. 151

Subject : Theory of Computation
Please answer , posting second time now cause nobody answered it previously

Answer 1

Dear student, I have uploaded the answer of b. only as I was not 100% sure for the correct answer of c. So I have uploaded b. thinking that if minimum is better than zero.

CAR actepts4 ujeds cxep