Saturday 26 January 2013

useful Links ppts and books

Have a look at below links :

Software Engineering 

Unit I

Unit II

Unit III
Unit IV
Unit V

Pressman Download link
http://rapidshare.com/files/249795254/SoftwareEngineering-Pressman.pdf

Jalote Download link
http://199.91.154.98/tn01yv351d4g/gru947t4hvbudxw/An+Integrated+Approach+to+Software+Engineering+3rd+Edition+by+Pankaj+Jalote.pdf


DISCRETE MATHEMATICS
valid arguments Proof methods
proof methods
methods of proofs
MCQ's
mathematical induction
graph theory basics
Functions
distance_centre_diameter
connectivity in graphs
complexity of graph searching
closure of relations

Discrete Mathematics e-boook by Kenneth H Rosen Part1 Part2 Part3 Part4 Part5
Download all parts and then extract part1.

PROGRAMMING LANGUAGES
Introduction
Unit II
Unit III
Unit IV
Subprogram Control
Efficiency and Regularity

Advance Operating System


quiz3.doc Download

quiz4.doc Download





unit3ans.doc Download



unit5ans.doc Download





UNIT5_MPS.ppt Download


Theory of Computation

closure properties.rtf Download

new mcqs.doc Download

purva.rar Download

TOC for STUDENTS.rar Download

toc mcq.doc Download    

 

Computer Networks

ch26.ppt View Download
Chap-23.ppt View Download
Chapter 22 Transport Layer.ppt View Download
chapter3a.ppt View Download
Chapter5 (Subnetting and Supernetting).ppt View Download
Chapter6TransportLayer-1.ppt View Download
Copy of tcp.ppt View Download
Lecture18.ppt View Download
      

 

Distributed Systems

Unit 1 Tutorial.doc View Download

Unit 2 Tutorial.doc View Download

Unit 3.doc View Download

Unit 4.doc View Download

Unit 5.doc View Download

MCQs.doc View Download    

 

Mobile Computing

APPLICATIONSOFMOBILECOMPUTING.doc View Download

ute 3,4 and 5 units.docx View Download 

tutesheet2mc.doc View Download

unit2 tute.docx View Download

mc-1stunit.rar View Download

 

Data Compression

Data Compression Crossword.pdf View Download

TSheetV.doc View Download

Unit III MCQ.doc View Download

Unit III TS.doc View Download

Unit IV MCQ.doc View Download

Unit IV TS.doc View Download     

 

 

 


TOC Chapter 14

Chapter 14. New Models of Computation

 

14.1. DNA Computing

Mathematical biology is a highly interdisciplinary area of research that lies at the intersection of mathematics and biology. So far, in this area, mathematical results have been used to solve biological problems. The development of stochastic processes and statistical methods are examples of such a development. In contrast, an instance of the directed Hamilton path problem was solved solely by manipulating DNA strings by Leonard Adleman. Hence, one can see that biological technique is used to solve a mathematical problem, thus paving way for a new line of research ‘DNA computing.’ The resemblance between mathematics and biology is that in both, simple operations are applied to initial information to obtain a result. Hence, the use of biology to solve a mathematical problem was demonstrated by a mathematician with adequate knowledge in biology, to bring together these two fields. Adleman thought that DNA strings can be used to encode an information while enzymes can be employed to simulate simple computations.
Molecules that play central roles in molecular biology and genetics, are DNA, RNA, and the polypeptides. The recombinant behaviors of double-stranded DNA molecules is made possible by the presence of restricted enzymes. Hence, DNA computing is a fast-growing research area concerned with the use of DNA molecules for the implementation of computational processes.

14.2. Membrane Computing

Membrane computing is a new computability technique which is inspired from biochemistry. The model used for any computation here resembles a membrane structure and it is a highly parallel, distributed computing model. Several cell-like membranes are recurrently placed inside a unique membrane called “skin” membrane. The structure of this model may be placed as a Venn diagram without intersected sets and with unique superset. Hence, the structure or compartment of the computing model can be diagrammatically represented as below:


TOC Chapter 13

Chapter 13. Recent Trends and Applications

13.1. Regulated Re-writing

