Functions and programs

August 28, 2023

Functions

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

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?

  1. What will it do if CheckIfProgramReturnsOne(*itself*,*itself*) returns 1?

  2. What will it do if CheckIfProgramReturnsOne(*itself*,*itself*) returns 0 or crashes?

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)}?

  1. Is there a b ∈ A such that f(b) = B? If so, why?

  2. What happens if b ∈ B? Why is that a contradiction?

  3. What happens if b ∉ B? Is that a contradiction too?