Número computable

π pot calcular-se en una precisió arbitrària, mentres que casi tots els número real no són calculables.

En matemàtiques, especialment en ciència computacional teòrica i llògica matemàtica, els números computables o recursivos són els número real que poden ser computats en la precisió que es desige per un algoritme finito. Es pot aplegar al mateix resultat utilisant funcions recursivas, màquines de Turing o càlcul-λ, d'acort en la tesis de Church-Turing.

Definició informal utilisant Màquines de Turing

Marvin Minsky va definir els números que es van a calcular més o menys com ho va fer allà per 1936 Alan Turing, com "una seqüència de dígits interpretada com a fraccions decimals" entre 0 i 1:

"Un número computable [és] aquell per al que hi ha una màquina de Turing que, donat n en la seua cinta inicial, termina en el n-ésimo dígit d'eixe número [codificat en eixa cinta]." (Minsky 1967:159)

Les claus d'esta definició són: (1) s'especifica n al principi, i (2) el càlcul té un número finito de passos per a qualsevol n, despuix del com la màquina produïx el resultat desijat i termina.

Una forma diferent de dir (2) podria ser que la màquina escriu successivament tots els dígits en la cinta i per a en el n-ésimo dígit, i esta definició emfatisa l'observació de Minsky: (3) utilisant una Màquina de Turing es dona una definició finita de lo que és potencialment una cadena infinita de dígits decimals.

Aixina i tot, esta no és la definició formal i moderna, que únicament requerix que el resultat calga donat qualsevol grau de precisió. La definició informal està subjecta a un problema de grosseig mentres que la moderna no.

Definició formal

Un número real és computable si es pot donar una aproximació d'ell per mig d'una funció computable de la següent forma: donat qualsevol número entero $n\ge 1$, la funció produïx un número entero k tal que:

$\frac{k-1}{n}\le a\le \frac{k+1}{n}$

Hi ha dos definicions similars que són equivalents:

• Existix una funció computable que, donat qualsevol marge d'error $\epsilon$, produïx un número racional r tal que $|r-a|\le \epsilon$
• Existix una seqüència computable d'número racional $q_i$ que convergixen en $a$ tal que $|q_i-q_{i+1}|<2^{-i}$ per a cada i.

Existix encara una atra definició de números computables per mig de cortaduras de Dedekind. Una cortadura de Dedekind computable és una funció computable $D$ que, proporcionat un número racional $r$ com a entrada, torna $D(r)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ o $D(r)=false$, i complixen les següents condicions:

$\mathrm{\exists }rD(r)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$

$\mathrm{\exists }rD(r)=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$

$(D(r)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e})\wedge (D(s)=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e})\Rightarrow r<s$

$D(r)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}\Rightarrow \mathrm{\exists }s>r,D(s)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$

Un eixemple pot ser un programa D que definix la raïl cúbica de 3. Assumint $q>0$ es definix:

$p^3<3q^3\Rightarrow D(p/q)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$

$p^3>3q^3\Rightarrow D(p/q)=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$

Un número real és computable si i solament si existix una cortadura de Dedekind D que convergix en ell. La funció D és única per a cada número computable irracional (encara que dos programes diferents puguen donar la mateixa funció).

Un número complejo és computable si les seues parts real i imaginària són abdós computables.

Referències

Bibliografia

• Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299. Descriu el desenroll del càlcul sobre els números computables.
• Errett Bishop i Douglas Bridges, Constructive Analysis, Springer, 1985, ISBN 0-387-15066-8
• Douglas Bridges i Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
• Jeffry L. Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics, 55, (2007) 303–316.
• Marvin Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. El capítul §9 "The Computable Real Numbers" expandix els temes d'este artícul.

• E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic , 14 (1949) pp. 145–158
• (and ). Els números computables (i les màquines de Turing) estan en este document; la definició de números computables usa seqüències infinites de decimals.
• Klaus Weihrauch 2000, Computable analysis, parla de ciències de la computació, Springer, ISBN 3-540-66817-9. El capítul §1.3.2 introduïx la definició per mig del principi dels intervals encaixats. També es parla d'atres representacions en el capítul §4.1.
• Klaus Weihrauch, A simple introduction to computable analysis