August 28, 2023
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}?
Consider the following computer program, that takes an input string
called inputString
from {0, 1}^{*}.
Functions and programs are not the same. The code above is just one way to implement the abstract function we are describing.
These are all decision programs.
def MaybeLoopForever(inputString):
if "1" in inputString:
n = 1
while(n > 0):
n = n+1
else:
return 0
Each program is written using ASCII characters. For example:
has 39 ASCII characters (including an end of file EOF character). How many bits is that?
What output would we get if we used the binary representation of the
AlwaysOne
program as the inputString
for the
MoreThan100Bits
program?
What happens with each of these commands?
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.
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?
What will it do if
CheckIfProgramReturnsOne(*itself*,*itself*)
returns
1?
What will it do if
CheckIfProgramReturnsOne(*itself*,*itself*)
returns 0 or
crashes?
The program CheckIfProgramReturnsOne
is impossible.
Otherwise you would be able to create the impossible program
ReverseCheckIfProgramReturnsOneOnSelf
.
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}*|} = 2^{ℵ0} which is uncountable.
Conclusion. You cannot program every function from {0, 1}^{*} because there are 2^{ℵ0} such functions, but only ℵ_{0} possible computer programs.
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)}?
Is there a b ∈ A such that f(b) = B? If so, why?
What happens if b ∈ B? Why is that a contradiction?
What happens if b ∉ B? Is that a contradiction too?