Part $1$:

F$($P$)$I$(|$P$($I$)|==|$I$|*2$n$,$ n $>=1).$ That is$,$ P is a positive instance of F if is there is some string I such that the length of the output from the P$($I$)$ call is a power of two times the length of the input, excluding $20.$

Prove that F is undecidable by modifying the template to show that yesOnString $<=$T F $($updated $2/14$ to define yesViaPow$2()$ with two parameters instead of $1)$:

ReduceYesToPow$2$Len$-1.$py

$\text{'}\text{'}\text{'}$

This lab requires you to complete two functions,

yesViaPow$2($progString$,$inString$),$ and alterYesToPow$2.$ These functions

will not be run, they are thought experiments to help us reason about

decidability and recognizability. To save time and trouble, both are included in the same file, even though the call to pow$2$len expects alterYesToPow$2.$py to be in a separate file from yesViaPow$2.$py

$\text{'}\text{'}\text{'}$

import utils; from utils import rf

from universal import universal

def yesViaPow$2($progString$,$inString$)$:

# $...$ add code needed to show that yesOnString reduces to

# pow$2$len. That is$,$ to show that this function, yesViaPow$2,$ could

# decide yesOnString if pow$2$Len could decide if there was some

# input to a Python function such that the length of the output

# was a power of two times the length of the input.

# If needed, add second parameter to the pow$2$Len call.

result $=$ pow$2$Len$($rf$(\text{'}$alterYesToPow$2.$py$\text{'}))$

# Add any other code needed for the reduction, and return

# the right thing.

# return something # CHANGE THIS

def alterYesToPow$2($inString$)$

# Add code needed for the reduction

# Somewhere in this function you'll need a call to universal

# val $=$ universal$($aProgram$,$aString$)--$ CHANGE universal args

# Finally, modify the template below such that altersYesToPow$2$

# will be a positive instane of pow$2$Len iff progString$($inString$)$

# is a positive instance of yesOnString, where progString &

# inString are the arguments to yesViaPow$2.$

#

# if a certain condition:

# return something meaningful to pow$2$Len

# else:

# return something with the opposite meaning

# to pow$2$Len

To understand F$,$ suppose that $($P$)$ were a function that decided if P was a positive or negative instance of F$,$ and consider these two functions:

def gAlphabet$($inString$)$: return 'CAGT$*4\text{'}$

def pivotEpsilon$($inString$)$:

if inString $==\text{'}\text{'}$: return 'CAGT'

else: return $\text{'}\text{'}$

Then $($rf$(\text{'}$gAlphabet$.$py$\text{'}))==$ 'yes', because if len$($inString$)$ is $2$ or $4,$ the output length $16$ is $24$ or $22$ times the length of the input.

And $($rf$(\text{'}$pivotEpsilon$.$py$\text{'}))==\text{'}$no$\text{'},$ because the output of pivotEpsilon is never a power of two times the input length.

Part $2$:

Recall the definition of F:

F$($P$)$I$(|$P$($I$)|==|$I$|*2$n$,$ n $>=1).$ That is$,$ P is a positive instance of F if is there is some string I such that the length of the output from the P$($I$)$ call is a power of two times the length of the input, excluding $20.$

L$0213$a asked you to prove that F was undecidable. For this lab, answer these questions and explain your thinking.

a$.$ Is F recognizable?

b$.$ How would you define $$F$,$ the complement of F$,$ without reference to F$?$ That is$,$ under what conditions would $$F return 'yes'$/\text{'}$no$\text{'}$

c$.$ Is $$F recognizable?