introduction1.tex
\section{Introduction}

The main goal of this paper is to provide a simple definition which would capture 
the intuitive notion of whether $f: \RR \ra \RR$ is an ``easily" computable function.

There are two main currently existing approaches to the computability and complexity of 
real functions. One is the BSS approach, where algebraic operations are performed on real 
numbers that are stored with infinite precision. This approach is described in \cite{BSS} and 
\cite{BCSS}.  The other approach, which we call bit-computability, goes all the way back to the 
Polish school in the 1930-50s, and can be formulated best as: ``given a good rational approximation of $x$, compute a good rational approximation
of $f(x)$". More recent references on the subject include \cite{Kobook} and \cite{WeiBook}.

The quality of a given definition for computability of real functions (or any notion 
of computability in general) can be judged by how well it matches the intuitive notion 
of ``easy" vs. ``hard" vs. ``impossible". For example, in the discrete case, it it much easier to add two 
numbers $x+y$ (an operation that takes linear time in the size of the input), than factor 
an integer $n$ (an operation most believe requires time superpolynomial in the size of the 
input), and solving the Halting Problem is {\em truly} impossible (for example, the Goldbach conjecture 
can be presented as a simple instance of the Halting Problem). We keep this in mind while examining the different approaches to the computability of real functions. 

We consider some reservations to both approaches mentioned above. One complaint 
about the BSS approach is that it is too focused on the algebraic simplicity of 
the function $f$, allowing only piecewise-semialgebraic functions to be computable. 
In particular,  simple functions such as $x \mapsto e^x$ and $x \mapsto \sqrt{x}$ are not computable in 
this model (cf. \cite{Emperror}). There are also problems in the opposite direction:
this model classifies all the constant functions $x\mapsto a$, which are extremely simple algebraically,
as computable. However, there are infinitely many real $a$'s such that computing $a$ with an 
arbitrarily good precision would allow us to solve the Halting Problem. We will discuss more 
of these issues, and ways to `fix' them in section \ref{BSSsection} below.

On the other hand, in the bit computability model all the computable functions must be 
continuous. Thus even the simplest step function $s_0 (x)=1$ if $x\ge 0$ and $f(x)=0$ if $x < 0$ 
is not computable in this model. This function is extremely simple from the mathematical point of view
(involving only the constants $0$ and $1$ and the comparison operations in its description), hence it 
would be reasonable to expect it to be computable at least in some sense. For a real function $f$
it is hard to say whether it is uncomputable in this model because it is ``difficult" in some 
profound way, or because it is just discontinuous in one or a few points. It would also be nice to 
have a setting in which, by analogy with the discrete case, we have a strong connection between 
the computability of  a set $A$ and the computability of its characteristic 
function $\chi_A$. Another problem is how to 
properly define the computability of  multi-valued functions such as $\sqrt{~} : \CC \ra \CC$.
It is obvious that such a simple function should be computable, but it doesn't 
have a continuous (and hence bit-computable) branch defined on the entire complex plane $\CC$. 

We deliberately restrict our discussion to the simple case where the 
functions are from
$\RR^k$ or from a simple rectangle such as $[0,1]^k$ to $\RR^\ell$. The 
goal being not to 
give the broadest definitions and prove the most general theorems, but rather provide a simpler discussion 
accessible to a broader audience. We will try to use only basic background in the computability 
and complexity theory and in the topology of $\RR^k$. 

The paper is organized as follows. In section \ref{TTCsection} we give
an introduction to the bit model of computation for sets, along with 
some properties and examples. This section can be viewed as 
a separate simple introduction to the subject. In section \ref{BSSsection} we discuss 
the BSS computability for sets, and propose three natural modifications 
to the model that make BSS-computability equivalent to  bit-computability. 
In section \ref{weakcomp} we introduce another notion of set-computability -- weak 
computability, and show its equivalence to the standard bit-computability. 
Sections \ref{BSSsection} and \ref{weakcomp} can be read independently. 
In section \ref{mysect} we use results from sections \ref{BSSsection} and 
\ref{weakcomp} to propose a new computability and complexity definition
for real functions extending the computability in both models, and 
the classical complexity in the case of continuous functions. 
