True or False. T = true, F = false, and O = open, meaning that the answer is not known science at this

time. In the questions below, P and NP denote P-time and NP-time, respectively.

(xvii) If G is a context-free granmar, the question of whether L(G) = . is decidable, where is the terminal alphabet of G. (xviii) The set of all fractions whose values are less than is decidable. (A fraction is a string, defined to be a non-empty string of decimal digits followed by a slash followed by a non-empty xix) There exists a polynomial time algorithm which finds the factors of any positive integer, (xx)For any two languages L1 and L2, if L is undecidable and there is a recursive reduction of (xxi)_ For any two languages L1 and L2, if L2 is undecidable and there is a recursive reduction of string of decimal digits, such as "3/42") where the input is given as a unary ("caveman") numeral. L1 to L2, then L mst be undecidable. L1 to L2, then L1 must be undecidable. (xxi) As you may have learned, there is a formal language which can be used to write any mathematical proposition as well as any proof of any mathematical proposition. In 1978, Jack Milnor told me If P is a mathematical proposition that can be written using string of length n, and P has There is a P-TIME reduction of the context-free grammar membership problem to the halting that in the future no proof wll be accepted unless it can be verified by a computer. a proof, then P must have a proof whose length is 0(22 (xx