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

In this course, a program is a file or string that contains instructions written using a programming language (like C or Python) for how to compute a function.

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

def contains_0101(input_string):
    if "0101" in input_string:
        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. A single function can have lots of programs that implement it.

Decision Programs

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 always_one(input_string):
    return 1

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

def more_than_100_bits(input_string):
    if len(input_string) > 100:
        return 1
    else:
        return 0

Question: One of these programs does not correspond to a function f : {0, 1}^* → {0, 1}. Which is it?

Answer

The Python function maybe_loop_forever does not correspond to a true function f : {0, 1}^* → {0, 1}.

def always_one(input_string):
    return 1

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

def more_than_100_bits(input_string):
    if len(input_string) > 100:
        return 1
    else:
        return 0

Converting Programs to Strings

Each program is written using ASCII characters. For example:

def always_one(input_string):
    return 1

has 43 ASCII characters (including an end of file EOF character). How many bits is that? Recall that standard ASCII codes go from 0 to 127.

Inputing One Program Into Another

What output would we get if we used the binary representation of the always_one program as the input_string for the more_than_100_bits program?

more_than_100_bits(binary_encoding("always_one.py"))

What about using the binary representation of always_one.py in maybe_loop_forever?

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

Inputing a Program Into Itself

What happens with each of these commands?

always_one(binary_encoding("always_one.py"))

maybe_loop_forever(binary_encoding("maybe_loop_forever.py"))

more_than_100_bits(binary_encoding("more_than_100_bits.py"))

A More Complicated Program

Consider the following unfinished program:

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

This program is impossible!
We’ll use a proof by contradiction.

Here’s the idea:

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

def reverse_check(program_string):
    return 1 - check_if_program_returns_one(program_string, program_string)

What will reverse_check do?

If we feed reverse_check itself as input, why can’t it return 1?
Why can’t it return 0?

Conclusion

Both check_if_program_returns_one and reverse_check are impossible programs.

But the function we are trying to program with reverse_check is a perfectly well defined function f : {0, 1}^* → {0, 1}.
- It inputs a binary encoding of a Python program.
- It outputs 0 if the program returns one when it runs on itself as its input.
- Otherwise if the input is gibberish or runs forever or doesn’t output 1, then f outputs 1.
There is just no binary encoding of a program for this function, because that would be impossible.

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 based on cardinality.

How many computer programs are possible (say programs written using ASCII characters)?
How big is the set {0, 1}^*?
Answer: The strings {0, 1}^* are countable, so their cardinality is ℵ₀.
How many functions f : {0, 1}^* → {0, 1} are there?

Theorem. If A, B are finite sets and |A| = a and |B| = b, then the cardinality of the set of all functions f : A → B (denoted {f : f : A → B}) is b^a.
If A is an infinite set, then we abuse notation slightly and say that the cardinality of {f : f : A → B} is b^|A|.

How Many Functions?

How many functions f : {0, 1}^* → {0, 1} are there?
Since |{0, 1}^*| = ℵ₀, the cardinality of {f : f : {0, 1}^* → {0, 1}} = 2^ℵ₀ which is uncountable because it is the same as the cardinality of the power set (i.e., set of all subsets) of ℕ.
Theorem (Exercises 4-5 on HW 2). The power set 2^A of a set A always has higher cardinality than the set A itself.

Conclusion. You cannot program every function from {0, 1}^* because there are 2^ℵ₀ such functions, but only ℵ₀ possible computer programs.

Schroeder Bernstein Theorem

Another really useful theorem is:

Schroeder-Bernstein Theorem. If the are 1-to-1 functions f : A → B and g : B → A, then there is a bijection from A to B. In particular, |A| = |B|.

Functions and programs