Theory of Automata

Problem_1: Page 115: #2;

Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from the standard enumeration on its tape.

A={ 1,2,3,……….n}

f(x) = [pic 1]

Let’s take the example of input 14, it can be expressed as 1110. Turing machine reads the binary string, Search for a binary string in the range of set A. If string matches, then the output is 1 and the Turing machine halts. If there is no match, then the Turing machine diverges.

Problem_2: Page 115: #5;

As we know from our study of computability, programs can be translated into Turing machines. If we check off these Turing machines (those which are transformed programs), we find that there are still some left over in our standard enumeration. Does this mean that there are more Turing machines than programs? Comment.

We cannot compute whether the Turing machine is more than programs. The number of Turing machines will be equal to the number of programs and each Turing machine will have a unique code. But given that if there are some leftover Turing machines in our standard enumeration it is because if the order of instructions changes then the machines used will also change.

Suppose, let's consider two or more machines with same instructions but with some of the instruction lines in a different order then the machines will not be the same.

Problem_3: Page 116: #6;

Some infinite sequences of zeros and ones (such as 1010101... or 1101001000...) are not too difficult to compute. In fact, we could design Turing machines which compute them. Are there any binary sequences which cannot be computed by Turing machines? Why?

According to Theorem 3: There are sets that cannot be computable. Some binary sequence cannot occur anywhere in the list of sequences and it is not computable by Turing machine. Hence proved that there exists a binary sequence which is not executable by the Turing machine.

Problem_4: Page 117: #2;

Might the following be a Turing machine? Explain your reasoning.

[pic 2]

Yes, it is a Turing machine. Turing machine takes inputs and it halts If the given input is computable and it diverges if it is not computable.

Consider a set of languages A= {1,2, 3, ….. , n}  

Now assume that the machine Mi(n) halts for the input 12 that is Mi (12). We can say that it is a Turing machine if and only if it halts for some inputs which are recognizable and acceptable and diverges for all other inputs. We know that every program will have its own Turing machine. So here in this case, if the machine halts for the input 12 then we can say it is a Turing machine.

Problem_5: Page 117: #4;

We showed that since the problem concerning a machine halting on its own index is unsolvable, the general halting problem for Turing machines is unsolvable. Does this imply that any superset of an unsolvable problem is unsolvable? Provide a proof or a counterexample.

We already know that the machine halting on its own index is unsolvable. This implies that any superset of an unsolvable problem is also unsolvable. To prove this let’s consider a superset of an unsolvable problem as unsolvable.

                                                                                                                                        superset[pic 3][pic 4]

                                                                                                                                                                                                                Subset {1,2,…..,k}[pic 5][pic 6]

For example, if we consider the subset of this superset and if we compute this set on some machine M, at some point for the input ‘k’ the machine halts which is unsolvable. But for the other subsets, it may be solvable. So, by this, we can say that the superset of an unsolvable problem may or may not be solvable.

Problem_6: Page 118: #7;

Prove that the membership problem for any finite set is solvable.

To prove the halting problem for any finite set is solvable, we consider a finite set   A= {1,2,3} then, suppose if we consider the Turing machine M1 and it ran with its own index as input i.e., we examined the computation of M1(1). In this case, we know the answer because we remember that M1 was merely the machine:

and we know that it will only halt when it receives an input that begins with a zero. We could look at that also M2(2). Then we could go on to M3(3). So, this shows that the membership problem for any finite set is solvable.

Problem_7: Page 119: #1;

Are the following sets recursive? Are they recursively enumerable? Justify your conjectures.

a) { x | x is an even integer }

b) { i | Mi halts for all inputs }

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

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

a) {x | x is an even integer}

Yes, it is recursively enumerable

This set is recursive enumerable because we can design a Turing machine which accepts a set of even integers. We know that a set is recursive if and only if both the set and its complement are recursively enumerable.  

So consider,  A = { x | x is an even integer}  A’= { x | x is an odd integer} According to the theorem if a Turing machine exists which accepts the set, then the set is recursively enumerable. Here the Turing machine can be designed for both A and A’. So they are recursively enumerable.

b) { i | Mi halts for all inputs }

Let this set be P. Since Mi is a Turning machine, it can be implied that the given set is acceptable and hence the set P is recursively enumerable. If Mi halts for all the inputs then it is one of the enumerated Turing machines.