In a given grammar, re-writing can take place at a step of a derivation by the usage of any applicable rule in any desired place. That is, if A is a nonterminal occurring in any sentential form say αAβ, the rules being Aγ, Aδ, then any of these two rules are applicable for the occurrence of A in αAβ. Hence, one encounters nondeterminism in its application. One way of naturally restricting the nondeterminism is by regulating devices, which can select only certain derivations as correct in such a way that the obtained language has certain useful properties. For example, a very simple and natural control on regular rules may yield a non-regular language.
While defining the four types of grammars in Chapter 2, we put restrictions in the form of production rules to go from type 0 to type 1, then to type 2 and type 3. In this chapter, we put restrictions on the manner of applying the rules and study the effect. There are several methods to control re-writing. Some of the standard control strategies will be discussed below.

13.2. Marcus Contextual Grammars

Marcus defined the contextual grammars in 1969. The implicit motivation for these new generative devices were in the concepts of descriptive linguistics. S. Marcus introduced first what are known as ‘external contextual grammars (ECG)’ and other variants like ‘internal contextual grammars (ICG)’; total contextual grammars were developed later. The power of contextual grammars is compared with Chomskian grammars, and some other grammars (Păun, 1997). The research on this branch of formal language theory is well developed now.
In a CFG, rules are always of the form Aα. One understands that the application of the rules to any word containing A does not depend on the context. That is, any word of the form w1 Aw2 will yield w1αw2 on application of Aα once, whereas a CFG will contain rules of the form w1Aw2w1 αw2, which are understood to be sensitive to the contexts w1 and w2. That is, one cannot apply this rule to any word containing A as in the case of context-free rule. Thus, in the above-said Chomskian models of re-writing, contexts may or may not play a role for re-writing.

13.3. Lindenmayer Systems

L-systems were defined by Lindenmayer in an attempt to describe the development of multi-cellular organisms. In the study of developmental biology, the important changes that take place in cells and tissues during development are considered. L-systems provide a framework within which these aspects of development can be expressed in a formal manner. L-systems also provide a way to generate interesting classes of pictures by generating strings and interpreting the symbols of the string as the moves of a cursor.
From the formal language theory point of view, L-systems differ from the Chomsky grammars in the following three ways:

13.4. Grammar Systems and Distributed Automata

With the need to solve different problems within a short-time in an efficient manner, parallel and distributed computing have become essential. Study of such computations in the abstract sense, from the formal-language theory point of view, started with the development of grammar systems. In classical formal-language theory, a language is generated by a single grammar or accepted by a single automaton. They model a single processor or we can say the devices are centralized. Though multi-tape Turing machines (TMs) try to introduce parallelism in a small way, the finite control of the machine is only one. The introduction of distributed computing useful in analyzing computation in computer networks, distributed databases etc., has led to the notions such as distributed parallelism, concurrency, and communication. The theory of grammar systems and the distributed automata are formal models for distributed computing, where these notions could be formally defined and analyzed.

Grammar Systems

A grammar system is a set of grammars working in unison, according to a specified protocol, to generate one language. These are studied to model distribution, to increase the generative power, to decrease the complexity etc. The study of grammar systems probes into the functioning of such system under specific protocols and the influence of various protocols on various properties of the system are considered.




TOC Chapter 12

Chapter 12. Time and Space Complexity

In the earlier chapters, we considered the Turing machine (TM) and its acceptance power. By Church–Turing hypothesis, we realize that whatever could be done by a computer can be achieved by a TM. Also, while considering the variations of TMs, we found that even though all of them have the same accepting power, the number of steps could be very much increased in some cases. We also noted earlier that a procedure corresponds to a TM and an algorithm corresponds to a TM, which halts on all inputs. When we study algorithms for problems, we are also interested in finding efficient algorithms. Hence, it becomes essential to study the time and tape (space) complexity of TMs. In this chapter, we study some of these results.

12.1. The RAM Model

The standard model of computation which will represent the action of a modern computer is the family of random access machines (RAM). They are also referred to as register machines sometimes. There are several variations of this model. We consider the following model. It consists of a central processor and an unbounded number of registers. The processor carries out instructions from a given limited set on these registers. Each register can store an arbitrarily large integer. The program is not stored in these registers. It immediately follows that a RAM program cannot modify itself. In this way, it is different from the stored program concept. Also, at any time, the RAM program can refer to only a fixed number of registers, even though it has unbounded number of registers. When the machine starts, the input data is stored in a few registers. When it stops, the result of the computation is stored in a few registers. Let us consider the simplest RAM model which uses only four instructions, viz, increment, decrement, jump on zero, and halt. To add two numbers stored in R1 and R2 and store the result in R1, the following program can be executed.
loop:Jump on zero, R2, done
Decrement R2
Increment R1
done: Halt.

