
\documentclass[11pt,letter]{article}
\pagestyle{plain}
\usepackage{latexsym}
%\textwidth15cm
%\newtheorem{lemma}{Lemma}
\newtheorem{statement}{Proposition}
\newtheorem{exercise}{Exercise}
%\newtheorem{theorem}{Theorem}
%\newtheorem{prop}{Proposal}
%\newtheorem{property}{Property}
%\newtheorem{corollary}{Corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% comments and stuff / temporary %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\lastcorrections}%
{{\vskip  0.2in
\begin{sloppypar}
    \baselineskip -0.2in
    \tiny\bf\noindent Last Corrections:\\   %%%%% keep this info
                                            %%%%% current
larry: Wed Apr 16 01:04:04 PDT 2003\\
larry: Thu Apr 17 07:21:41 PDT 2003
\end{sloppypar}
}}

\newcommand{\margincomment}[1]%
    {{%
      \marginpar{{\tiny\begin{minipage}{0.5in}
                       \begin{flushleft}
                          {#1}
                       \end{flushleft}
                       \end{minipage}
                }}
    }}

%\renewcommand{\cite}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints
%\renewcommand{\ref}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% useful editing macros %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\etal}{{\em et al.~\/}}
\newcommand{\tH}{{\rm th}}
\newcommand{\etc}{{\em etc.\/}}
\newcommand{\ie}{{\em i.e.\/}}
\newcommand{\eg} {{\em e.g.\/}}
\newcommand{\larry}{$\calL^3$}
\newcommand{\mch}{\mbox{${\cal MC}h$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% lengths and sizes %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\setlength{\evensidemargin}{0.1in}
%\setlength{\oddsidemargin}{0.1in}
%\setlength{\textwidth}{6.7in}
%\setlength{\topmargin}{0.2in}
%\setlength{\textheight}{8.7in}
%\setlength{\headheight}{0in}
%%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}

%\parskip=.080in
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\textwidth}{6.5in}
%\setlength{\topmargin}{0.0in}
%\setlength{\textheight}{8.8in}
%%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}
\addtolength{\textheight}{1.0in}
\addtolength{\topmargin}{-0.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
%\addtolength{\textheight}{0.6in}
%\addtolength{\topmargin}{-0.4in}
%\addtolength{\textheight}{0.0in}
%\addtolength{\topmargin}{-0.6in}
%\addtolength{\textwidth}{1.0in}
%\addtolength{\oddsidemargin}{-0.5in}
%\addtolength{\evensidemargin}{-0.5in}
%\renewcommand{\baselinestretch}{1.16}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% all sorts of letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bfx}{{\bf x}}

\newcommand{\bara}{{\bar a}}
\newcommand{\barm}{{\bar m}}
\newcommand{\barA}{{\bar A}}

