| Version 11 |
Version 10 |
| \PMlinkescapeword{recursive} |
\PMlinkescapeword{recursive} |
|
|
| A subset $S$ of the natural numbers $\mathbb{N}$ is said to be \emph{recursive} if its characteristic function |
A subset $S$ of the natural numbers $\mathbb{N}$ is said to be \emph{recursive} if its characteristic function |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| \chi_S(x) &:=& \left\{ |
\chi_S(x) &:=& \left\{ |
| \begin{array}{ll} |
\begin{array}{ll} |
| 1 & \mbox{ if } x\in S \\ |
1 & \mbox{ if } x\in S \\ |
| 0 & \mbox{ if } x\in \mathbb{N}-S |
0 & \mbox{ if } x\in \mathbb{N}-S |
| \end{array}\right. |
\end{array}\right. |
| \end{eqnarray*} |
\end{eqnarray*} |
| is computable. In other words, there is an algorithm (via Turing machine for example) that determines whether an element is in $S$ or not in $S$. |
is computable. In other words, there is an algorithm (via Turing machine for example) that determines whether an element is in $S$ or not in $S$. |
|
|
| Examples of recursive sets are finite set, the set of integers, the set of positive integers, the set of prime numbers. In the last example, one may use the Sieve of Eratosthenes as an algorithm to determine the primality of an integer. |
Examples of recursive sets are finite set, the set of integers, the set of positive integers, the set of prime numbers. In the last example, one may use the Sieve of Eratosthenes as an algorithm to determine the primality of an integer. |
|
|
| A set $S\subseteq \mathbb{N}$ is \emph{recursively enumerable} if the partial function |
A set $S\subseteq \mathbb{N}$ is \emph{recursively enumerable} if the partial function |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| f(x) &:=& \left\{ |
f(x) &:=& \left\{ |
| \begin{array}{ll} |
\begin{array}{ll} |
| 1 & \mbox{ if } x\in S \\ |
1 & \mbox{ if } x\in S \\ |
| \mbox{undefined} & \mbox{ if } x\in \mathbb{N}-S |
\mbox{undefined} & \mbox{ if } x\in \mathbb{N}-S |
| \end{array}\right. |
\end{array}\right. |
| \end{eqnarray*} |
\end{eqnarray*} |
| is computable. In other words, there is an algorithm that halts (and returns $1$) only when an element in $S$ is used as an input. |
is computable. In other words, there is an algorithm that halts (and returns $1$) only when an element in $S$ is used as an input. |
|
|
| \textbf{Remarks} |
\textbf{Remarks} |
| \begin{itemize} |
\begin{itemize} |
| \item A recursive set is variably known as a \emph{decidable set} or a \emph{computable set}. |
\item A recursive set is variably known as a \emph{decidable set} or a \emph{computable set}. |
| \item Since every finite set $\Sigma$ can be encoded by the natural numbers, we can define a \emph{recursive language} over $\Sigma$ to be a subset $L\subseteq \Sigma^*$ such that $L$, when encoded by the natural numbers, is a recursive set. Equivalently, $L$ is recursive iff there is a Turing machine that decides $L$ (accepts $L$ and rejects $\Sigma^*-L$). |
\item Since every finite set $\Sigma$ can be encoded by the natural numbers, we can define a \emph{recursive language} over $\Sigma$ to be a subset $L\subseteq \Sigma^*$ such that $L$, when encoded by the natural numbers, is a recursive set. Equivalently, $L$ is recursive iff there is a Turing machine that accepts $L$ and rejects $\Sigma^*-L$. |
| \item Similarly, a language $L$ over $\Sigma$ is \emph{recursively enumerable} if its encoding by the natural numbers is a recursively enumerable set. Equivalently, $L$ is recursively enumerable iff there is a Turing machine that accepts $L$. |
|
| \item Using the above definition, one can define a \emph{recursive predicate} or a \emph{recursively enumerable predicate} $\varphi(x)$ according to whether $\lbrace x\mid \varphi(x)\rbrace$ is a recursive or recursively enumerable set respectively. |
\item Using the above definition, one can define a \emph{recursive predicate} or a \emph{recursively enumerable predicate} $\varphi(x)$ according to whether $\lbrace x\mid \varphi(x)\rbrace$ is a recursive or recursively enumerable set respectively. |
| \end{itemize} |
\end{itemize} |
