|
|
|
Viewing Version
5
of
'computable number'
|
[ view 'computable number'
|
back to history
]
| Title of object: |
computable number |
| Canonical Name: |
ComputableNumber |
| Type: |
Topic |
| Created on: |
2003-04-08 16:55:26 |
| Modified on: |
2004-02-23 21:30:06 |
| Classification: |
msc:68Q05, msc:03D25 |
| Defines: |
computable |
Revision comment (for changes between this and next version):
| Equivalence with Turing's definition |
Preamble:
% 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}
% 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 |
Content:
\PMlinkescapeword{constant}
\PMlinkescapeword{constants}
\PMlinkescapeword{contains}
A real number $r$ is called \emph{computable} if there exists some algorithm (or Turing machine) that can approximate it to arbitrary precision. Specifically, the algorithm takes a natural number $n$ as input and produces an integer $m$ as output such that
\[\frac{m-1}{n} < r < \frac{m+1}{n}\]
A complex number is called computable if its real and imaginary parts are computable.
The computable numbers form an algebraically closed field, and arguably this field contains all the numbers we ever need in practice. It contains all algebraic numbers as well as many known transcendental constants. There are however many real numbers which are not computable: the set of all computable numbers is countable (because the set of algorithms is) while the set of real numbers is uncountable.
Every computable number is definable, but not vice versa. An example of a definable, non-computable real is Chaitin's constant, $\Omega$.
Computable numbers were introduced by Alan Turing in 1936. |
|
|
|
|
|
