\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 4    *
%**************


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{\bf (15 points)}
Suppose that the following procedure is used to multiply two
non-negative integers $a$ and $b$.

\centerline{
\begin{minipage}{0 in}
\medskip
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= xxx \= xxx \= \kill
Let $x = a$, $y = b$, $p = 0$. \\
Repeat the following steps. \\
\> If $x = 0$, then output $p$ and terminate. \\
\> Otherwise, if $x$ is even, then let $x = x/2$ and $y = 2y$. \\
\> Otherwise, if $x$ is odd, then let $x = x - 1$ and $p = p + y$.
\end{tabbing}
\medskip
\end{minipage}}

\begin{problemparts}

\problempart Model the procedure with a state machine.

\solution{The set of states $Q$ consists of quintuples $(a, b, x, y,
p)$ where all variables are non-negative integers.  The set of start
states $Q_0$ consists of the single state $(a, b, a, b, 0)$.  The set
of transitions $\delta$ consists of transitions of the form $(a, b, x,
y, p) \rightarrow (a, b, x', y', p')$ where one of the following two
sets of conditions holds:

\begin{enumerate}
\item $x$ is even and positive, $x' = x/2$, $y' = 2y$, and $p' = p$.
\item $x$ is odd, $x' = x - 1$, $y' = y$, and $p' = p + y$.
\end{enumerate}
}

\problempart Formulate an invariant relating $a$, $b$, $x$, $y$, and
$p$ that holds at the top of the loop.  Your invariant should imply
that when $x = 0$, $p = ab$.

\solution{
\[
xy + p = ab
\]
}

\problempart Prove that the invariant holds.

\solution{ The invariant holds initially, because $x = a$, $y = b$,
and $p = 0$.  Suppose that the invariant holds in state $(a, b, x, y,
p)$.  The invariant holds under a transition of the first type because:

\begin{eqnarray*}
x' y' + p'	& = &	(x / 2) \cdot 2y + p \\
		& = &	x y + p \\
		& = &	a b
\end{eqnarray*}

The first equation follows from the definition of the first type of
transition.  The second line is obtained by simplification, and the
third line uses the hypothesis that the invariant holds prior to the
transition.  By similar reasoning, the invariant holds under a
transition of the second type:

\begin{eqnarray*}
x' y' + p'	& = &	(x - 1) \cdot y + (p + y)\\
		& = &	x y + p \\
		& = &	a b
\end{eqnarray*}
}

\problempart Prove that the procedure terminates.

\solution{The variable $x$ is a non-negative integer that decreases
under every transition.  Therefore, the procedure must terminate after
at most $x$ transitions.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} Brad Banks, the one 6.042 TA that Theory
Pig trusts as his true friend, has promised our mascot a delicious
treat.  He places Theory Pig on one end of a 1 meter long rubber mat
and places the treat at the other end of the mat.  Theory Pig then
begins to run excitedly toward his treat at the rate of 1 centimeter
per second.  (Theory Pig is four inches tall and a bit pudgy.)

However, after exactly one second has elapsed, Brad stretches the
rubber mat out by 1 meter, so that its total length is now 2 meters.
The mat stretches uniformly and instantly, so there are now 2
centimeters of mat behind Theory Pig and 198 centimeters between him
and his treat.  Theory Pig continues running toward his prize, but
whenever another second elapses, Brad stretches the mat out by
another meter.

Either prove that Theory Pig never reaches his treat or else compute
approximately the number of seconds that he requires.

\solution{ Running at a rate of 1 centimeter per second, Theory Pig
crosses $1/100$ of the mat in the first second, $1/200$ of the mat in
the second second, $1/300$ of the mat in the third second, and so
forth.  He reaches his treat within $n$ seconds provided that the sum
of the first $n$ of these fractions is greater than or equal to 1.
Note that the sum of the first $n$ of these fractions is just $H_n /
100$.  This expression is at least 1 when $H_n$ is at least 100.
Since $H_n$ is about $\ln n$, around $e^{100} \approx 10^{43}$ seconds
are required for Theory Pig to reach his tasty treat.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} The 6.042 staff recently received the
following mystifying, but disturbing email.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 2 complaint

We found your depiction of our society in problem set 2 simplistic,
inaccurate, and insulting.  We have launched a Fritolator device from
our homeworld at galactic coordinates (0, 0, 0).  During each hour,
the Fritolator can move in any one of the following ways.

  1.  first coordinate +4, second +1, third -1
  2.  first coordinate +1, second -1, third +3
  3.  first coordinate -2, second +3, third +4

Expect Earth, located at galactic coordinates (7, 8, 5), to be
Fritolated promptly.

/Grzzwk
\end{verbatim}

We are unsure what Fritolation entails, but surmise that it is not
good.

\begin{problemparts}

\problempart Model the movement of the Fritolator as a state machine.

\solution{
\begin{itemize}
\item The set of states $Q$ consists of all triples of integers $(x, y
, z)$.
\item The set of initial states $Q_0$ consists of the single
state $(0, 0, 0)$.
\item For all integers $x$, $y$, and $z$, the set of transitions
$\delta$ contains the following three transitions:

\begin{eqnarray*}
(x, y, z) & \rightarrow & (x + 4, y + 1, z - 1) \\
(x, y, z) & \rightarrow & (x + 1, y - 1, z + 3) \\
(x, y, z) & \rightarrow & (x - 2, y + 3, z + 4)
\end{eqnarray*}
\end{itemize}
}

\problempart Either list a sequence of Fritolator moves leading to the
destruction of Earth, or use the Invariant Theorem to prove that Earth
is safe.

\solution{
Earth is safe.

\bigskip

\begin{proof}
The proof uses the Invariant Theorem.  We prove that the following
invariant holds: in state $(x, y, z)$, $2x + 2y + z \equiv 0
\pmod{3}$.

The invariant holds in the only start state, $(0, 0, 0)$, because $2
\cdot 0 + 2 \cdot 0 + 0 \equiv 0 \pmod{3}$.  Next, we prove that the invariant
is maintained under each transition in $\delta$.  There are three
cases to consider corresponding to the three possible Fritolator
moves.

\begin{itemize}

\item If the Fritolator moves from $(x, y, z)$ to $(x + 4, y + 1, z -
1)$, then the invariant is maintained because:

\begin{eqnarray*}
2 (x + 4) + 2(y + 1) + (z - 1)
	& \equiv & (2 x + 2 y + z) + 9 \pmod{3} \\
	& \equiv & 2 x + 2 y + z \pmod{3} \\
	& \equiv & 0 \pmod{3} \\
\end{eqnarray*}

Terms are just rearranged in the first step.  The second step uses the
fact that 6 is a multiple of 3, and the third step uses the assumption
that the invariant holds in state $(x, y, z)$.

\item Similarly, if the Fritolator moves to position $(x + 1, y - 1, z
+ 3)$, then the invariant is maintained because $2 (x + 1) + 2 (y - 1)
+ (z + 3) \equiv (2x + 2y + z) + 3 \equiv 0 \pmod{3}$.

\item If the Fritolator moves to position $(x - 2, y + 3, z + 4)$,
then the invariant is maintained because $2 (x - 2) + 2 (y + 3) + (z +
4) \equiv (2x + 2y + z) + 6 \equiv 0 \pmod{3}$.
\end{itemize}

Earth is safe at coordinates $(7, 8, 5)$, because $2 \cdot 7 + 2 \cdot
8 + 5 \equiv 2 \pmod{3}$.
\end{proof}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%%%%  S99 ps4



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Suppose that the following procedure is used to
raise a real number $x$ to the non-negative integral power $y$.  
\begin{itemize}
\item Do the assignments $a := x, b := y, p := 1$.
\item Repeat the following steps:
  \begin{itemize}
  \item If $b$ is 0, output $p$ and terminate.
  \item If $b$ is even, do the assignment $a := a^2$ (that is, set the next
        value of $a$ to be the square of the current value), and also do
        $b := b/2$.
  \item If $b$ is odd, do $p := p \cdot a$ and $b := b - 1$.
  \end{itemize}
\end{itemize}

\begin{problemparts}
\problempart Model the procedure with a state machine.

\solution

The state can be represented with a triple of numbers $a,b,p$:
\[Q = \{a, b, p\} \subset
(\reals \times \naturals \times \reals)
\]
The initial state is
\[
q_0 = (x,y,1)
\]
There are two transitions:
\begin{eqnarray*}
(a, b, p) &\rightarrow& (a^2, b/2, p) \,\,\mbox{ if $b$ is even and $b > 0$}
\\
(a, b, p) &\rightarrow& (a, b-1, ap) \,\,\mbox{ if $b$ is odd}
\end{eqnarray*}
The terminating condition is $b=0$, and then the state machine outputs~$p$.



\problempart Formulate an invariant relating $a, b, x, y$, and $p$ that
holds at the top of the loop.  Your invariant should imply that if
$b = 0$, then $p = x^y$.

\solution

The invariant is expressed by the following predicate $P(\cdot)$ which
takes a state of the machine as an argument:
\[
P(a,b,p)=\mbox{``\,\,$a^bp=x^y$\,\,''}
\]
Note that if $b=0$ and $P(a,b,p)$ then $a^bp=p=x^y$.


\problempart Prove that the invariant holds.

\solution

Clearly, $P(q_0)$ holds:
\[
P(q_0)=\mbox{``\,\,$(x^y)*1=x^y$\,\,''}
\]
Now, we show that if $P(q)$ and $(q,q')$ is a valid transition then
$P(q')$: 

Take some $q=(a,b,p)$ and assume $P(q)$, i.e. that $a^bp=x^y$.  $q'=(a',b',p')$
could be a state following $q$ if one of the two cases holds:
\begin{itemize}
\item 
If $b>0$ and $b$ even then $(a',b',p')=(a^2,b/2,p)$, and then
\[
(a')^{b'}p'=(a^2)^{(b/2)}p=a^bp=x^y
\]
where the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true.
\item
If $b$ odd then $(a',b',p')=(a,b-1,ap)$, and then
\[
(a')^{b'}p'=a^{b-1}ap=a^bp=x^y
\]
where again, the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true as well.
\end{itemize}


\problempart Prove that the procedure terminates.

\solution

We need to show that $b$ always reaches $0$, because that's the
termination condition.  Let's argue the following facts:
\begin{enumerate}
\item 

It is an invariant of this state machine that $b$ is an integer.  It
starts as an integer $y$, and the two transitions preserve that: If
$b\in\integers$ and $b$ is even then $b/2\in\integers$.  Similarly,
if $b\in\integers$ then $(b-1)\in\integers$.

\item

$b$ cannot be a negative number.  We can show that by a contradiction:
If $b$ ever reached a negative number, since $b$ starts from a
nonnegative integer $y$, there must be a transition where $b$ went
below $0$, i.e. a transition from $b\geq{0}$ to $b'<0$.  But that's impossible
with our transitions:  
\begin{itemize}
\item
If $b\geq{0}$ then $b/2\not<{0}$
\item
If $b\geq{0}$ and $b\neq{0}$ then $b-1\not<0$.
\end{itemize}

\item

$b$ decreases in every transition (obviously, if $b>0$ than $b/2<b$
and $b-1<b$).
\end{enumerate}

Facts (1), (2) and (3) imply that $b$ must attain the value $b=0$ and
trigger the state machine to terminate.

Formally, it the the well-ordering principle that we use here: From
facts (1) and (2) it follows that for any execution of this state
machine, the set of values of variable $b$ is a subset of $\naturals$.
Therefore, from the well-ordering principle, it must have the smallest
element $b_0$.  Now from fact (3) we see that $b_0=0$ (or otherwise
$b_0$ could not be the smallest value attained by $b$, since if
$b\neq{0}$ then the next $b$ would be smaller).  Hence $b_0=0$ and so
the procedure must terminate.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} A hungry ant is placed on an unbounded grid.
Each square of the grid either contains a crumb or is empty.  The squares
containing crumbs form a path in which, except at the ends, every crumb is
adjacent to exactly two other crumbs.  The ant is placed at one end of the
path and on a square containing a crumb.  For example, the figure below
shows a situation in which the ant faces North, and there is a trail
of food leading approximately Southeast.  The ant has already eaten
the crumb upon which it was initially placed.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/ant.eps}}}
\bigskip

The ant can only smell food directly in front of it.  The ant can only
remember a small number of things, and what it remembers after any move
only depends on what it remembered and smelled immediately before the
move.  Based on smell and memory, the ant may choose to move forward one
square, or it may turn right or left.  It eats a crumb when it lands on
it.

%The ant sends a signal whenever it cannot smell food on all four adjacent squares.

The above scenario can be nicely modelled as a state machine in which each
state is a pair consisting of the ``ant's memory'' and ``everything
else,'' e.g., information about where things are on the grid.  Work out
the details of such a model state machine; design the ant-memory part of
the state machine so the ant will eat all the crumbs on \emph{any} finite
path at which it starts and then signal when it is done.  Be sure to
clearly describe the possible states, transitions, and inputs and outputs
(if any) in your model.  Briefly explain why your ant will eat all the
crumbs.

\solution

If all the crumbs are placed as if ``on a string'', then the ant can
pick them all up very easily: If the ant smells no crumb in front of
it, it should turn in some fixed direction (say left), and if it does
smell a crumb, it should go forward and eat it.  Hence the ant can eat
all the crumbs of bread even if it is completely memory-less.
However, we requested that the ant-machine stops and signals {\em
done} when all the bread crumbs are eaten.  If the ant had no memory
than after eating the last crumb it would rotate indefinitely.
Therefore we should embed it with a memory of how many times it
rotated in the same spot in the search of an adjacent bread crumb.  If
the number of turns reaches four, all the bread crumbs are eated and
the ant can signal {\em done}.  Here is the state machine:
\begin{eqnarray*}
AntMemory &=& \{0,1,2,3,4\}
\\
BoardLocation &=& \naturals \times \naturals
\\
AntDirection &=& \set{N,E,W,S}
\\
Crumbs &\subseteq& BoardLocation
\\
AntLocation &=& BoardLocation
\\
Q &=& AntMemory \times (AntLocation \times AntDirection \times Crumbs)
\end{eqnarray*}

The transitions correspond to the three actions \{``go straight'',
``turn left'', ``done''\}.  We will use variables $q=(m,l,d,C)$ to
represent a state $q\in{Q}$ ($m\in{AntMemory}, l\in{AntLocation},
d\in{AntDirection}, C\in{Crumbs}$).  Let ${\sf Loc}(l,d)$ be a
function taking a location $l\in{AntLocation}$ and
$d\in{AntDirection}$ and returning $l'\in{AntLocation}$ s.t. $l'$ is a
location adjacent to $l$ in direction $d$.  In particular, if the ant
is in location $l$ and goes in direction $d$, it will come to location
$l'={\sf Loc}(l,d)$.  Let ${\sf Next}(d)$ be a function which picks
next direction of an ant which turns left, i.e. ${\sf Next}$ maps N to
W, W to S, S to E, and E to N.

\begin{itemize}
\item
{\sf go straight:}
$(m,l,d,C)\rightarrow(0,{\sf Loc}(l,d),d,C\setminus\{{\sf Loc}(l,d)\})$ if
${\sf Loc}(l,d)\in{C}$.
\item
{\sf turn left:} $(m,l,d,C)\rightarrow(m+1,l,{\sf Next}(d),C)$ if
${\sf Loc}(l,d)\not\in{C}$ and $m\neq{4}$.
\item
{\sf done:} If $m=4$, ant signals ``done''.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} A popular hand-held electronic game by Tiger 
Electronics called ``Lights Out'' is a $5\times5$ grid of buttons, each one
of which is either lighted or not.  The puzzle is to make all the
lights go out by pushing a sequence of buttons.  Pushing a button
toggles the state of the button pushed (lighted $\iff$ not lighted) and
all of its adjacent neighbors (not the diagonal neighbors).

