Let a decision problem X be defined as follows:

    X: Given a Turing machine M over Σ and nay word w ∈ Σ,
       does M loop forever on w? 

You may assume that the halting problem of Turing machine is undecidable but partially decidable.

(a) Show that X is undecidable.
(b) Show that X is not even partially decidable.

Consider the following problem X.

Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?

Which of the following statements about X is correct?

The aim of the following question is to prove that the language {M| M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M',x| M' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the 2 main steps in the construction of M. in part (c) describe the key property which relates the behaviour of M on its input w to the behaviour of M′ on x.

(a) On input w, what is the first step that M must make?
(b) On input w, based on the outcome of the first step, what is the second step that M must make?
(c) What key property relates the behaviour of M on w to the behaviour of M′ on x?

Define languages L₀ and L₁ as follows:

L0 = {〈M, w, 0〉 | M halts on w}
L1 = {〈M, w, 1〉 | M does not halts on w} 

Here 〈M, w, i〉 is a triplet, whose first component. M, is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit.

Let L = L₀∪L₁. Which of the following is true?

A single tape Turing Machine M has two states q₀ and q₁, of which q₀ is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

The table is interpreted as illustrated below. The entry (q₁, 1, R) in row q₀ and column 1 signifies that if M is in state q₀ and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q₁.

Which of the following statements is true about M?

(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a₁. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?