12.2. Time and Tape Complexity of Turing Machines

Space Complexity

Consider the offline TM M. It has a read-only input tape and the input is placed within end markers # and $. It has k storage tapes infinite in one direction. If for every input word of length n, M scans at most S(n) cells on any storage tape, then M is said to be an S(n) space bounded TM, or of space complexity S(n). The language recognized by M, is also said to be of space complexity S(n). It should be noted that symbols on the input tape cannot be rewritten and only the cells used in storage tapes count towards space complexity. This way of looking at the TM helps to consider space bounds less than O(n). For example, log n. If the symbols on the input tape can be written, then minimum space complexity will be n, as we need to look at whole of the input.
Figure 12.1. Multi-tape TM with read only input tape

Problems and Solutions

1.Show that DT(22n+2n) properly includes DT(22n).
Solution.

By result 2 mentioned in “Some Results on Complexity Classes,” DT(22n+2n) properly includes DT(22n).
2.What is the relationship between:
  1. DS(n2) and DS(n3)?
  2. DT(2n) and DT(3n)?
  3. NS(2n) and DS(5n)?
Solution.
a.
By result 1 mentioned in “Some Results on Complexity Classes,” DS(n3) properly includes DS(n2).
b.
By result 2 DT(2n) is properly included in DT(3n).
c.(c) NS(2n) is included in DS((2n)2) = DS(4n) (result 4) DS(4n) is properly included in DS(5n) (result 1) Therefore, NS(2n) is properly included in DS(5n).
3.Show that the following problem is NP-complete. One-in-Three-3SAT (1in3SAT) has the same description as 3SAT, except that a satisfying truth assignment must set exactly one literal to true in each clause.
Solution.One-in-Three-3SAT (1in3SAT)
Is the given Boolean expression, given in 3SAT, satisfiable with the additional condition that the truth assignment must set exactly one literal to true in each clause.
1in3SAT is in NP, as we can non-deterministically give a truth assignment and evaluate the expression and also check the additional condition on truth assignment in polynomial time.
We next reduce 3SAT to 1in3SAT. Let w0 be a Boolean expression in 3SAT form. From this, construct a Boolean expression for the 1in3SAT problem as follows. To each clause
Equation 12.6

of w0 introduce new variables a, b, c, d and convert this to:
Equation 12.7

