August 28, 2023

# Functions

• We’ve seen that Boolean circuits can be used to calculate any function {0, 1}n → {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``````
• Question: Which of these programs corresponds to a function f : {0, 1}* → {0, 1}?

# 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"))``
• What about using the binary representation of `AlwaysOne.py` in `MaybeLoopForever`?
``````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.  ``````
• This program is impossible!

• We’ll use a proof by contradiction.

# 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.

• How many computer programs are possible (say programs written using ASCII characters)?

• How big is the set {0, 1}*?

• How big is the set {f : f : {0, 1}* → {0, 1}}?

• Answer: Every ASCII program can be encoded as a binary string in {0, 1}*. Since {0, 1}* is countably infinite, so is the set of all possible ASCII programs. The last set {f : f : {0, 1}* → {0, 1}} has cardinality 2|{0,1}*| = 20 which is uncountable.

• Conclusion. You cannot program every function from {0, 1}* because there are 20 such functions, but only 0 possible 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?