7.5 Prove that each of the following problems is undecidable. Each problem receives a single program P as input. (a) EMPTYONEMPTY: Does Ple) = ? (b) GAGAONEMPTY: Does P() =GAGA? (c) NOONSOME: Does P(I) =no for some I? (d) YESONGAGA: Does P(GAGA) =yes? (e) LONGERTHAN3ONALL: Is \P(I)| > 3 for all I? 7.11 Consider our proof that NUMCHARSONSTRING is uncomputable. In par- ticular, 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. ure 7.11: A first example of an uncomputable problem that is not a decision problem: JMCHARSONSTRING. from universal import universal 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' from numCharsOnString import numCharsOnString # oracle function def yesViaNumChars (progString, inString): singleString = utils.ESS (progString, inString) val = numCharsOnString (rf('alterYesToNumChars.py'), \ singleString) if val == '3': return 'yes' else: return 'no' 7.5 Prove that each of the following problems is undecidable. Each problem receives a single program P as input. (a) EMPTYONEMPTY: Does Ple) = ? (b) GAGAONEMPTY: Does P() =GAGA? (c) NOONSOME: Does P(I) =no for some I? (d) YESONGAGA: Does P(GAGA) =yes? (e) LONGERTHAN3ONALL: Is \P(I)| > 3 for all I? 7.11 Consider our proof that NUMCHARSONSTRING is uncomputable. In par- ticular, 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. ure 7.11: A first example of an uncomputable problem that is not a decision problem: JMCHARSONSTRING. from universal import universal 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' from numCharsOnString import numCharsOnString # oracle function def yesViaNumChars (progString, inString): singleString = utils.ESS (progString, inString) val = numCharsOnString (rf('alterYesToNumChars.py'), \ singleString) if val == '3': return 'yes' else: return 'no