\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\barr}{{\bar r}}

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calJ}{{\cal J}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calQ}{{\cal Q}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calV}{{\cal V}}
\newcommand{\calW}{{\cal W}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calY}{{\cal Y}}
\newcommand{\calZ}{{\cal Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% maly %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\maly}[1]{{\scriptscriptstyle#1}}
\newcommand{\malyz}{{\maly{0}}}
\newcommand{\malyone}{{\maly{1}}}
\newcommand{\malytwo}{{\maly{2}}}
\newcommand{\malythree}{{\maly{3}}}
\newcommand{\malyhalf}{{\mbox{$\maly{\frac{1}{2}}$}}}
\newcommand{\malylambdahalves}{{\mbox{$\maly{\frac{\lambda}{2}}$}}}
\newcommand{\malyA}{{\scriptscriptstyle A}}
\newcommand{\malyB}{{\scriptscriptstyle B}}
\newcommand{\malyC}{{\scriptscriptstyle C}}
\newcommand{\malyD}{{\scriptscriptstyle D}}
\newcommand{\malyE}{{\scriptscriptstyle E}}
\newcommand{\malyF}{{\scriptscriptstyle F}}
\newcommand{\malyG}{{\scriptscriptstyle G}}
\newcommand{\malyH}{{\scriptscriptstyle H}}
\newcommand{\malyI}{{\scriptscriptstyle I}}
\newcommand{\malyJ}{{\scriptscriptstyle J}}
\newcommand{\malyK}{{\scriptscriptstyle K}}
\newcommand{\malyL}{{\scriptscriptstyle L}}
\newcommand{\malyM}{{\scriptscriptstyle M}}
\newcommand{\malyN}{{\scriptscriptstyle N}}
\newcommand{\malyO}{{\scriptscriptstyle O}}
\newcommand{\malyP}{{\scriptscriptstyle P}}
\newcommand{\malyQ}{{\scriptscriptstyle Q}}
\newcommand{\malyR}{{\scriptscriptstyle R}}
\newcommand{\malyS}{{\scriptscriptstyle S}}
\newcommand{\malyT}{{\scriptscriptstyle T}}
\newcommand{\malyU}{{\scriptscriptstyle U}}
\newcommand{\malyV}{{\scriptscriptstyle V}}
\newcommand{\malyW}{{\scriptscriptstyle W}}
\newcommand{\malyX}{{\scriptscriptstyle X}}
\newcommand{\malyY}{{\scriptscriptstyle Y}}
\newcommand{\malyZ}{{\scriptscriptstyle Z}}
\newcommand{\smallworkfs}{{\scriptstyle\workfs{}}}
\newcommand{\smalld}{{b}}
\newcommand{\smallrm}{{\rm\small}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% delimiters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\parend}[1]{{\left( #1  \right) }}
\newcommand{\spparend}[1]{{\left(\, #1  \,\right) }}
\newcommand{\angled}[1]{{\left\langle #1  \right\rangle }}
\newcommand{\brackd}[1]{{\left[ #1  \right] }}
\newcommand{\spbrackd}[1]{{\left[\, #1  \,\right] }}
\newcommand{\braced}[1]{{\left\{ #1  \right\} }}
\newcommand{\leftbraced}[1]{{\left\{ #1  \right. }}
\newcommand{\floor}[1]{{\left\lfloor #1\right\rfloor}}
\newcommand{\ceiling}[1]{{\left\lceil #1\right\rceil}}
\newcommand{\barred}[1]{{\left|#1\right|}}
\newcommand{\doublebarred}[1]{{\left|\left|#1\right|\right|}}
\newcommand{\spaced}[1]{{\ #1\ }}
\newcommand{\suchthat}{{\spaced{:}}}

\newcommand{\bracedtwo}[2]{\braced{\begin{array}{c}
                                        #1 \\ #2
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedtwo}[2]{\left\{\begin{array}{l}
                                        #1 \\ #2
                                    \end{array}\right.
                           }
\newcommand{\bracedthree}[3]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedthree}[3]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3
                                    \end{array}\right.
                           }
\newcommand{\bracedfour}[4]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfour}[4]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}\right.
                           }
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\bracedfive}[5]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfive}[5]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}\right.
                           }

\newcommand{\mycase}[1]{\smallskip\noindent \mbox{Case #1:}}

\newcommand{\ignore}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{observation}{Observation}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{conjecture}{Conjecture}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}
\newenvironment{example}{\medskip\noindent{\it Example:\/}}{$\Box$\vskip 0.1in}
\newenvironment{problem}{\medskip\noindent{\it Problem:\/}}{$\Box$\vskip 0.1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% some general mathematical symbols %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\half}{{\mbox{$\frac{1}{2}$}}}
\newcommand{\onehalf}{{\half}}
\newcommand{\onethird}{{\mbox{$\frac{1}{3}$}}}
\newcommand{\twothirds}{{\mbox{$\frac{2}{3}$}}}
\newcommand{\fourthirds}{{\mbox{$\frac{4}{3}$}}}
\newcommand{\onefourth}{{\mbox{$\frac{1}{4}$}}}
\newcommand{\fivefourths}{{\mbox{$\frac{5}{4}$}}}
\newcommand{\onesixth}{{\mbox{$\frac{1}{6}$}}}

\newcommand{\Comp}{{\parend{1+e^{-\malyhalf}}}}

\newcommand{\update}{{\wedge}}
\newcommand{\opt}{{\mbox{\it opt}}}
\newcommand{\cost}{{\mbox{\it cost}}}
\newcommand{\back}{{\mbox{\it back}}}
\newcommand{\lood}{{\mbox{\it load}}}
\newcommand{\congestion}{{\mbox{\it congestion}}}
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\malyopt}{{\mbox{\tiny\it opt}}}
\newcommand{\adv}{{\mbox{\it adv}}}
\newcommand{\malyadv}{{\mbox{\tiny\it adv}}}

\newcommand{\eps}{\epsilon}
\newcommand{\adversary}{{\mbox{\it R}}}
\newcommand{\Exp}{{\mbox{\it Exp}}}
\newcommand{\reals}{{\bf R}}
\newcommand{\tendsto}{{\rightarrow}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% Temporary macros %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  \newcommand{\Ref}[1]{\ref{#1} {\rm \{#1\}}}
  \newcommand{\Ref}[1]{\ref{#1}}
%  \newcommand{\Cite}[1]{\cite{#1} {\rm \{#1\}}}
  \newcommand{\Cite}[1]{\cite{#1}}
% \newcommand{\Label}[1]{\label{#1} \mbox{$\backslash$ {\rm label\{#1\}}}}
  \newcommand{\Label}[1]{\label{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\today}{}

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

\begin{document}

\title{Problems and Languages}
\author{Lawrence L Larmore}
%\maketitle
%\begin{abstract}
%The concept of a {\em problem\/} is related to the theory of
%formal languages.
%\end{abstract}
%{\bf Keywords:} Problem, Complexity \\

\section*{Problems and Languages}

\subsection*{Encoding of a Set\/}
Let $S$ be any set, and let $\Sigma$ be any alphabet.  An {\em encoding\/}
of $S$ over $\Sigma$ is defined to be a one-to-one function $S\to\Sigma^*$.
Given such an encoding, the {\em language\/} of $S$ is defined to be
the set of all strings which are encodings of members of $S$.

When we say that a set $S$ is {\em regular\/}, {\em recursive\/},
{\em polynomial time\/}, \etc, we always have a specific encoding of $S$
in mind, and we mean that the language of $S$ is {\em regular\/}, {\em
recursive\/}, {\em polynomial time\/}, \etc.

For most applications, $S\subseteq U$, where $U$ is some universal set
which has a given encoding, which $S$ inherits.

For example, the set of natural numbers can be encoded over
$\Sigma = \braced{1}$ by using {\em unary notation\/}, \ie, the number
$n$ is encoded as the string $1^n$.  Then, for example, the set of
multiples of 3 is regular, because the language $\braced{1^{3i}}$ is
a regular language.

\subsection*{Encoding of a Problem\/}
A {\em problem\/} consists of a set of {\em instances\/}, where for
each instance, there is a {\em solution\/}.  Fix an encoding of both
instances and solutions of a given problem.  Then, the problem
is a function from strings to strings, \ie, if $w$ is the encoding of
an instance of the problem, $f(w)$ is the encoding of of the solution
of that instance.

Consider, for example, addition of natural numbers.  A problem instance
is encoded as a non-empty string of digits, followed by the symbol $+$,
followed by another non-empty string of digits, such as ``$43+517$".
The solution to a problem instance is a string of digits, in this case,
``$560$".

\subsection*{Encoding of a 0-1 Problem\/}

A {\em 0-1 problem\/} is defined to be a problem where, for each
instance, the solution is either true (1) or false (0).
In this special case, the {\em language\/} of the problem is defined
to be the set of encodings of problem instances for which the solution
is true.  In this case, we usuall identify the problem with its language.

For example, we can define a 0-1 addition problem to be strings of symbols
which encode addition facts, such as ``$43+517=560$".

\subsection*{Encodings of Numbers}

An encoding of numbers is called a {\em numeration system\/}, and
the encoding of one number is called a {\em numeral}.

Standard numeration systems for $\calN$, the set of natural numbers,
include the unary, binary, and decimal numeration systems, over the
alphabets $\braced{1}$, $\braced{0,1}$, and
$\braced{0,1,2,3,4,5,6,7,8,9}$, respectively.
We can encode the set of integers by using the additional symbol ``$-$"
for negative numbers.

\begin{exercise}{\rm
The knapsack problem with integer input is well-known to
be $\calN\calP$-complete if binary or decimal encoding is used for the inputs.
Prove that the problem is polynomial time if unary encoding is used for
the inputs.}
\end{exercise}

\subsection*{Rational Numbers}

Let $\calQ$ be the set of rational numbers.  We can encode $\calQ$ by
using {\em fractions\/}, where each rational number is written as
the encodings of two integers separated by the symbol ``$/$", such as
``$23/57$".  To ensure uniqueness, we insist that the denominator never
be negative, and that the fraction is reduced to the lowest terms.

\subsection*{Real Numbers}
Let $\Re$ be the set of real numbers.  There is no encoding of $\Re$,
since it is an uncountable set.  However, there is a way to express
every real number as a 0-1 problem.

Given a real number $x$, let $\calQ_x\subseteq\calQ$ be the set of
all rational numbers less than or equal to $x$.
Intuitively, if we ``know" $\calQ_x$, then we ``know" $x$, since
two real numbers $x$ and $y$ can be distinguished by a rational number
that lies between them.  We then identify the real number $x$ with
the set $\calQ_x$, which means, with the language of all encodings
of members of $\calQ_x$.

Thus, for instance, if we say $x$ is {\em recursive\/}, we mean that the
language of all encodings of members of $\calQ_x$ is recursive.

For example, every rational number can be considered to be a real
number, and as such, is trivially recursive, since it is easy to
decide whether a given fraction is less than or equal to another
given fraction.

As another example, $\sqrt{2}$ is recursive, since the truth of the
statement $n/m \le \sqrt{2}$ can be easily decided.

The well known transcendental number $\pi$, the ratio of the circumference
of a circle to its diameter, is also recursive.
Hint: $\frac{\pi}{4} = \sum_{i=0}^\infty(-1)^i\frac{1}{2i+1}$.

\begin{exercise}{\rm
 Prove that a real number $x$ is recursive if and only if
there is a machine that runs forever, writing the decimal digits
of $x$ onto an output tape.}
\end{exercise}

\begin{exercise}{\rm
Let $S$ be a set of natural numbers.  Let  $x_S\in\Re$ be
defined by
\begin{eqnarray*}
x_S &=& \sum_{i\in S}2^{-i}
\end{eqnarray*}
Prove that $x_S$ is recursive if and only if $S$ is recursive.}
\end{exercise}

Note: since not all sets of natural numbers are recursive, not all
real numbers are recursive.

\begin{exercise}{\rm
Suppose that $x$ is a real number, and that there exists
a machine $M$ that runs forever, printing a sequence of rational
numbers that converges to $x$.  Does this prove that $x$ is recursive?
Prove or give a counter-example.}
\end{exercise}

\end{document}


