\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\funcs}[2]{[#1 \to #2]}
\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\BN}{\funcs{\naturals}{\set{0,1}}}

\begin{document}

\tutn{6}{9/30/99}{October 1,  1999}

\begin{problems}

\problem 

We use the notation $\funcs{A}{B}$ for the set of all functions from a
domain $A$ to codomain $B$.  A function in $\BN$ is called a \emph{Boolean
function on the natural numbers}.

We're interested in knowing about those Boolean functions which can be
evaluated by computer programs.  So assume we have computer programs which
can take any natural number as an input and then will run and produce 0 or
1 as an output.  Any such program, $\alpha$, defines a Boolean function
$f_\alpha \in \BN$ by the rule that $f_\alpha(n)$ is the output when
$\alpha$ is run on input $n$.  A function in $\BN$ is \emph{computable} if
it equals $f_\alpha$ for some program, $\alpha$.

We won't try to define exactly what a computer program is or how it works.
For our purposes, all we need agree on is that any computer program can be
represented as a finite string of ASCII characters.  This will be enough
for us to conclude that not all Boolean functions on the natural numbers
are computable.

\bparts

\ppart Show that the set of \emph{computable} Boolean functions on the
natural numbers is a countable set.

\solution{
Since programs are represented as ASCII strings, we need only show that
the set of all finite ASCII strings which represent programs is countable.
Since any subset of a countable set is countable, it's sufficient to show
that the set of \emph{all} finite ASCII strings is countable.

Now there are only a finite number (256) of ASCII symbols, so there are
only a finite number ($256^n$) of ASCII strings of length $n$.  The set of
all ASCII strings is the union over $n\in \naturals$ of the strings of
length $n$.  Since finite sets are countable, this is a countable union of
countable sets, which we know (from lecture and notes) is countable.}

\ppart Conclude that there is a Boolean function on the natural numbers
which is not computable.  In fact, conclude that there are an uncountable
number of such noncomputable functions in $\BN$.  \hint Problem Set 3,
Prob 1(b) establishes that $\BN$ is uncountable.

\solution{ Since there are countably many computable functions in $\BN$
but uncountably many functions altogether in $\BN$, there are ``more''
functions in $\BN$ than computable ones, so there must be one which is not
computable.

More precisely, ``more'' means there is no surjection from the set of
computable functions in $\BN$ onto all of $\BN$.  Now the identity mapping
which maps each computable function to itself determines a higher-order
function which has the \emph{computable} functions in $\BN$ as its domain
and has all of $\BN$ as it codomain; its range, of course, is exactly the
computable functions.  Since this mapping cannot be a surjection, there is
some element in codomain $\BN$ not in its range.  So this element is a
Boolean function on the natural numbers which is not computable.

In fact, if there were only a countable number of noncomputable functions
in $\BN$, then $\BN$ would be the union of two countable sets---the
computable ones and the noncomputable ones---and therefore would be
countable, contradicting the result from Problem Set 3.}

\eparts


\problem 

Let $\{0,1\}^n$ be the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and codomain
$\{0,1\}^n$?


\solution{

There are $2^m$ elements in the domain.  There are $2^n$
elements in the codomain.  For every element in the domain, we thus have
$2^n$ choices for what we can map it to.  Therefore, by the Product Rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
codomain $\{0,1\}^n$.}

\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if $f(x) = x$.
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} fixed
points?

\solution{
To count all the functions without fixed points, we observe that such a
function could map each element of the domain to any element but itself,
that is, to any one of the remaining $2^n - 1$ elements in the codomain.
There are $2^n$ elements in the domain, so, by Product Rule there are
$(2^n-1)^{2^n}$ such functions with no fixed points.}

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\solution{
There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no
fixed points.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have
at least one fixed point.}

\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\solution{ Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself---thus it can be mapped to exactly $2^n -
1$ possible spots.  So by the Product Rule, there are $(2^n - 1)^{2^n -
1}$ functions with exactly this particular fixed point and no other.  Now
there are $2^n$ possible choices for the particular fixed point, so by the
Sum Rule, the total number of functions with exactly one fixed point is
$2^n(2^n - 1)^{2^n - 1}$.}

\eparts

\end{problems}
\end{document}
