\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 688: Theory of Computability and Complexity \hrulefill}
\markboth{\headlineaux}{\headlineaux}


\newcommand{\outdate}{October, 1992}
\newcommand{\naturals}{\mbox{\bf N}}
\newcommand{\compose}{\circ}
\newcommand{\twocases}[4]{\left\{\begin{array}{ll}#1&#2\\#3&#4\end{array}\right.}
\newcommand{\indexof}[1]{[#1]}
\newcommand{\QED}{\hfill$\Box$}

\newtheorem{theorem}{Theorem}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\noindent{\small\sc Burt Rosenberg \hfill University of Miami \hfill Fall 1992 }

\section*{Recursion is while-program computable}



We show that recursively defined functions are while-program
computable via least-upper-bound of partial functions by extension
ordering. The purpose is to combine approaches from Kfoury, Moll 
and Arbib, ``A Programming Approach to Computability'', hereafter
abbreviated KMA,
thus introduce the abstract apparatus of posets of functions
without diverging the discussion into denotational semantics.

Recursive programs are those which call themselves. Non-recursive
programs with subroutine calls can be treated as macros. Therefore
we reduce immediately to the case of self-recursion. We let the
program refer to itself by a special symbol created and reserved
for this purpose. We shall use the symbol R. To transform programs
to indices, we need to include R in Table~1 on page~46 of KMF.
We will agree that R has decimal representation 54.

Let's take as running example the factorial program,
\[ \mbox{fact}(n) = \twocases{1}{n=0}{n\mbox{ fact}(n-1)}{n>0} \]
written as,
\begin{verbatim}
    begin
      if X1=0 then x1:=1
      else begin
        x2:=x1 ; x1:=pred(X1);
        R; {recursion symbol}
        X1:=X2*X1
      end
    end 
\end{verbatim}
There are four problems to contend with,
\begin{enumerate}
\item How can we place a function inside itself?
This will be resolved by defining a substitution function.
\item Straight textual substitution of the function inside of itself
will cause a conflict of variable names. We will define a function
which renames variable to avoid the problem.
\item The renaming and substitution must proceed an infinite number of
times in order to reach the function. We will approach this problem
two ways. First by the notion of a limit function, and second by the
definition of a mechanism capable of substituting the function inside
itself an arbitrary but finite number of times {\em on demand.}
\item Assigning semantics to R. Having introduced this symbol,
we need to say what happens when while-program execution reaches this
symbol. We shall avoid this by removing all references to R before
actually calling the result a while-program.
\end{enumerate}
We will restrict our attention, with loss of generality, to unary functions.

\subsection*{Substitution and Renaming}

Let the {\em Recursion Kernel}, abbreviated RK, be the 
program which defines the recursive function perhaps using the special
symbol R. Given a program P, such as RK, its encoding as an
integer will be denoted $\indexof{P}$. The program encoded by
integer $i$ will be denoted $P_i$. So, for instance,
\[ RK = P_{\indexof{RK}}.\]

Define a number theoretic function,
\[ \begin{array}{llcl}
\mbox{sub}:& \naturals^2 & \rightarrow & \naturals \\
&(i,j) &\mapsto& \left\{\parbox{3in}{Form program $P$ by
replacing each \verb.R. in $P_i$ with $P_j$ and return $\indexof{P}$}\right. \\
\end{array}\]
For instance, the following program is sub,
\begin{verbatim}
    begin
      X3:=0 ; {this will be the output program}
      while X1<>0 do  {while there are symbols in the}
      begin           {input program...}
        X4:=head(X1) ;
        if X4<>'R' then X3:=X3||X4 {pass along symbol}
        else X3:=X3||X2 ; {insert Pj}
        X1:=tail(X1)
      end ;
      X1:=X3
    end
\end{verbatim}

Next we define a function 
\[ \begin{array}{llcl}
\mbox{ren}:& \naturals^2 & \rightarrow & \naturals \\
   &(i,k) &\mapsto& \left\{\parbox{3in}{Returns $\indexof{P}$ where P is
the program resulting from renaming all variables Xj in $P_i$,
except X1, to X(j+k-1).}\right. \\
\end{array}\]
That is,
\begin{eqnarray*} X1 &\mapsto& X1 \\ X2&\mapsto&X(k+1)\\X3&\mapsto&X(k+2)\\
&\vdots&\\
\end{eqnarray*}
It would be difficult to give an explicit while-program for this function,
however the following description is precise. Scan $P_i$ looking for the
symbol X. For each non-X symbol, simply output the symbol unchanged.
If X is found, collect into a string $\alpha$ the unbroken string of digits
following X and output X followed by the string $\beta$ derived from $\alpha$
as follows. If $\alpha$ is empty or is the string '1', then $\beta=\alpha$.
Else convert $\alpha$ to integer, add $k-1$ to this integer, and $\beta$ is the string
representation of the sum.

As an example, if the factorial function defined above is taken as the recursion
kernel,
\[ \mbox{sub}( \indexof{RK}, \mbox{ren}( \indexof{RK}, 2 ) ) \]
would be,
\begin{verbatim}
    begin
      if X1=0 then X1:=1
      else begin
        X2:=X1; X1:= pred(X1);
        begin
          if X1:=0 then X1:=1
          else begin
            X3:=X1; X1:=pred(X1) ;
            R;
            X1:=X3*X1
          end
        end;
        X1:=X2*X1
      end
    end
\end{verbatim}
This is not a valid while-program since R is semantically undefined. We
correct that problem by simply causing the ``call'' to R loop indefinitely.

Let $\indexof{\bot}$ by the index of some empty function. We intend to remove all
references to R by substitution in $\indexof{\bot}$. Returning to the
factorial example, 
\[\begin{array}{ccl}
\mbox{sub}( \indexof{RK}, \indexof{\bot} ) &\mbox{ yeilds }& f_1 = \twocases{1}{n=0}{\bot}{\mbox{else,}} \\
\mbox{sub}( \mbox{sub}( \indexof{RK}, \mbox{ren}( \indexof{RK}, 2 ) ), \indexof{\bot} )
  &\mbox{ yeilds } & f_2 = \twocases{1}{n=0,1}{\bot}{\mbox{else,}} \\
&\vdots & \end{array}\]
Or in general,
\[ f_0 \le f_1 \le f_2 \le \ldots \le F \]
where $f_0=\bot$, by convention, and $F$ is the ``limit'' function of the sequence. It
is the recursive function we seek, defined everywhere in the domain by an ever-expanding
sequence of functions defined on larger and larger portions of the domain.
We need to make the definition of a limit function precise and then show that it
is while-program computable.

\subsection*{Interlude on Posets}

Recall that a poset $\{S,\ge\}$ is a set $S$ with a reflexive, anti-symmetric, transitive
relation $\ge$. Our most important example for this article is the poset of partial
functions by extension ordering. We most prove that this is a poset.
\begin{theorem} For any partial function $f$, $f\ge f$.
If $f$ and $g$ are partial functions and $f\ge g$ and $g \ge f$, then
$f=g$. If $f$, $g$ and $h$ are partial functions, and $f \ge g$ and $g\ge h$, then $f \ge h$.
\end{theorem}
The proof is an exercise in the definition of extension ordering.

Posets can have two operations, the {\em meet} and the {\em join}. The meet of two
elements $a$ and $b$ is the greatest lower bound of $a$ and $b$. That is, it is
an element $c$ such that $c\le a$, $c\le b$ and it is the greatest
such element. It is not necessary for a meet to exist, that depends on the
particular poset. If such a $c$ does exist, one writes $c = a\wedge b$.
In the poset of partial functions, given any two partial functions, their meet always exists,
see the related problem on the midterm.
However, the least upper bound of two functions is generally not definable. 
For instance, if $f$ and $g$ are two distinct total functions 
then the existence of any $h$ such that $h\ge f$ and $h\ge g$ would force $f=g$, contradicting
our assumption.
However, if $f\le g$ then the least upper bound does exist and is equal to $g$.
Proof: $f\le g$ and $g\le g$ so $g$ is an upper bound, but if $h$ is also an upper 
bound then $h\ge g$. So $g$ is the least upper bound.
Then $g$ is called the {\em join} of $f$ and $g$ and is written $g=f\vee g$.

Not only are finite joins definable if the two functions are compatible in extension ordering,
so are infinite joins.
\begin{theorem} Let ${\cal F} = \{\,f_1, f_2, f_3, \ldots \,\}$ be a perhaps infinite family of
partial functions such that for any integers $i$ and $j$ for which $i\le j$ then $f_i\le f_j$.
Then a unique least upper bound of the family exists and is written,
\[ \bigvee_i f_i = F \]
\end{theorem}
{\sc Proof:} We define a function $F$ and show that it is the least upper bound of the family
$\cal F$.
\[ F(n) = \twocases{f_i(n)}{f_i(n) \mbox{ exists for some $i$}}{\bot}{\mbox{for no $i$ is $f_i(n)$
defined}.} \]
The function $F$ is well-defined: either $f_i(n)$ is defined for some $i$ or
for no $i$. If it is defined for more than one $i$, the value at $n$ agrees. It is
necessary to show that for all $i$, $F\ge f_i$. Suppose $f_i(n)$ is defined. Then from
the definition of $F$, $F(n)$ is defined and $F(n)=f_i(n)$. So $F\ge f_i$ for any $i$.
It is also necessary to show that if $G\ge f_i$ for all $i$, then $G\ge F$. Suppose $F(n)$ is
defined. Then $f_i(n)$ is defined for some $i$. Because $G\ge f_i$, $G(n)$ is defined as
well. And $G(n)=f_i(n)=F(n)$. So $G\ge F$. \QED

\subsubsection*{Examples}
The integers with the usual ordering is a poset. A finite meet always exists,
\[ a \wedge b = min(a,b),\]
as does a finite join,
\[ a\vee b = max(a,b).\]
However an infinite join does not always exist even if it is of a family $\{\,a_1, a_2, \ldots\,\}$
for which $i\le j$ implies $a_i\le a_j$. However, the set of integers with a new element
called infinity does always have infinite joins,
\[ \bigvee_i a_i = \twocases{\max_i\{a_i\}}{\mbox{if there is a finite such maximum}}
{\infty}{\mbox{if the $a_i$ are unbounded}}\]

Infinite joins do not always exist for the poset of the rationals with usual size ordering. 
A sequence of rationals can be made to converge on an irrational, say pi or the square root
of 2. However, a bounded set of reals does always have a least upper bound and this is
an important property of the reals. For instance, a circle can be approximated
by a series of inscribed polygons, each approximating the circle more closely than the
previous. The areas of these polygons form an increasing, bounded sequence
$a_1, a_2, \ldots$ whose least upper bound is said to be the area of the circle.

In the same way, if $f_0 \le f_2 \le f_2 \le \ldots$ is the sequence of functions
approximating the recursive function $F$, we want to show that $F$ is the least upper
bound of the $f_i$. Thinking about the meaning of recursion, a recursive program is
defined at input $n$
if and only if after a finite number of calls to itself the processing of input $n$
reaches a level where the calculation can be performed with no further recursion.
That is, if and only if there exists and $i$ for which $f_i(n)$ is defined. And this
is exactly the definition if $F = \vee_i f_i$. 

Therefore, to prove that recursion is no more powerful than while-programs we need to
show that given a {\em certain} sequence of functions computable by while-programs,
their join is also computable by while-programs.  It is not enough just that
this sequence is ascending, in the sense $i\le j$ implies $f_i\le f_j$.
Because any function
is the least upper bound of a set of functions with finite but increasing domain, and
any function of finite domain is computable.
We shall show that under the hypothesis that the sequence of
functions is effectively enumerable, then the join is computable.

\subsection*{Main Theorem and Application}

In this section the technique of dovetailed computation is used to prove the following
theorem. The close of this section will argue its relevance for the major result of this
article.

\begin{theorem} Let ${\cal F} = \{\, f_1, f_2, \ldots\,\}$ be an effectively enumerable
sequence of computable functions such that $i\le j$ implies $f_i\le f_j$. Then
$\vee_i f_i$ is computable.
\end{theorem}

{\sc Proof:} 
Recall from KMA that there exists a universal while-program for unary functions,
\[ \Phi(x,y) = f_x(y). \]
The proof was constructive, demonstrating a while-program which calculated
for any pair of integers $x, y$ the output of program $P_x$ on input $y$. The
code can be modified to form a new function $\Phi(x,y,z)$ such that on input
triple $(x, y, z)$ the code:
\begin{itemize}
\item simulates $P_x(y)$ for $z$ steps;
\item if the simulated program halts on or before $z$ steps, a special {\em haltflag} is set
true, else the flag is false;
\item in either case the program halts and the pair (X1, {\em haltflag}) is considered the output.
\end{itemize}
Because the family $\cal F$ is effectively enumerable, let $ee:\naturals\rightarrow\naturals$
be a total function for which $f_i = P_{ee(i)}$.
Our aim is to use dovetail through all pairs of integers, $(i,j)$, running 
the $i$-th program for $j$ steps. To to this, let
$\tau:\naturals^2\rightarrow\naturals$ be a computable bijection and $\pi_1,\pi_2:\naturals
\rightarrow\naturals$ two functions ``inverting'' $\tau$ in the sense that,
\[ i = \tau( \pi_1(i), \pi_2(i) ). \]
Then we shall run all programs for all number steps using the following program,
\begin{verbatim}
  begin
    i:=0;
    haltflag:=false;
    while not haltflag do begin
      j:=ee(pi1(i));
      N:=pi2(i);
      Phi(j,X1,N);
      i:=succ(i);
    end
  end
\end{verbatim}
If there is any program $P_j$ which halts on $x1$, it does so in $N$ steps. So
for the appropriate $i$, haltflag will be set true and X1 will have the proper output
for having computed $P_j(x1)$. \QED

\begin{theorem} Recursive programs are computable by while-programs.
\end{theorem}
{\sc Proof:} It only remains to show that the sequence of functions whose limit defines
the recursive function is effectively enumerable. The enumerating program is,
\begin{verbatim}
    begin
      if X1=0 then X1:=#B
      else begin
        ktot:=k;
        r:=#RK;
        while x1>1 do
        begin
          r:=sub(r,ren(#RK,ktot));
          ktot:=ktot+k;
          X1:=pred(X1)
        end;
        X1:=sub(r,#B)
      end
    end
\end{verbatim}
Where \verb.#B. is $\indexof{\bot}$, \verb.#RK. is $\indexof{RK}$ and $k$ is the largest
integer such that Xk appears in the recursive kernel RK. \QED
                
\end{document}