\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{partial recursive function} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{constructivism_realizability_computability}{}\paragraph*{{Constructivism, Realizability, Computability}}\label{constructivism_realizability_computability} [[!include constructivism - contents]] \hypertarget{deduction_and_induction}{}\paragraph*{{Deduction and induction}}\label{deduction_and_induction} [[!include deduction and induction - contents]] \hypertarget{foundations}{}\paragraph*{{Foundations}}\label{foundations} [[!include foundations - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak \noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak \noindent\hyperlink{the_ackermann_function}{The Ackermann function}\dotfill \pageref*{the_ackermann_function} \linebreak \noindent\hyperlink{busy_beaver_function}{Busy Beaver function}\dotfill \pageref*{busy_beaver_function} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} A \textbf{partial recursive function} (often ``[[computable function]]'', but see there for disambiguation) is a [[partial function]] of [[natural numbers]] which can be [[definition|defined]] by an [[algorithm]] or computer [[program]] (e.g., a [[Turing machine]]), taking finitely many [[natural numbers]] as inputs, and which on input may run forever, but otherwise eventually halts and returns a natural number as output. This idea as described is vague until it is circumscribed by a specific notion of computer program (Turing machines, register machines, abaci, etc.). There is a standard article of faith called the ``[[Church-Turing thesis]]'', identifying functions on natural numbers that are algorithmically computable with those that are computable using a Turing machine (or some variant class of machines that is Turing-complete). A purely mathematical definition of the intended class of functions is given below. \hypertarget{definition}{}\subsection*{{Definition}}\label{definition} \begin{defn} \label{recursive}\hypertarget{recursive}{} A \emph{partial recursive function} is a [[partial function]] from $\mathbb{N}^k$ to $\mathbb{N}$ (where $\mathbb{N}$ is the [[set]] of [[natural numbers]] and $k \geq 0$ is finite) that belongs to the smallest [[class]] $\mathcal{C}$ of partial functions that \begin{itemize}% \item includes all [[constant functions]] $1 \to \mathbb{N}$; \item includes all [[projection]] maps $\pi_i: \mathbb{N}^k \to \mathbb{N}$, $i = 1, \ldots, k$; \item includes the successor function $s: \mathbb{N} \to \mathbb{N}$; \item is closed under [[composition]]: if $f_1: \mathbb{N}^{k} \to \mathbb{N}, \ldots, f_n: \mathbb{N}^{k} \to \mathbb{N}$ and $g: \mathbb{N}^n \to \mathbb{N}$ belong to $\mathcal{C}$, then so does $g \circ (f_1, \ldots, f_n): \mathbb{N}^{k} \to \mathbb{N}$; \item is closed under primitive [[recursion]]: if $g: \mathbb{N}^k \to \mathbb{N}$ and $h: \mathbb{N}^{k+2} \to \mathbb{N}$ belong to $\mathcal{C}$, then the function $f: \mathbb{N}^{k+1} \to \mathbb{N}$ defined recursively by the equations (for $y \in \mathbb{N}$ and $\mathbf{x} \in \mathbb{N}^k$) \begin{displaymath} f(0, \mathbf{x}) = g(\mathbf{x}) \end{displaymath} \begin{displaymath} \, \end{displaymath} \begin{displaymath} f(y+1, \mathbf{x}) = h(y, f(y, \mathbf{x}), \mathbf{x}) \end{displaymath} also belongs to $\mathcal{C}$; \item is closed under minimization: given any \emph{[[total function|total]]} function $f: \mathbb{N}^{k+1} \to \mathbb{N}$ belonging to $\mathcal{C}$, the partial function $g: \mathbb{N}^k \to \mathbb{N}$, defined by $g(\mathbf{x}) = c$ iff $f(c, \mathbf{x}) = 0$ and $f(d, \mathbf{x}) \gt 0$ whenever $0 \leq d \leq c-1$, also belongs to $\mathcal{C}$. \end{itemize} \end{defn} \begin{defn} \label{}\hypertarget{}{} A \emph{primitive recursive function} is a function that belongs to the smallest class of functions of the form $\mathbb{N}^k \to \mathbb{N}$ that contains constants, projection maps, the successor map, is closed under composition, and is closed under primitive recursion. \end{defn} Clearly the primitive recursive functions are a subclass of partial recursive functions. Notice that primitive recursive functions are not merely partial functions, but actual (\emph{total}) functions. \begin{remark} \label{Lawvere}\hypertarget{Lawvere}{} Both the class of partial recursive functions and the class of primitive recursive functions yield [[Lawvere theories]] $Th(Comp)$ and $Th(PrimRec)$, where a morphism $k \to 1$ of the Lawvere theory is a function $\mathbb{N}^k \to \mathbb{N}^1$ belonging to the class. It is straightforward to check that in either case, the generating object $1$ of the Lawvere theory (or $\mathbb{N}$ if you prefer) is a parametrized [[natural numbers object|NNO]] in that category: this is the essence of primitive recursion. \end{remark} \begin{defn} \label{}\hypertarget{}{} A \emph{recursive relation} (or what is more usual nowadays, a \emph{computable relation}) is a subset of $\mathbb{N}^k$ whose characteristic function $\chi: \mathbb{N}^k \to \{0, 1\}$ is recursive. Similarly, a primitive recursive relation is a relation whose characteristic function is primitive recursive. \end{defn} \hypertarget{properties}{}\subsection*{{Properties}}\label{properties} We may build up a stock of functions and relations that are primitive recursive as follows. (All closure properties mentioned will clearly also apply to partial recursive functions and relations.) \begin{enumerate}% \item Addition, multiplication, and exponentiation on $\mathbb{N}$. The factorial function $n \mapsto n!$ is primitive recursive. Binomial coefficients. \item The predecessor function $Pred: \mathbb{N} \to \mathbb{N}$, defined by the recursion $Pred(0) = 0$, $Pred(n+1) = n$. \item \emph{Truncated subtraction}, where $x \stackrel{\cdot}{-} y = x - y$ if $x \geq y$, else $0$, is primitive recursive. It is defined by the recursion $x \stackrel{\cdot}{-} 0 = x$, $x \stackrel{\cdot}{-} (y+1) = Pred(x \stackrel{\cdot}{-} y)$. \item The distance function ${|x-y|} = (x \stackrel{\cdot}{-} y) + (y \stackrel{\cdot}{-} x)$. The function $\alpha(x) = 1 \stackrel{\cdot}{-} x$; this is the characteristic function of the unary relation or predicate ``equals zero''. So ``equals zero'' is a computable relation. So is ``doesn't equal zero'', since this has characteristic function $\alpha(\alpha(x))$. \item Therefore the equality relation ${|x-y|} = 0$ is a primitive recursive relation. So is $x \lt y$, being the relation ``$y \stackrel{\cdot}{-} x$ doesn't equal zero''. If $f$ is a (primitive) recursive function, then its graph defined by the relation $y = f(x)$ is a (primitive) recursive relation. \item (Boolean combinations) Similarly, if $R$ is a primitive recursive relation (so that its characteristic function $\chi_R$ is primitive recursive), then so is its negation $\neg R$, since $\chi_{\neg R} = \alpha(\chi_R)$. If $P$, $Q$ are primitive recursive relations, so is $P \wedge Q$, since $\chi_{P \wedge Q} = \chi_P \cdot \chi_Q$. Hence Boolean combinations of primitive recursive relations are primitive recursive. \item If $f(x, y, \mathbf{z})$ and $h(y)$ are primitive recursive, so is \begin{displaymath} g(y, \mathbf{z}) \coloneqq \sum_{x=0}^{h(y)} f(x, y, \mathbf{z}) \end{displaymath} and similarly with the sum replaced by a product. It follows that primitive recursive predicates are closed under \emph{bounded quantification}; e.g., if $R(x, y, \mathbf{z})$ is a primitive recursive predicate and $h$ is a primitive recursive function, then the predicate $Q$ defined by \begin{displaymath} Q(y, \mathbf{z}) = \forall_{0 \leq x \lt y} R(x, y, \mathbf{z}) \coloneqq \bigwedge_{x=0}^{y-1} R(x, y, \mathbf{z}) \end{displaymath} is primitive recursive since $\chi_Q(y, \mathbf{z}) = \prod_{x=0}^{y-1} \chi_R(x, y, \mathbf{z})$. \item (Bounded least choice operator) If $R(x, y, \mathbf{z})$ is a primitive recursive relation and $h$ is a primitive recursive function, then the function $f(y, \mathbf{z})$ defined to be ``the least $x \leq h(y)$ such that $R(x, y, \mathbf{z})$ if such $x$ exists, else $y$'' is primitive recursive. Indeed, \begin{displaymath} f(y, \mathbf{z}) = [\sum_{x=0}^{h(y)} (x \cdot \chi_R(x, y, \mathbf{z}) \cdot (\prod_{w=0}^{x-1} \chi_{\neg R}(w, y, \mathbf{z}))] + y \cdot \prod_{x=0}^{h(y)} \chi_{\neg R}(x, y, \mathbf{z}). \end{displaymath} \item (Pairing and unpairing) There is an isomorphism $\mathbb{N}^2 \to \mathbb{N}$ in the Lawvere theory $Th(PrimRec)$, i.e., there is a primitive recursive function $f: \mathbb{N}^2 \to \mathbb{N}$ with a primitive recursive inverse $g: \mathbb{N} \to \mathbb{N}^2$. For example, take $f$ to be the function \begin{displaymath} f: (m, n) \mapsto \binom{m+n+1}{2} + n \end{displaymath} Its inverse $g$ takes $m$ to the pair \begin{displaymath} (a \stackrel{\cdot}{-} (m - \binom{a \stackrel{\cdot}{-} 1}{2}+2), m - \binom{a \stackrel{\cdot}{-} 1}{2}) \end{displaymath} where $a$ is the least element less than $m+2$ such that $\binom{a}{2} \gt m$. By the aforementioned properties, this $g$ is manifestly primitive recursive. \end{enumerate} As a consequence of this last property, there exist primitive recursive [[isomorphisms]] between $\mathbb{N}$ and $\mathbb{N}^k$ for any $k \gt 0$. Since partial/primitive recursive functions are closed under composition, it is sufficient (and sometimes convenient) to consider only partial/primitive recursive functions on $\mathbb{N}$ itself. (The exception is the case $k = 0$, but this is trivial, since every partial function $1 \to \mathbb{N}$ is recursive.) \begin{remark} \label{}\hypertarget{}{} To show that $\mathbb{N}^2 \cong \mathbb{N}$ in the category of primitive recursive functions, it is not enough just to exhibit a primitive recursive bijection $f: \mathbb{N}^2 \to \mathbb{N}$, because it is not true that every primitive recursive bijection possesses a primitive recursive inverse. In other words, it is not true that the forgetful functor $Th(PrimRec) \to Set$ (see Remark \ref{Lawvere}) reflects isomorphisms. See Example \ref{inverse} below. \end{remark} \begin{remark} \label{}\hypertarget{}{} Similarly, it is not always true that if a graph of a function is a primitive recursive relation, then the function itself is primitive recursive. (For example, the graph of the Ackermann function, discussed below, is a primitive recursive relation.) However, we do have a sample theorem as follows. \end{remark} \begin{theorem} \label{bound}\hypertarget{bound}{} If a graph of a function $f$ is a primitive recursive relation, and if $f \leq g$ for some primitive recursive $g$, then $f$ is itself primitive recursive. \end{theorem} The proof can be roughly expressed as follows: if $R(x, y)$ is the functional computable relation, then let $f(x)$ be the least $y \leq g(x)$ such that $R(x, y)$. The bounded least choice property shows that $f(x)$ is primitive recursive. The point hovering in the background is that there are some computable functions which grow faster (in fact, much much much faster) than any primitive recursive function. This underscores the important role of the minimization axiom for partial recursive functions, which allows unboundedly large searches to take place. Indeed, we have the following crucial fact: \begin{theorem} \label{graph}\hypertarget{graph}{} If $R \subseteq{N}^2$ is a graph of a function $f$ and is a recursive relation, then $f$ is a (total) recursive function. (The converse holds by one of the properties listed above.) \end{theorem} \begin{proof} According to the minimization axiom in Definition \ref{recursive}, given that $\chi_R: \mathbb{N}^2 \to \{0, 1\}$ is a recursive function, the function that takes $x$ to the least $y \in \mathbb{N}$ such that $1 - \chi_R(x, y) = 0$ is also recursive. But this function is simply $f$. This completes the proof. \end{proof} \begin{corollary} \label{}\hypertarget{}{} The inverse of a recursive bijection $f$ is also recursive. \end{corollary} \begin{proof} The graph of $f$ is a recursive relation, and so is the opposite graph, which is the graph of the function $f^{-1}$. Apply the preceding theorem. \end{proof} Before passing on to general recursive functions, it is good to have some idea of the scope of primitive recursive functions. Some examples: \begin{itemize}% \item The function $f(n) = p_n$, the $n^{th}$ prime, is primitive recursive. \end{itemize} \hypertarget{the_ackermann_function}{}\subsection*{{The Ackermann function}}\label{the_ackermann_function} \begin{defn} \label{}\hypertarget{}{} For each $n$, we define a function $A_n: \mathbb{N} \to \mathbb{N}$ by \begin{itemize}% \item $A_0(m) = 2 m$; \item $A_{n+1}(m) = (A_n)^m(1)$ \end{itemize} where $f^m$ denotes the composition of $m$ copies of $f$. The \textbf{Ackermann function} $A: \mathbb{N} \to \mathbb{N}$ is defined by $A(m) = A_m(m)$. \end{defn} (The function is named after [[Wilhelm Ackermann]]. There are several variations of this function around, and one common version actually puts $A_0(m)=m+1$ and \$A\_\{n+1\}(m)=(A\_n){\tt \symbol{94}}m(f(1)).) We show that while each $A_n$ is primitive recursive, the function $A$ grows faster than any primitive recursive function on $\mathbb{N}$, hence is not itself primitive recursive. It does however belong to the class of partial recursive functions. By property 1 above, $A_0$ is primitive recursive. Supposing that $A_n$ is primitive recursive, $\phi = A_{n+1}$ is also primitive recursive because it satisfies the recursion $\phi(0) = 1$, $\phi(m+1) = A_n (\phi(m))$. By induction one may easily show $A_n(1) = 2$ for all $n$ and $A_n(2) = 4$ for all $n$. We have $A_{n+1}(3) = A_n(A_n(A_n(1))) = A_n(A_n(2)) = A_n(4)$ for all $n$. The function $A_1$ gives $n^{th}$ powers of $2$, the function $A_2$ gives tetrations (iterated exponentials stacked $n$ high) of $2$, the function $A_3$ gives iterated tetrations, and so on. Some routine inductions establish the following facts: \begin{itemize}% \item For all $n$, the function $A_n$ is strictly increasing, and with the sole exception of $A_0(0) = 0$, we have $m \lt A_n(m)$ for all $m$, i.e. $A_n$ is strictly inflationary in arguments $m \gt 0$. We also have $n \lt A_n(3)$ for all $n$. \end{itemize} \begin{lemma} \label{}\hypertarget{}{} If $f: \mathbb{N}^k \to \mathbb{N}$ is primitive recursive, then there exists $n$ such that $f(x_1, \ldots, x_k) \leq A_n(\max \{3, x_1, \ldots, x_k\})$ for all $x_1, \ldots, x_k$. (We say $f$ is \textbf{dominated} by $A_n$, for short.) \end{lemma} \begin{proof} In the case where $f$ is constant with value $m$, take $n=m$. For $f$ the successor, use $n = 0$. For each projection $\pi_i: \mathbb{N}^k \to \mathbb{N}$, again use $n = 0$: \begin{displaymath} x_i = \pi_i(x_1, \ldots, x_k) \leq A_0(\max \{3, x_1, \ldots, x_k\}). \end{displaymath} Now proceed by induction on the construction of primitive recursive functions. Given that $f: \mathbb{N}^k$ is dominated by $A_n$ and $g_1, \ldots, g_k: \mathbb{N}^m \to \mathbb{N}$ are dominated by $A_{n+1}$, we calculate that $h = f \circ (g_1, \ldots, g_k): \mathbb{N}^m \to \mathbb{N}$ is dominated by $A_{n+2}$: \begin{displaymath} \itexarray{ h(x_1, \ldots, x_m) & = & f(g_1(x_1, \ldots, x_m), \ldots, g_k(x_1, \ldots, x_m)) \\ & \leq & A_n(\max \{3, g_1(x_1, \dots, x_m), \ldots, g_k(x_1, \ldots, x_m)\}) \\ & \leq & A_n(A_{n+1}(\max\{3, x_1, \ldots, x_m\})) \\ & = & A_{n+1}(\max\{3, x_1, \ldots, x_m\} + 1) \\ & \leq & A_{n+2}(\max\{3, x_1, \ldots, x_m\}). } \end{displaymath} And given that $g: \mathbb{N}^k \to \mathbb{N}$ is dominated by $A_{n+1}$ and $h: \mathbb{N}^{k+2} \to \mathbb{N}$ is dominated by $A_n$, if we define $f: \mathbb{N}^{k+1} \to \mathbb{N}$ by recursion by $f(0, x_1, \ldots, x_k) = g(x_1, \ldots, x_k)$ and $f(y+1, x_1, \ldots, x_k) = h(y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k)$, we calculate that $f$ is dominated by $A_{n+3}$, in two steps. First we claim \begin{displaymath} f(y, x_1, \ldots, x_k) \leq A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}). \end{displaymath} Indeed, this is true by assumption for $y=0$. And then \begin{displaymath} \itexarray{ f(y+1, x_1, \ldots, x_k) & = & h(y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k) \\ & \leq & A_n(\max\{3, y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k)\}) \\ & \leq & A_n(\max\{3, y, A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}), x_1, \ldots, x_k\}) \\ & \leq & A_n(A_{n+1}(y + \max\{3, x_1, \ldots, x_k\})) \\ & = & A_{n+1}(y+1+\max\{3, x_1, \ldots, x_k\}) } \end{displaymath} which justifies the claim. Finally, we have \begin{displaymath} \itexarray{ f(y, x_1, \ldots, x_k) & \leq & A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}) \\ & \leq & A_{n+1}(2\max\{3, y, x_1, \ldots, x_k\}) \\ & \leq & A_{n+1}(A_{n+2}(\max\{3, y, x_1, \ldots, x_k\})) \\ & = & A_{n+2}(\max\{3, y, x_1, \ldots, x_k\} + 1) \\ & \leq & A_{n+3}(\max\{y, x_1, \ldots, x_k\}) } \end{displaymath} so that $f$ is dominated by $A_{n+3}$. This completes the proof. \end{proof} \begin{corollary} \label{}\hypertarget{}{} The Ackermann function $A$ is not primitive recursive. \end{corollary} \begin{proof} If $A: x \mapsto A_x(x)$ were recursive, then so would be the function $\phi: x \mapsto A_x(x) + 1$. In that case, $\phi$ is dominated by $A_n$ for some $n \geq 3$. We then arrive at the contradiction \begin{displaymath} A_n(n) + 1 = \phi(n) \leq A_n(\max\{3, n\}) = A_n(n). \end{displaymath} \end{proof} \begin{prop} \label{}\hypertarget{}{} The \emph{graph} of the Ackermann function \emph{is} a primitive recursive relation. \end{prop} \begin{proof} The rough idea is to let $z$ bound the search for solutions $(x, y)$ to $A_x(y) = z$. For $x, y \gt 0$ we have $A_x(y) = A_{x-1}(A_x(y-1)) = A_x(y')$ where $y' \coloneqq A_x(y-1)$. We have $y' \lt A_{x-1}(y') = z$. Starting with $y_0 = y \lt z$, iterate this procedure so that \begin{displaymath} z = A_x(y_0) = A_{x-1}(y_1) = A_{x-2}(y_2) = \ldots = A_0(y_x) = 2 y_x \end{displaymath} with each $y_i$ less than $z$. (Explicitly, the iteration is $y_{i+1} \coloneqq A_{x-i}(y_i - 1)$.) Thus, after disposing of some trivial low number cases, WLOG we may take $z \gt 4$, where the ternary predicate \begin{displaymath} (z \gt 4) \wedge (A_x(y) = z) \end{displaymath} is equivalent to \begin{displaymath} (x \gt 0) \wedge (y \gt 2) \wedge (x \lt z) \wedge \exists_{y_0, y_1, \ldots y_x \lt z} (y = y_0) \wedge (\forall_{i \lt x} y_{i+1} = A_{x-i}(y_i - 1)) \wedge (2 y_x = z) \end{displaymath} where the quantifications are manifestly bounded by $z$. This shows that the ternary predicate $A_x(y) = z$ is primitive recursive. From this it follows that the binary relation $A_x(x) = z$ is also primitive recursive, as claimed. \end{proof} Combining this result with Theorem \ref{graph}, we have \begin{corollary} \label{}\hypertarget{}{} The Ackermann function $A: x \mapsto A_x(x)$ is recursive. \end{corollary} \begin{example} \label{inverse}\hypertarget{inverse}{} Here we exhibit a primitive recursive bijection whose inverse is not primitive recursive. The graph $y = A_x(x)$ of the Ackermann function is primitive recursive binary predicate, and the image $I = \{y: \exists_x y = A_x(x)\}$ is a primitive recursive unary predicate, because the existential quantifier is a bounded quantifier applied to a primitive recursive relation: \begin{displaymath} I = \bigvee_{x=0}^{y-1} [A_x(x) = y]. \end{displaymath} Observe that both $I$ and its complement $\neg I$ in $\mathbb{N}$ are infinite. For any infinite set $J \subseteq \mathbb{N}$, let $p_J: \mathbb{N} \to \mathbb{N}$ be the function taking $n$ to the $n^{th}$ element of $J$ (with respect to the usual order $\lt$). For example, $p_I(x) = A_x(x)$. Now define a function $f: \mathbb{N} \to \mathbb{N}$ by \begin{displaymath} \itexarray{ f(m) & = & 2p_I^{-1}(m) & \text{if} \; m \in I \\ & = & 2p_{\neg I}^{-1}(m) + 1 & \text{if} \; m \in \neg I } \end{displaymath} Then $f(m) \leq 2m + 1$ and the graph of $f$ is primitive recursive, so by Theorem \ref{bound}, $f$ is a primitive recursive function. It is a bijection by construction. But $f^{-1}$ is not primitive recursive, because $f^{-1}(2x) = p_I(x) = A(x)$, and $A$ is not primitive recursive. \end{example} \hypertarget{busy_beaver_function}{}\subsection*{{Busy Beaver function}}\label{busy_beaver_function} \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[recursive subset]] \end{itemize} [[!include computable mathematics -- table]] \hypertarget{references}{}\subsection*{{References}}\label{references} A standard textbook in recursive functions is \begin{itemize}% \item Hartley Rogers, Jr., \emph{Theory of recursive functions and effective computability}, McGraw-Hill, 1967. \end{itemize} Quite a bit of the arrangement and proofs above were taken from clear and useful lecture notes of Stephen Simpson, \begin{itemize}% \item Stephen G. Simpson, \emph{Foundations of Mathematics} (Lecture Notes), October 1, 2009. (\href{http://www.math.psu.edu/simpson/notes/fom.pdf}{pdf}) \end{itemize} Of course, there is always good old Wikipedia: \begin{itemize}% \item Wikipedia, \emph{\href{http://en.wikipedia.org/wiki/Computable_function}{Computable function}} \end{itemize} [[!redirects partial recursive function]] [[!redirects partial recursive functions]] [[!redirects recursive partial function]] [[!redirects recursive partial functions]] [[!redirects Ackermann function]] [[!redirects Ackermann functions]] \end{document}