The $5\times5$ game is a very large state machine involving millions
of states.  Thus let us consider instead the 3x3 game as shown:

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/lightsout.eps}}}
\bigskip

To win this game, we only need to press one button.  Pressing the top center
button will result in itself and the three neighbors turning off.

\begin{problemparts}
\problempart Describe this game as a state machine.  Don't draw every state;
             just describe the states and how you can move from one to another.

\solution

The state of this game could be represented as a nine bit string
$s=s_1...s_9$, with one bit $b_i$ per each button, saying whether that
button is lit ($b_i=1$) or not lit ($b_i=0$).  There can be many
conventions, but here we will assume that $s_1s_2s_3$ are the top row
buttons, $s_4s_5s_6$ the middle row, and $s_7s_8s_9$ the bottom row,
all left to right.  From every state $s$ there are nine transitions,
one per each button that can be pressed.  Note that if there is a
transition from $s$ to $s'$ then there is a transition involving the
same button from $s'$ to $s$.  The transitions from
$s=s_1s_2s_3s_4s_5s_6s_7s_8s_9$ lead to:
\begin{eqnarray*}
\overline{s_1}\overline{s_2}s_3\overline{s_4}s_5s_6s_7s_8s_9
&& \mbox{if button 1 is pressed}\\
\overline{s_1}\overline{s_2}\overline{s_3}s_4\overline{s_5}s_6s_7s_8s_9
&& \mbox{if button 2 is pressed}\\
{s_1}\overline{s_2}\overline{s_3}s_4{s_5}\overline{s_6}s_7s_8s_9
&& \mbox{if button 3 is pressed}\\
\overline{s_1}{s_2}{s_3}\overline{s_4}\overline{s_5}s_6\overline{s_7}s_8s_9
&& \mbox{if button 4 is pressed}\\
\mbox{etc...}
\end{eqnarray*}
where $\overline{0}=1$ and $\overline{1}=0$.


