Recall that a language L is called decidable there is some machine M such that if M is given any string w as input, M will give the output 1 if w L, 0 if w / L. Decidable languages are also called recursive. A function is said to be computable, or recursive, if it is computed by some machine. There are uncom- putable functions, such as the Busy Beaver function: http://googology.wikia.com/wiki/Busy_beaver_function In fact, there are more uncomputable functions than computable functions. 1. True or False. T = true, F = false, and O = open, meaning that the answer is not known to science at This time.

The problem of whether two given context-free grammars generate the same language is decidable. The problem of whether a given string is generated by a given context-free grammar is 1l decidable. Every bounded function is recursive 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 well-known ratio of the circumference of a circle to its diameter) (z) For every real number x, there exists a machine that runs forever and outputs the string of decimal digits of . 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