3.12 Consider a Python program startsWithz.py. This program takes two parameters (P, I). It returns yes if P(I) is a string that starts with the character Z, and no otherwise. Using an approach similar to figure 3.9 and claim 5.4 (page 38), prove that startsWithz.py cannot exist. 38. 3 Some impossible Python programs Program name Program behavior yesOnString(P, 1) - return yes, if P(I) =yes return "no", otherwise yesOnSelf (P) - return yes, if P(P) = "yes" return "no", otherwise notYesOnSelf(P) return no, if P(P)= yes return "yes", otherwise Figure 3.8: A sequence of three decision programs that cannot exist. The last program, notyesonself.py, is obviously impossible since it produces a contradiction when run on itself. However, each of the programs can be produced easily by invoking the one above it (shown by the arrows). Therefore, none of the three programs can exist. from yesOnString import yesOnString 2 def weirdYesOnString (progString): if yesOnString (progString, progString) =='yes': return 'no' else: return 'yes' 6 Figure 3.9: The program weirdYesonString.py. only a few lines. Because it will be important for us to understand the compact version of the proof, we will now restate the previous claim, and give the compact proof. Claim 3.4. The Python program yesOnString.py cannot exist. Proof of the claim. Suppose yesOnString.py does exist, and argue for a con- tradiction. Then we can write the program weirdYesOnString.py, shown in figure 3.9. This program has the same behavior as notYesOnSelf.py: when it is given itself as input, weirdYesonString.py returns yes if and only if it returns no. So all possible behaviors result in a contradiction, and the claim is proved. Definition of a Python program. With respect to a reference computer system C, a Python program is a string of ASCII characters P, such that Pis syntactically correct Python; P defines at least one Python function in which case the first defined function is the main function). We also need to define the output of a Python program. Our initial definition assumes the main function has a single parameter; we will later describe how to relax that requirement. Definition of P(I), the output of a Python program. Let P be a Python program with respect to a reference computer system C. Suppose P has main function M, and let I be a string of ASCII characters that will be used as input to P. The output of P on input I, written P(I), is produced by using computer C to execute M with input I, then defining P(I) as follows: If M returns an ASCII string S, then P(I)=S. If M returns a Python object that is not an ASCII string, then P(I) is undefined. . If M throws an exception on input I, then P(I) is undefined. If M doesn't terminate on input I, then P(I) is undefined. In plain English, P(I) is the string output by P's main function on input I, whenever this makes sense, and undefined otherwise. The detailed definition above gives the precise meaning of whenever this makes sense. Note that the definition can easily be generalized for main functions that receive multiple string parameters. We replace I with multiple strings 11, 12, ..., and obtain a corresponding definition for P(11,12, ...). The above definitions of Python programs and their outputs work perfectly well in practice, but from a mathematical point of view they might appear to have some technical problems. What exactly do we mean by syntactically correct Python? Does the definition depend on which computer and operating system are used? Do different versions of Python produce different results? How do we define the output if the computer crashes during execution? What if someone has edited the Python library files, so that a statement such as import sys does not import the expected functionality from the sys module? What if the Python program runs out of memory
