Theory of Automata

...

Now, P’ will be the set for which Mi diverges. If we can say whether or not an integer x is a member of P then, we can also say if it is not a member of P by evaluating the Turing machine which doesn’t halt for all the inputs. Hence there is a Turning machine for P’ as well. Since P and P', both can be accepted by Turing machines, by corollary they are recursive. Hence P is a recursive set.

c) { i | Mi halts only for prime integers }

The given set is recursively enumerable because all the prime integers will be acceptable by the Turing machine. The complement of the set is the remaining integers which are also acceptable by the Turing machine. Hence it is recursive.

d) { i | Mi is not a Turing machine }

It is not recursive and recursively enumerable. The set given above is not recursively enumerable because any set should be computable by the Turing machine to be recursively enumerable. It is given Mi is not a Turing machine. No machine can determine the divergence of another machine. Hence, such a machine cannot be constructed.

Problem_8: Page 120: #3;

Show that the following sets are not recursively enumerable.

a) { i | Wi = Ø }

b) { i | Wi = all integers }

a) { i | Wi = Ø }

The above set represents the indices of the empty set. Since it is an empty set, the Turing machine for this set as input will always diverge. So it is not recursively enumerable.

b) { i | Wi = all integers }

The given set represents the indices of all integers. We know that any Turing machine will accept all integers as input. If this set is to be recursively enumerable, then there should be a Turing machine which halts on taking indices which consist of all integers in their set, as input and diverges on all other indices. So according to the theorem, this set is acceptable by Turing machine so it is recursively enumerable.

PROBLEM_9

Read chapter 16 from the Book "COMPUTING: A Historical and Technical Perspective" and write a one-page essay on "what is computation?

Computability is the ability to solve a problem effectively. The problem is divided into two types, according to Hilbert any formal mathematical theory there must exist an algorithm by which its provability could be decided. This is called as decision problem and Function problems are those in which we find a mapping from an element in one set to another element in the other set. An Algorithm can be defined as an effective procedure for computing a function. The Hilbert theorem is also related to several results which are related to undecidable problems in recursion theory. In order to compute these problems, we need a model of computation, and with the help of Turing machine we can perform computation easily, this is because it is simple, it can be analyzed and used to prove the results. The Computability theory is concerned with the question of the extent to which a problem is solvable on a computer. The Computational complexity theory decides whether a problem can be solved at all on a computer, as well as efficiency is taken into consideration.

The two main aspects come into picture i.e. time complexity and space complexity. Time complexity is nothing but the number of steps it takes to perform a computation, and Space complexity is how much memory is being used. Turing machine can be constructed easily. It consists of an arbitrarily long tape and a finite state control. The tape is divided into a number of squares on which symbols can be read and written. The movement of the head and the read-write operations would be defined by the instructions set in the finite state control. By using either NICE language or Small programming language along with Turing machine computation can be perform [pic 7] ed easily.