If Equation (12.6) is not satisfiable x1 = x2 = x3 = 0. In this case, looking at Equation (12.7) as lin3SAT problem . Hence, a = b = c = d = 0. Since x2 = 0. (b + x2 + c) becomes 0. Equation (12.7) is not satisfiable or in otherwords, if Equation (12.7) is satisfiable, Equation (12.6) is satisfiable.
To prove the other way round, let Equation (12.6) be satisfiable.
If x2 = 1, then make b = 0 = c, a = x1, d = x3.
Then, Equation (12.7) satisfies the additional restriction and is satisfiable.
If x2 = 0, then if x1 = x3 = 1 make a = 1, b = 0, c = 1, d = 0.
If x1 = 1, x2 = 0, x3 = 0 make a = 0, b = 1, c = 0, d = 0.
If x1 = 0, x2 = 0, x3 = 1 make a = 0, b = 0, c = 1, d = 0.
In all cases if Equation (12.6) is satisfiable Equation (12.7) is satisfiable.
If w0 has k clauses and n variables, has 3k clauses and n + 4k variables. w0 can be converted to ’ in polynomial time.
Hence, the known NP-complete problem 3SAT is polynomial-time reducible to 1in3SAT problem. Hence, 1in3SAT is NP-complete.
4.Positive 1in3SAT problem is the 1in3SAT problem, where none of the literals are negated. Show that it is NP-complete.
Solution.Positive 3SAT problem is: Given a Boolean expression in 3SAT form, where none of the literals are negated, is the expression satisfiable?
This is a trivial problem as the assignment giving values 1 to all the variables makes the expression satisfiable.
It is straightforward to see that positive 1in3SAT problem is in NP. It can be shown to be NP-complete by reducing the 1in3SAT problem to it.
Let w0 = c1... ck be a Boolean expression in 3SAT form. From this, we construct an expression w in 3SAT form where none of the literals are negated such that w0 is satisfiable with the 1in3 condition if and only if w is satisfiable with the 1in3 condition.
Also, given w0, w can be constructed in polynomial time.
Let x1, ..., xn be the variables used in w0. There are k clauses in w0. In w, we use variables x1, ..., xn and also variables y1, ..., yn and z1, ..., zk, z1, ..., zk, z1, ..., zk.
We shall now give the method of constructing w from w0.
For each clause ci in w0 some clauses ci are constructed.
  1. If ci is of the form (xk + xl + xm) with no literal negated, this is kept as it is in ci
  2. If ci is of the form (¬xk + xl + xm) with one literal negated, ci consists of (yk + xl + xm)(yk + xk + zi)(x1 + zi + zi)(xm + zi + zi) (yk in essence refers to ¬ xk). If (¬xk + xl + xm) is satisfiable with the 1in3 condition, then ci is satisfiable with the 1in3 condition and vice versa. It should be noted that one of yk or xk will be 0 and the other 1 and zi has to be 0. The values of zi, zi can be properly chosen to satisfy the 1in3 condition.
  3. If ci is of the form (¬xk + ¬xl + xm) with two of the literals negated, ci consists of (yk + yl + xm)(yk + xk + zi)(yl + xl + zi)(xm + zi + zi).
    Again, it can be checked that if ci is satisfiable with the 1in3 condition then ci is satisfiable with the 1in3 condition and vice versa. Note that one of yk, xk is 0 and the other 1 as also one of yl, xl is 0 and the other 1 and zi = 0. zi assumes suitable value to satisfy the 1in3 condition.
  4. If ci is of the form (¬xkxlxm) will all three literals negated, ci consists of (yk + yl + ym)(yk + xk + zi)(yl + xl + zi)(ym + xm + zi). Again, it can be checked that if ci is satisfiable with the 1in3 condition ci is satisfiable with the 1in3 condition and vice versa. Also zi = 0 and one of yj, xj(j = k, l, m) is 0 and the other 1, and it is straightforward to see that w′ can be constructed from w0 in polynomial time. Hence, positive 1in3SAT is NP-complete.
5.Exact cover by three-sets (X3C): Given a set with 3n elements for some natural number n and a collection of subsets of the set, each of which contains exactly three elements, do there exist in the collection n subsets that together cover the set?
Show that this problem is NP-complete.
Solution.Membership in NP is obvious. Select a set of n three-sets and check whether they cover the given set. To show X3C is NP-complete, we reduce positive 1in3SAT to it. Let us consider an instance of positive 1in3SAT with n variables and k clauses. This instance of positive 1in3SAT will be converted to a X3C instance with 18k elements and 15k three-sets such that positive 1in3SAT instance is satisfiable if and only if the X3C instance has a ‘yes’ answer. i.e., an exact cover with n three-sets is present.
For each clause c = (x + y + z) we set up six elements xc, yc, zc, tc, fc, fc. The first three will represent the three literals, while the other three will distinguish the true literal from the two false literals. For each variable, we construct a component with two attaching points (one corresponding to true and the other to false) for each of its occurrences. See Figure 12.2.
Figure 12.2. x is the variable occuring 4 times

Let variable x occur nx times in the Boolean expression. We set up 4nx elements of which 2nx will be used as attaching points while the other will ensure consistency. Call the attaching points and for 1 ≤ inx; call the other point , 1 ≤ i ≤ 2nx. Now, we construct three-sets. The component associated with variable x has 2nx sets:

Suppose there are n variables x1, ..., xn, xi occurs nxi times say. Then, nx1 + nx2 +... + nxn = 3k as there are k clauses. So the number of three-sets formed is 2(nx1 + ...+nxn)=6k.
Also, corresponding to each clause c = (x + y + z), we make nine three-sets, three for each literal. The first of these sets, if picked for the cover indicates that the associated literal is the one set to true in the clause; for literal x in clause c, this set is for some attaching point i. If one of the other two is picked, the associated literal is set to false; for literal x, they are .
So for (x + y + z) we have:

for some i, j, k.
So, totally we have 6k + 9k = 15k three sets. We have element and for 1 ≤ inx. Hence, the number of such elements is 2 * 3k = 6k. Number of elements of the for , 1 ≤ j ≤ 2nx is 2. Σnx = 2.3k = 6k. Hence, totally we have 18k elements.
Note that, for each variable x, the element can be covered only by one of the two sets or . If the first is chosen, then the second cannot be chosen, so that the element , must be covered by the only other three-set in which it appears, namely, . Continuing this chain of reasoning, we see that the choice of cover for entirely determines the cover for all . In this,
  1. all are included and all are excluded or
  2. all are included and all are excluded. Thus, a covering of the components associated with variables corresponds to a legal truth assignment, where the concerned elements correspond to the complement values. Considering the components associated with clauses, we note that exactly three of the nine sets must be selected for the cover. Whichever set is selected to cover the element, tc must include a true literal, thereby ensuring that at least one literal per clause is true. The other two sets chosen cover fc and fc and thus, contain one false literal each, ensuring that at most one literal per clause is true. It can be seen that the construction of the sets can be done in polynomial time, given an instance of positive 1in3SAT.
Note that there are 18k elements and 15k three-sets. Out of the 15k three-sets, we must select 6k to get an exact cover. For each clause, 3 three-sets are chosen amounting to 3k three-sets. For each variable x occurring nx times, nx three-sets are chosen involving elements of the form . The number of such three-sets is . Hence, totally we select 3k + 3k = 6k three-sets and by our choice they are disjoint and hence form an exact cover.

Exercises

1.The notion of a crossing sequence – the sequence of states in which the boundary between two cells is crossed – was introduced in Chapter 6 with regard to two-way FSA. The notion can be extended to TM. Prove the following about crossing sequences.
  1. The time taken by single-tape TM M on input w is the sum of the lengths of the crossing sequences between each two cells of M’s tape.
  2. Suppose M is a single tape TM which accepts an input after reading the whole input and reaches the accepting state when the tape is in a cell to the right of the cells where the input was originally placed. Show that if M accepts input w1w2, and the crossing sequence between w1 and w2 is the same as that between x1 and x2 when M is given input x1, x2, then M accepts x1w2.
2.Discuss how many steps a single-tape TM will require to accept
  1. {wcwR|w ∊ {a, b}*}
  2. {wcw|w ∊ {a, b}*}
3.Show that the following functions are fully time and space constructible
  1. n2
  2. 2n
  3. n!
4.Show that the following problems are NP-complete. Let G = (V, E) be an undirected graph.
  1. A vertex cover of G is a subset SV such that each edge of G is incident upon some vertex in S.
    Does an undirected graph have a vertex cover of size k, |S| = k?
  2. A Hamilton circuit is a cycle of G containing every vertex of V. Does an undirected graph have a Hamilton circuit?
  3. G is k-colorable if there exists an assignment of the integers 1, 2, ..., k, called “colors,” to the vertices of G such that no two adjacent vertices are assigned the same color. The chromatic number of G is the smallest integer k such that G is k-colorable. Is an undirected graph k-colorable?
Let G″ = (V′, E′) be a directed graph.
  1. A feedback vertex set is a subset S′ ⊆ V′ such that every cycle of G′ contains a vertex in S′.
    Does a directed graph have a feedback vertex set with k members?
  2. A feedback edge set is a subset F′ ⊆ E′ such that every cycle of G′ contains a edge in F′.
    Does a directed graph have a feedback edge set with k members?
  3. A directed Hamilton circuit is a cycle containing every vertex of V.
    Does a directed graph have a directed Hamilton circuit?
5.Consider the following problems:
  1. Not-all-equal 3SAT(NAE3SAT) has the same description as 3SAT, except that a satisfying truth assignment may not set all three literals of any clause to true. This constraint results in a symmetric problem: the complement of a satisfying truth assignment is a satisfying truth assignment.
  2. Maximum cut (MxC): Given an undirected graph and a positive integer bound, can the vertices be partitioned into two subsets such that the number of edges with endpoints in both subsets is no smaller than the given bound?
  3. Partition: Given a set of elements, each with a positive integer size, and such that the sum of all element sizes is an even number, can the set be partitioned into two subsets such that the sum of the sizes of the elements of one subset is equal to that of the other subset?
  4. Art Gallery (AG): Given a simple polygon, P, of n vertices and a positive integer bound, Bn, can at most B “guards” be placed at vertices of the polygon in such a way that every point in the interior of the polygon is visible to at least one guard? (A simple polygon one with a well-defined interior; a point is visible to a guard if and only if the line segment joining the two does not intersect any edge of the polygon).
