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.

Every bounded function is recursive. If L is NP and also co-NP, then L must be P Recall that if C is a class of languages, co- is defined to be the class of all languages that (xxiv) xxvi are not in L. Let R be the class of all recursively enumerable languages. If L is in RE and also L is in co-RE then L must be decidable. )Every language is enumerable If a language L is undecidable, then there can be no machine that enumerates L There exists a mathematical proposition that can be neither proved nor disproved. There is a non-recursive function which grows faster than any recursive function There exists a machine' that runs forever and outputs the string of decimal digits of (the (xxix) well-known ratio of the circumference of a circle to its diameter) (xxxii) For every real number r, there exists a machine that runs forever and outputs the string of decimal digits of z As always in automata theory, "machine" means abstract machine, a mathematical object whose memory and running time are not constrained by the size and lifetime of the known (or unknown) universe, or any other physical laws. If we want to discuss the kind of machine that exists (or could exist) physically, we call it a "physical machine