|
|
|
Viewing Version
1
of
'recursive set'
|
[ view 'recursive set'
|
back to history
]
| Title of object: |
recursive set |
| Canonical Name: |
RecursiveSet |
| Type: |
Definition |
| Created on: |
2007-10-12 14:03:18 |
| Modified on: |
2007-10-12 14:03:18 |
| Classification: |
msc:03D20 |
| Defines: |
recursively enumerable set |
| Synonyms: |
recursive set=decidable set
recursive set=computable set |
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% 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}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} |
Content:
\PMlinkescapeword{recursive}
Fix a set $U$. A subset $S\subseteq U$ is said to be \emph{recursive} if its characteristic function on $U$
\begin{eqnarray*}
\chi_S(x) &:=& \left\{
\begin{array}{ll}
1 & \mbox{ if } x\in S \\
0 & \mbox{ if } x\in U-S.
\end{array}\right.
\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$.
A recursive set is variably known as a \emph{decidable set} or a \emph{computable set}.
Examples of recursive sets are finite set, the set of integers, the set of positive integers, the set of prime numbers. |
|
|
|
|
|