Show that these problems are NP-complete.

TOC Chapter 11

Chapter 11. Universal Turing Machine and Decidability

In this chapter, we consider universal turing machine (TM), the halting problem, and the concept of undecidability.

11.1. Encoding and Enumeration of Turing Machines

The TM is specified by a 6-tuple M = (K, Σ, Γ, δ, q0, F) (refer Definition 9.1). in Γ is a special symbol. The TM can be encoded as a binary string. Without loss of generality, we can take the state set as (q1,q2, ..., qs} where q1 is the initial state and q2 is the final state. The tape symbol set can be taken as {,0,1}. A move of the TM is represented as:
δ(qi, Xj) = (qk, Xr, dl)

11.2. Recursive and Recursively Enumerable Sets

We have seen that the language accepted by a TM is a type 0 language. It is also called a recursively enumerable (RE) set. A TM accepts a string by going to a final state and halting. It can reject a string by halting in a non-final state or getting into a loop. A TM when started on an input may get into a loop and never halt.
We have also seen that a TM corresponds to an effective procedure. An effective procedure is one where at each step, the next step is specified. An effective procedure need not halt. For example,

11.3. Universal Turing Machine

A Universal TM is a TM which can simulate any other TM including itself. Let us denote a universal TM by U. Without loss of generality, we are considering TMs with tape alphabets {0,1,}. The encoding of such a TM T is a binary string dT. U has three tapes. The first tape is presented with dT t; i.e., the encoding of T and the input t to T. It will be of the form:
111...11......111 t...

11.4. Problems, Instances, and Languages

A decision problem is a problem for which the answer is ‘yes’ or ‘no.’ For example, satisfiability problem means to find out whether a Boolean expression is satisfiable or not. We call this as SAT. Also AMB is the ambiguity problem for CFG – i.e., finding out whether a CFG is ambiguous or not. A particular CFG is an instance of the problem. If this particular CFG G is ambiguous, it is an ‘yes’ instance of the problem. If it is not ambiguous, it is a ‘no’ instance of the problem. Similarly, a particular Boolean expression is an instance of SAT problem. If it is satisfiable, it is an ‘yes’ instance of the problem. If it is not satisfiable, it is a ‘no’ instance of the problem. In contrast to these problems, problems like finding a Hamiltonian circuit in a graph are called optimization problems. Whether a graph has a Hamiltonian circuit or not is a decision problem. Finding one is an optimization problem. We shall consider more of this concept in the next chapter.
Any instance of a problem can be encoded as a string. A Boolean expression can be looked at as a string. For example, (x1 + x2)(1 + 2) can be written as (x1 + x2)(¬ x1 + ¬ x2) – a string from the alphabet {(,), x, +, ¬, 0,1,..., 9}. A CFG G = (N, T, P, S) can be looked at as a string over NT∪{(,), {,}, →,}. For example, the grammar ({S}, {a, b}, P, S) where P consists of SaSb, Sab can be looked at as a string ({S}, {a, b}, {SaSb, Sab}, S). It is to be noted that generally integers are represented as decimal or binary and not as unary. The problem can be re-formulated as one recognizing the language consisting of the ‘yes’ instances of the problem.

11.5. Rice’s Theorem

Let us recall that a language accepted by a TM is called a recursively enumerable (RE) language. Without loss of generality we consider TMs over the input alphabet {0, 1} and tape alphabet {0,1,}.
Let F be a set of RE languages. Each language is over the alphabets {0, 1}. F is said to be a property of the RE languages. A language L has the property F, if LF. For example, F may denote the set {L|L is recursive}. F is a trivial property if F is empty or F contains all RE languages. Let LF denote the set {dM|L(M) is in F} where M is a TM, L(M) is the language accepted by it and dM is the encoding of M.

11.6. Reduction of Problems to Show Undecidability

In the last section, we have shown that any non-trivial problem of RE sets is undecidable. This theorem helps to prove many problems to be undecidable. Consider the problem: ‘Will a TM started on a blank tape halt?’ This is equivalent to the problem does εT(M)? and hence undecidable by Rice’s theorem. But for problems about TMs, there is no simple theorem which can be applied. Each problem has to be looked at separately.
Example 11.1.
Consider the question, “Does machine T ever print the symbol S0 when started on tape t?” This is undecidable. There does not exist a TM which will take dTt as input and say whether the symbol S0 will be printed or not, for all (T, t).
For, we may take each machine T which does not ordinarily use the symbol S0 and alter the machine so that before it halts, ‘it prints S0 and halts.’ Then, the ‘printing problem’ for the new machine is the same as the halting problem for the old machine. Since any machine that does use S0 can first be converted to one that does not (by renaming S0) and then altered as above, solution of the printing problem would give solution to all halting problems, and we know that this cannot be done.

