Functions

• We’ve seen that Boolean circuits can be used to calculate any function {0, 1}ⁿ → {0, 1}.

• What about functions f : {0, 1}^* → {0, 1}?

• Answer: No! We’ll prove today that some of those functions are impossible to compute.
  

Programs

Consider the following computer program, that takes an input string called inputString from {0, 1}^*.

def contains0101(inputString):
    if "0101" in inputString:
        return 1
    else:
        return 0

• Functions and programs are not the same. The code above is just one way to implement the abstract function we are describing.

• Decision programs. A program that always returns a 0 or a 1 when it finishes is called a decision program.
  
  • It’s okay if the program might crash on some inputs.
  • It’s also okay if some inputs cause the program to loop forever.
  • As long as the program only ever returns 0 or 1 when it finishes (if it ever does!).

Example Decision Programs

These are all decision programs.

def AlwaysOne(inputString):
    return 1

def MaybeLoopForever(inputString):
    if "1" in inputString:
        n = 1
        while(n > 0):
            n = n+1
    else:
        return 0

def MoreThan100Bits(inputString):
    if len(inputString) > 100:
        return 1
    else:
        return 0

Converting Programs to Strings

Each program is written using ASCII characters. For example:

def AlwaysOne(inputString):
    return 1

has 39 ASCII characters (including an end of file EOF character). How many bits is that?

Inputing One Program Into Another

What output would we get if we used the binary representation of the AlwaysOne program as the inputString for the MoreThan100Bits program?

MoreThan100Bits(binaryEncoding("AlwaysOne.py"))

def MaybeLoopForever(inputString):
    if "1" in inputString:
        n = 1
        while(n > 0):
            n = n+1
    else:
        return 0

Inputing a Program Into Itself

What happens with each of these commands?

AlwaysOne(binaryEncoding("AlwaysOne.py"))

MaybeLoopForever(binaryEncoding("MaybeLoopForever.py"))

MoreThan100Bits(binaryEncoding("MoreThan100Bits.py"))

A More Complicated Program

Consider the following unfinished program:

def CheckIfProgramReturnsOne(programString,inputString):
    # return 1 if 
    #   1. programString is the ASCII binary encoding of a valid Python program, and
    #   2. The program defined by programString returns 1 when given inputString as its input.
    # otherwise, return 0.  

Here’s the idea:

If the program function CheckIfProgramReturnsOne is possible, then we could make the following Python function:

def ReverseCheckIfProgramReturnsOneOnSelf(programString):
    return 1-CheckIfProgramReturnsOne(programString,programString)

What will this program do?

Conclusion

The program CheckIfProgramReturnsOne is impossible.

Otherwise you would be able to create the impossible program ReverseCheckIfProgramReturnsOneOnSelf.

Un-programmable Functions

There is an easier way to see that there are functions f : {0, 1}^* → {0, 1} which are impossible to implement with computer programs.

Cardinality of Power Sets

The previous argument relied on the following important theorem:

Theorem. The power set of a set A (i.e., the set of all subsets of A) always has higher cardinality than the set A, itself.

Proof. Suppose that there was a function f from A onto the power set of A. Then you can ask whether a ∈ f(a) for every A. What can you say about the set B = {a ∈ A : a ∉ f(a)}?