recursively enumerableRecursivelyEnumerable2002-06-05 07:26:292002-06-05 11:42:02Definitionsemi-recursiverecursively enumerable function% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amstext} % do we need this?
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newcommand{\Prob}[2]{\mathbb{P}_{#1}\left\{#2\right\}}
\newcommand{\norm}[1]{\left\|#1\right\|}
% Some sets
\newcommand{\Nats}{\mathbb{N}}
\newcommand{\Ints}{\mathbb{Z}}
\newcommand{\Reals}{\mathbb{R}}
\newcommand{\Complex}{\mathbb{C}}For a language $L$, TFAE:
\begin{itemize}
\item There exists a Turing machine $f$ such that $\forall x.(x\in L) \iff \mbox{the computation $f(x)$ terminates}$.
\item There exists a total recursive function $f:\Nats\to L$ which is \emph{onto}.
\item There exists a total recursive function $f:\Nats\to L$ which is \emph{one-to-one and onto}.
\end{itemize}
A language $L$ fulfilling \emph{any} (and therefore \emph{all}) of the above conditions is called \emph{recursively enumerable}.
\subsection*{Examples}
\begin{enumerate}
\item Any recursive language.
\item The set of encodings of Turing machines which halt when given no input.
\item The set of encodings of theorems of Peano arithmetic.
\item The set of integers $n$ for which the hailstone sequence starting at $n$ reaches 1. \textit{(We don't know if this set is recursive, or even if it is $\Nats$; but a trivial program shows it is recursively enumerable.)}
\end{enumerate}