\problempart How many states are there?

\solution

Since each 9-bit string represents a state, there are $2^9=512$ possible states.

\problempart Suppose all nine buttons are lighted.  What is the fewest number
             of buttons we must push to make all nine go out?  Which buttons
             must we push?

\solution 

You can lit all buttons in 5 moves: pressing all corner
buttons (buttons 1,3,7 and 9) and the middle button (button 5).

\problempart Is every pattern of lights reachable?  Prove your answer. 

\solution

Yes, because you can toggle each button individually:
\begin{itemize}
\item
The middle button can be toggled with all the other buttons remaining
in the same state by pressing the four buttons in the four edge
centers (2,4,6,8) and the middle button (5).
\item
Each corner button can be toggled without changing any other buttons
by pressing that corner button, the two adjacent corner buttons, and
the two buttons in the centers of the two edges not adjacent to the
given corner.  For example, to change button 1 individually, we press
buttons (1,3,7,6,8).
\item
Each edge button can be toggled individually by pressing the middle
button and all the three buttons on the opposite edge.  For example,
to change button 2, we press (5,7,8,9).


\end{itemize}

\end{problemparts}



%%%%%%%%%%%%%%%%  S99 ps8


\problem {\bf (20 Points)}
In this problem we will prove the remarkable fact that
there exist mathematical functions that computers, no matter how powerful,
simply cannot compute.  We will do this through countability arguments.
\bparts
\ppart 

