320 Q, Theory ofComputer Science
10.6 Give an example of a language that is not recursive but recursively
enumerable.
10.7 Do there exist languages that are not recursively enumerable?
10.8 Let L be a language over L. Show that only one of the following are
possible for Land r.
(a) Both Land r are recursive.
(b) Neither L nor r is recursive.
(c) L is recursively enumerable but L is not.
(d) r is recursively enumerable but L is not.
10.9 What is the difference between A TM and HALT TM ?
10.10 Show that the set of all real numbers between 0 and 1 is uncountable.
(A set S is uncountable if S is infinite and there is no one-to-one
correspondence between S and the set of all natural numbers.)
10.11 Why should one study undecidability?
10.12 Prove that the recursiveness problem of type 0 grammar is unsolvable.
10.13 Prove that there exists a Turing machine M for which the halting
problem is unsolvable.
10.14 Show that there exists a Turing machine Mover {O, I} and a state qm
such that there is no algorithm to determine whether or not M will enter
the state ql11 when it begins with a given ill.
10.15 Prove that the problem of determining whether or not a TM over {O, 1}
will ever print the symbol 1, with a given tape configuration, is
unsolvable.
10.16 (a) Show that {x I x is a set and x ~ x} is not a set. (Note that this
seems to be well-defined. This is one version of Russell's paradox.)
(b) A village barber shaves those who do not shave themselves but no
others. Can he achieve his goal? For example, who is to shave the
barber? (This is a popular version of Russell's paradox.)
Hints: (a) Let S ={x I x be a set and x ~ x}. If S were a set, then S E S or
S ~ S. If S ~ S by the 'definition' of S, then S E S. On the other
hand, if S E S by the 'definition' of S, then S ~ S. Thus we can
neither assert that S ~ S nor S E S. (This is Russell's paradox.)
Therefore, S is not a set.
(b) Let S = {x Ix be a person and x does not shave himself}. Let b
denote the barber. Examine whether b E S. (The argument is
similar to that given for (a).) It will be instructive to read the proof
of HP of Turing machines and this example, in order to grasp the
similarity.
10.17 Comment on the following: "We have developed an algorithm so
complicated that no Turing machine can be constructed to execute the
algorithm no matter how much (tape) space and time is allowed."
10.6 Give an example of a language that is not recursive but recursively
enumerable.
10.7 Do there exist languages that are not recursively enumerable?
10.8 Let L be a language over L. Show that only one of the following are
possible for Land r.
(a) Both Land r are recursive.
(b) Neither L nor r is recursive.
(c) L is recursively enumerable but L is not.
(d) r is recursively enumerable but L is not.
10.9 What is the difference between A TM and HALT TM ?
10.10 Show that the set of all real numbers between 0 and 1 is uncountable.
(A set S is uncountable if S is infinite and there is no one-to-one
correspondence between S and the set of all natural numbers.)
10.11 Why should one study undecidability?
10.12 Prove that the recursiveness problem of type 0 grammar is unsolvable.
10.13 Prove that there exists a Turing machine M for which the halting
problem is unsolvable.
10.14 Show that there exists a Turing machine Mover {O, I} and a state qm
such that there is no algorithm to determine whether or not M will enter
the state ql11 when it begins with a given ill.
10.15 Prove that the problem of determining whether or not a TM over {O, 1}
will ever print the symbol 1, with a given tape configuration, is
unsolvable.
10.16 (a) Show that {x I x is a set and x ~ x} is not a set. (Note that this
seems to be well-defined. This is one version of Russell's paradox.)
(b) A village barber shaves those who do not shave themselves but no
others. Can he achieve his goal? For example, who is to shave the
barber? (This is a popular version of Russell's paradox.)
Hints: (a) Let S ={x I x be a set and x ~ x}. If S were a set, then S E S or
S ~ S. If S ~ S by the 'definition' of S, then S E S. On the other
hand, if S E S by the 'definition' of S, then S ~ S. Thus we can
neither assert that S ~ S nor S E S. (This is Russell's paradox.)
Therefore, S is not a set.
(b) Let S = {x Ix be a person and x does not shave himself}. Let b
denote the barber. Examine whether b E S. (The argument is
similar to that given for (a).) It will be instructive to read the proof
of HP of Turing machines and this example, in order to grasp the
similarity.
10.17 Comment on the following: "We have developed an algorithm so
complicated that no Turing machine can be constructed to execute the
algorithm no matter how much (tape) space and time is allowed."