11.7. Post’s Correspondence Problem

Let Σ be an alphabet having at least two elements.

Definition 11.1

Given two ordered sets of strings w1,... ,wk and x1,..., xk over Σ, is it possible to find integers i1,... ,in, 1 ≤ ijk such that wi1 ... win = xi1 ... xin? This is called Post’s Correspondence Problem (PCP). If integers i1,... ,in can be found, for an instance of a problem, that instance of PCP has a solution. If no such integers can be found, then that instance does not have a solution.

11.8. Computable Functions

In an earlier chapter, we have looked at a TM as a computing device. It computes a function. The TM M starts with input 1n. It halts in an accepting state ha and at that time if the contents of the tape is 1f(n), if f is defined at n. It halts at a non-accepting state or goes into a loop if f(n) is not defined at n. The partial function f is computed by M. A function which can be computed by a TM is called a Turing computable function. Here, we are restricting ourselves where the domain and range of the functions are tuples of integers. The focus on numerical function values is not as restrictive as it might sound, because any function from strings to strings can be described by encoding both arguments and values of the function as numbers.

Primitive Recursive Function

Definition 11.3 (Initial Functions)

The initial functions are the following:
  1. Constant functions: For each k ≥ 0 and each a ≥ 0, the constant function : is defined by the formula:
    for every

    In the case k = 0, we may identify the function with the number a.
  2. The successor functions: is defined by the formula:
    s(x) = x+1
  3. Projection functions: For each k ≥ 1 and each i with 1 ≤ ik, the projection function is defined by the formula:

Problems and Solutions

1.Which of the following properties of RE sets are themselves RE?
  1. L contains at least two strings.
  2. L is infinite.
Solution.
  1. This is RE.
    Let S = {L1, L2,... } each L in S contains at least two strings. LS = {< M > |T(M) = L and LS}.
    LS will be accepted by a TM MS which halts accepting < M > if < M > is in LS but may not halt if < M > is not in LS. MS takes as input < M > and uses a pair generator and simulates the behavior of M on string xi for j steps. It also keeps a counter, which initially contains 0.
    If M accepts xi in j steps, it increases the counter by 1. If the counter reads 2, MS halts and accepts < M >. Otherwise, it keeps on generating pair after pair and keeps testing. Since the property is nontrivial. LS is not recursive.
  2. This is not RE.
    Let S = {L1, L2,...} each L in S is infinite.
    LS = {< M > |T(M) = L and LS}.
    If LS is RE, it should satisfy the three conditions of Theorem 11.13. But condition 2 is violated. LS is not RE.
2.Which of the following decision problems are decidable?
Let Ti denote the ith TM.
  1. Given x, determine whether xS, where the set S is defined inductively as follows: 0 ∊ S, if uS, then u2 + 1, 3u + 2 and u! are all members of S.
  2. Given x1, x2, and x3 determine whether f(x1) = π2(x2, x3), where f is a fixed non-total recursive function 2 is Cantor numbering).
Solution.
  1. This is decidable.
    Construct a TM T halting on all inputs which stops saying ‘yes’ if xS or stops saying ‘no’ if xS.
    T has one input tape which initially contains x. It has six more tapes
    Tu, T1, T2, T3, T0, Tlist.
    Tu initially contains nothing (blank meaning 0)
    T1 initially contains 1
    T2 initially contains 2
    T3 initially contains 1
    T1ist contains in the increasing order a list of numbers separated by #’s. Initially, it contains # 1 # 2 #.
    T0 is the output tape which is initially blank. When u is in Tu, T computes u2 + 1 on T1, 3u + 2 on T2 and u! on T3, it then compares x with the contents of T1, T2 and T3. If there is a match, T outputs ‘yes’ in T0 and halts. If there is no match, the contents of T1, T2, and T3 are added to the list in T1ist in the proper place. Next string from T1ist is taken and placed on Tu and the process repeats. The process stops if a match between the input and the contents of T1 or T2 or T3 is found at any time with output ‘yes.’ If the contents of T1, T2, and T3 are greater than x (input) the process stops outputting ‘no.’ This is possible as the three functions computed are monotonically increasing. Hence, the problem is decidable.
  2. This problem is undecidable.
    f is a non-total function and π2 is a total function.
    Any algorithm to solve the problem with inputs x1, x2, and x3 should have two subroutines one computing f(x1) and another computing π2(x2, x3). Since f is nontotal for some arguments, the algorithm will not come out of the subroutine for computing f(x1) and will not be able to halt. Hence, the problem is undecidable.