Show that the set of finite length binary strings is countable.

\solution{Let $B_n$ denote the set of binary strings of length $n$.
This set has exactly $2^n$ elements.  Therefore the set of finite
length binary strings $B=\bigcup_{n\in\naturals}B_n$ is a union of
countable number of finite sets.  We know from Lecture 13 that such
union is countable.

Namely, one can easily list all elements of $B$ by first listing the
elements of $B_1$, then the elements of $B_2$, then the elements of
$B_3$, etc,.  We can do this since each set $B_i$ has a finite number
of elements.


{\bf Alternative Solution:} 
Some students noticed that finite length binary strings can be thought
of as natural numbers represented base $2$.  Therefore, an injective mapping
from finite length binary strings to natural numbers can be constructed as
follows:
\[
f(b_0b_1b_2...b_n)= 2^{n+1}+(b_0+b_12+b_22^2+...+b_n2^n)
\]
i.e. we map a string of bits to a natural number that it represents
in binary, except that we add $2^{n+1}$ term to make sure that bit
strings of different length get mapped to a different natural number
(Otherwise strings $0010$, $010$, $10$ would all map to the same number).
You can check that $f$ is an injection from $B$ to $\naturals$ and hence
$B$ is countable.  

You can also easily modify $f$ to be a bijection if instead of adding
$2^{n+1}$ term to the right side, you add $2^{n+1}-1$.  }


