7.11 Consider our proof that NUMCHARSONSTRING is uncomputable. In particular, examine the program alterYesToNumChars.py (top of figure 7.12). Line 10 of this program returns the string xx, but the proof could remain valid even if we had used a different return value here. Which return values can be used at line 10? In particular, for which of the following return values would the proof remain valid: , a, aa, aaa, aaaa? Explain your answer.

PROBLEM NUMCHARSONSTRING . Input: Two ASCII strings: a program P and an input I. Solution: The length of P(I), if P(I) is defined, or no otherwise. Figure 7.11: A first example of an uncomputable problem that is not a decision problem: NUMCHARSONSTRING. from universal import universal 2 def alterYesToNumChars (inString): (progString, newInString) = utils.DESS (inString) val = universal (progString, newInString) if val == 'yes': # return a string with three characters return 'xxx' else: # return a string with two characters return 'xx' 6 8 10 from numCharsOnString import numCharsOnString #oracle function 2 def yesViaNumChars (progString, inString): singleString = utils.ESS (progString, inString) val = numCharsOnString (rf('alterYesToNumChars.py'), singleString) if val '3': return 'yes' else: return 'no' == 8