3.Fermat’s last theorem, until recently one of the most-famous unproved statements in mathematics, asserts that there are no integer solution (x, y, z, n) to the equation xn + yn = zn satisfying x, y > 0 and n > 2. Show how a solution to the halting problem would allow you to determine the truth or falsity of the statement.
Solution.Suppose the halting problem is decidable. Construct a TM T which will solve Fermat’s last theorem as follows:
TM T has four tapes. In tape T1, it systematically generates ordered quadruples (x, y, z, n), x ≥ 1, y ≥ 1, z ≥ 1, n ≥ 3. Initial one is (1, 1, 1, 3).
In T2, it computes xn + yn.
In T3, it computes zn.
It compares contexts of T2 and T3 and if they match, outputs ‘yes’ in T4. If there is no match, next quadruple is generated in T1 and the process repeats. If there is no solution for Fermat’s last theorem, T will not halt and will go on forever. Now if ‘Halt’ is the algorithm for the halting problem, give T and the first quadruple as input. If ‘Halt’ says ‘yes’, then Fermat’s last theorem has a solution. If ‘Halt’ says ‘no’, then Fermat’s last theorem has no solution.

Exercises

1.Suppose the tape alphabets of all TMs are selected from some infinite set of symbols a1, a2,.... Explain how each TM may be encoded as a binary string.
2.Which of the following properties of RE sets are themselves RE.
  1. L is a context-free language.
  2. L = LR
3.Which of the following decision problems are decidable?
Let Ti denote the ith TM
  1. Given i and n, determine whether Ti visits more than n squares after being started on blank tape.
  2. Given i, determine whether Ti ever writes the same symbol during two consecutive moves after being started on blank tape.
  3. Given i, determine whether there exists a TM with fewer states that computes the same one-variable function as Ti.
4.Show that the following functions are primitive recursive.
  1. exponentiation
  2. factorial function
  3. predecessor function
  4. proper subtraction
  5. absolute difference |xy|
  6. Sign function
  7. comparison function
5.For each decision problem given, determine whether it is solvable or unsolvable and prove your answer.
  1. Given a TM T, does it ever reach a state other than its initial state when it starts with a blank tape?
  2. Given a TM T and a non-halting state q of T, does T ever enter state q when it begins with a blank tape?
  3. Given a TM T and a non-halting state q of T, is there an input string x that would cause T eventually to enter state q?
  4. Given a TM T, does it accept the string ∊ in an even number of moves?
  5. Given a TM T, is there a string which it accepts in an even number of moves?
  6. Given a TM T and a string w, does T loop forever on input w?
  7. Given a TM T, are there any input strings on which T loops forever?
  8. Given a TM T and a string w, does T reject input w?
  9. Given a TM T, are there any input strings rejected by T?
  10. Given a TM T, does T halt within ten moves on every string?
  11. Given a TM T, is there a string on which T halts within 10 moves?
  12. Given TMs T1 and T2, is L(T1) ⊆ L(T2) or L(T2) ⊆ L(T1)?
6.Which of the following problems about CFGs and their languages are decidable, and which of these are not decidable? Prove.
  1. the problem of determining whether an arbitrary string belongs to the language generated by a given CFG.
  2. the problem of determining whether a CFG generates a non-empty language.
  3. the problem of determining whether the languages generated by two CFGs have any strings in common.
  4. the problem of determining whether two CFGs generate the same language.
  5. given two CFGs G1 and G2, L(G1) ⊆ L(G2).
  6. given CFG G and a regular set R determine whether L(G) = R.
  7. given CFG G and a regular set R determine whether RL(G).
  8. given CFG G determine whether is a CFL.
  9. given two CFGs G1 and G2 determine whether L(G1) ∩ L(G2) is a CFL.