Nombre computable

En matemàtiques i especialment en complexitat computacional un nombre computable és un nombre real que pot ser computat amb una precisió arbitraria mitjançant un algorisme finit i que s'atura. També se'ls coneix com a nombres recursius o nombres reals recursius. Es poden obtenir definicions equivalents fent servir funcions recursives, màquines de Turing o el càlcul lambda.

Definició informal usant màquines de Turing

Seguint la definició feta per Marvin Minsky, es defineixen els números a calcular de forma similar a com ho va fer Turing el 1937, com "una seqüència de dígits interpretada com a fraccions decimals" entre 0 i 1:

"Un nombre és computable és aquell pel que hi ha una màquina de Turing que, donat n a la seva cinta inicial, acaba amb l'n-éssim dígit d'aquell número" (Minsky 1967)

Els conceptes claus d'aquesta definició son:

1. s'especifica n al principi
2. el càlcul té un nombre finit de passos per qualsevol n, després dels quals la màquina produeix el resultat desitjat i s'atura.

Una forma alternativa de dir (2) podria ser que la màquina escriu successivament tots els dígits a la cinta i s'atura amb l'n-éssim dígit. Aquesta definició emfatitza l'observació de Minsky: (3) utilitzant una màquina de Turing es dona una definició finita del que potencialment és una cadena infinita de dígits decimals.

Aquesta definició no és la definició formal actual, que només requereix que el resultat sigui precís donat qualsevol grau de precisió. La definició formal està sotmesa a un problema d'arrodoniment mentre que la moderna no.

Definició formal

Un nombre real a és computable si se'n pot donar una aproximació mitjançant una funció computable de la següent forma: donat un nombre enter qualsevol $n\geq 1$, la funció produeix un nombre enter k tal que:

${k-1 \over n}\leq a\leq {k+1 \over n}$

Hi ha dues definicions similars equivalents:

• Existeix una funció computable que, donat qualsevol marge d'error $\epsilon$, produeix un nombre racional r tal que $|r-a|\leq \varepsilon$.
• Existeix una seqüència computable de nombres racionals $q_{i}$, que convergeixen cap a $a$tal que $\displaystyle |q_{i}-q_{i+1}|<2^{-i}$per cada $i$.

Encara hi ha una altra definició de número computable mitjançant talls de Dedekind. Un tall de Dedekind computable és una funció computable D que donat un nombre racional r com entrada, retorna $D(r)=\mathrm {true}$o $D(r)=\mathrm {false}$i compleixen les següents condicions:

$\exists rD(r)=\mathrm {true} \;$

$\exists rD(r)=\mathrm {false} \;$

$(D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;$

$D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} \;$

Un exemple pot ser un programa D que defineix l'arrel cúbica de 3. Assumint $q>0\;$es defineix:

$p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;$

$p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} \;$

Un nombre real és computable si i només si existeix un tall de Dadekind D que convergeix cap a ell. La funció D és única per cada nombre computable irracional (tot i que dos programes diferents poden donar la mateixa funció).

Un nombre complex és computable si les seves parts reals i imaginaria són les dues computables.