\ppart 

From your answer to the previous part, 
what can you conclude about the countability of the set of all
computer programs?  

\solution{Since every computer program can be represented as a finite string of
bits (e.g. machine language code), it follows that the set of all
computer programs is countable.

Namely, the mapping which represents computer programs as finite
strings of bits is an injection.  Hence there is a surjection from the
set of finite strings of bits to the set of computer programs.  From
(a) we know that there is a surjection from the set of natural numbers
to the set of finite strings of bits.  By transitivity of surjective
mapping, there is a surjection between natural numbers and computer
programs.  Hence the set of all computer programs is countable.  }


\ppart 
Show that the set of {\em infinite} length binary strings is uncountable.

\solution{We construct a bijection from the set $B'$ of infinite length binary
strings to the power set of the natural numbers $P(\naturals)$.  Since
$P(\naturals)$ is uncountable, it will then follow that $B'$ is
uncountable.

We need to associate a subset of the naturals with each infinite
length binary string.  Let $b=b_0 b_1 b_2 b_3\ldots \in{B'}$ be an
infinite length binary string (here each $b_i \in \{0,1\}$).  We
associate with this string the set $f(b) = S = \{ i \ | \ b_i = 1 \}$.
That is, we include $i$ in $S=f(b)$ if and only if the $i$-th bit
position (from the left) of $b$ is 1.  Such mapping
$f:B'\rightarrow{P(\naturals)}$ is a bijection: It is an injection
because if two infinite length binary strings are different, then
clearly they map to different subsets.  Furthermore, it is a
surjection because for every subset $S\in P(\naturals)$, there is a
binary string $b$ s.t. $f(b)=S$, namely $b=b_0b_1b_2b_3\ldots$ where
$b_i$ is defined as $0$ if $i\not\in{S}$ and $1$ if $i\in{S}$.

{\bf Alternative Solution:} 

One can also show that the set $B'$ is uncountable directly by a
diagonalization argument.

Assume $B'$ is countable and let $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
be a list of all elements of $B'$.  By diagonalization, we will
construct an element $b=b_0b_1b_2b_3...\in{B'}$ s.t. $b\neq b^{(i)}$
for all $i\in\naturals$ as follows: $j$-th bit of $b$ is defined as
the opposite of the $j$-th bit of string $b^{(j)}$.  Obviously, so
defined $b$ is not equal to any $b^{(i)}$ from the list because for
every $i$, the $i$-th bit of $b^{(i)}$ is different than the $i$-th
bit of $b$.  Therefore, the list $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
is {\it not} a list of all elements in $B'$, and thus the assumption
that $B'$ is countable leads to a contradiction.  

}


\ppart 
A function is a {\em decision function} if it maps finite length bit
strings into the range $\{0,1\}$.  
% In other words, the function assigns a single bit 
% to every finite length bit string.  
Let $F$ be the set consisting of {\em all possible} decision
functions.  Show that set $F$ is uncountable.

\solution{From part (a), we know that there is a bijection from the set of
all finite length bit strings to the set of natural numbers (because
the set of all finite length bit strings was infinite and countable),
hence we can think of decision functions as mapping natural numbers to
the range $\{0,1\}$, i.e. to single bits.

It is easy to see a bijection between a set of such mappings and a
power set of the natural numbers.  Namely, we associate with a
decision function $f$ a set $S=\{i\in\naturals\mbox{ s.t. }f(i)=1\}$.
Clearly, this is an injection and a surjection.  Therefore, since the
power set of the set of natural numbers is uncountable then so is the
set of decision functions.

{\bf Alternative Solution:} 

We can give a bijection between the set of all decision functions and
the set of all infinite length bit strings, which by part (c), implies
that the set of decision functions is uncountable.  Let $f$ be a
decision function.  We map $f$ to an infinite length string as
follows.  We set bit $i$ of the string to be $f(i)$.  That is, our
infinite length bit string will be $f(1) f(2) f(3) \ldots $.  Now,
observe that this mapping is a bijection.  In particular, suppose we
have two different decision functions $f$ and $g$.  Since they are
different, they must give a different output on some particular input.
Suppose that this particular input is the number $j$.  That is,
$f(j)\neq g(j)$.  Then, the corresponding infinite length binary
strings will differ in the $j-th$ position.  This shows that the
function is injective.  Now, if we have an infinite length bit string
$b_0 b_1 b_2
\ldots$, then a decision function $f$ defined as
$f(0) = b_0, f(1) = b_1, f(2) = b_2, \ldots$, will be mapped to that
string.  Therefore, the mapping function is surjective.  Since it's
both injective and surjective, it is also bijective.


{\bf Alternative Solution 2:} 

Some students gave a diagonalization argument for why $F$ is
uncountable: Assume otherwise and let $\{f_1,f_2,f_3,...\}$ be the
list of all elements of $F$.  From part (a) we know that $B$, the set
of all finite length binary strings is countable, so there must exist
a bijection $g:B\rightarrow\naturals$.  Now, define a decision
function $f:B\rightarrow\{0,1\}$ as follows:
\[
f(s)=\mbox{ the opposite of }f_{g(s)}(s)
\]
Then $f$ is different from all $f_i$'s because for all
$i\in\naturals$, $h$ differs from $f_i$ on string $s=g^{-1}(i)$.


{\bf Alternative Solution 3:} 

One can also argue, as some students did, that $F$ is uncountable by
showing the bijection between $F$ and the set, $P(B)$, of all subsets of
$B$.  The bijection associates with $f\in{F}$ a set of strings $b \in B$
s.t. $f(b)=1$.  Then, since by part (a) there is a bijection between $B$
and $\naturals$, there must be a bijection between $P(B)$ and
$P(\naturals)$.  By transitivity of bijective relation between sets, there
is a bijection then between $F$ and $P(\naturals)$.  Hence $F$ is
uncountable.

}


\ppart 

A function is computable if there is a computer program that computes
it.  From your answers to the previous parts, prove that there is a
decision function that is not computable.
% STAS: repetitions...
% That is, there is no computer program that computes it.  

\ignore{ % STAS: Too much spoon-feeding...
(Hint: compare your answer from the second part to the the answer you
just got from the previous part)}

\solution{Since there are only countably many computer programs,
but uncountably many decision functions, there can be no surjection
from the set of computer programs to the set of decision functions (In
fact, this means that there is {\it more} decision functions than
computer programs).  In particular, if we associate a computer program
to a decision function which this program is computing\footnote{If a
program is not computing any decision function, associate it with a
trivial decision function $f(b)=0$, for all finite bit strings $b$.},
this association is not a surjection either.  Therefore there must be
some decision function which is not computed by any computer program.}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems

\end{problems}

\end(document}
