Número computável

π pode ser computado a precisão arbitrária, enquanto quase todo número real não é computável.

Na matemática, números computáveis são os números reais que podem ser calculados dentro de qualquer precisão desejada por um algoritmo finito de terminação. Eles também são conhecidos como números recursivos, números efetivos ou reais computáveis ou reais recursivos. O conceito de número real computável foi introduzido por Emile Borel em 1912, usando a noção intuitiva de computabilidade disponível na época.

Definições equivalentes podem ser dadas usando funções μ-recursivas, máquinas de Turing ou λ-cálculo como a representação formal de algoritmos. Os números computáveis formam um campo real fechado e podem ser usados no lugar dos números reais para muitos, mas não todos, propósitos matemáticos.

Definição informal usando uma máquina de Turing como exemplo

A seguir, Marvin Minsky define os números a serem computados de maneira semelhante àquelas definidas por Alan Turing em 1936; ou seja, como "sequências de dígitos interpretados como frações decimais" entre 0 e 1:

Um número computável [é] um para o qual há uma máquina de Turing que, dada n em sua fita inicial, termina com a no dígito desse número [codificado em sua fita].

As noções-chave na definição são (1) que algum n é especificado no início, (2) para qualquer n o cálculo leva apenas um número finito de etapas, após as quais a máquina produz a saída desejada e termina.

Uma forma alternativa de (2) – a máquina imprime sucessivamente todos os n dígitos em sua fita, parando após imprimir o nº – enfatiza Minsky' s observação: (3) Que pelo uso de uma máquina de Turing, uma definição finita – na forma da tabela de estado da máquina – está sendo usada para definir o que é um potencial string infinita de dígitos decimais.

No entanto, esta não é a definição moderna que exige apenas que o resultado seja preciso dentro de qualquer precisão. A definição informal acima está sujeita a um problema de arredondamento chamado dilema do fabricante da mesa, enquanto a definição moderna não está.

Definição formal

Um número real um o computável se ele pode ser aproximado por alguma função computável f:N→ → Z.{displaystyle f:mathbb] Não. Não. da seguinte forma: dada qualquer inteiro positivo n, a função produz um inteiro f(n) tal que:

f(n)- Sim. - Sim. 1n≤ ≤ um≤ ≤ f(n)+1n.{displaystyle {f(n)-1 over n}leq aleq {f(n)+1 over n}.}

Existem duas definições semelhantes que são equivalentes:

• Existe uma função computável que, dada qualquer erro racional positivo vinculado ε ε - Sim., produz um número racional R tal que |R- Sim. - Sim. um|≤ ≤ ε ε .{displaystyle |r-a|leq varepsilon.}
• Há uma sequência computável de números racionais qEu...Não. q_{i}} convergir para umNão. tal que <math alttext="{displaystyle |q_{i}-q_{i+1}||qEu...- Sim. - Sim. qEu...+1|<2- Sim. - Sim. Eu...Não. |q_{i}-q_{i+1}|<2^{-i},}<img alt="|q_i - q_{i+1}| para cada Eu....

Há outra definição equivalente de números computáveis através de cortes computáveis Dedekind. A computável Corte de Dedekind é uma função computável DNão. D. que quando fornecido com um número racional RNão. como retornos de entrada D(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue{displaystyle D(r)=mathrm {true} ;} ou D(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =fumEu...Se{displaystyle D(r)=mathrm {false} ;}, satisfazendo as seguintes condições:

Detalhe Detalhe RD(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue{displaystyle existe rD(r)=mathrm {true} ;}

Detalhe Detalhe RD(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =fumEu...Se{displaystyle existe rD(r)=mathrm {false} ;}

<math alttext="{displaystyle (D(r)=mathrm {true})wedge (D(s)=mathrm {false})Rightarrow r(D(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue)∧ ∧ (D(S)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =fumEu...Se)⇒ ⇒ R<S(D(r)=mathrm {true})wedge (D(s)=mathrm {false}) Direita r<s;}<img alt="(D(r)=mathrm{true}) wedge (D(s)=mathrm{false}) Rightarrow r

r,D(s)=mathrm {true}.;}" xmlns="http://www.w3.org/1998/Math/MathML">D(R)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue⇒ ⇒ Detalhe Detalhe S>R,D(S)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue.{displaystyle D(r)=mathrm {true} Rightarrow existe s>r,D(s)=mathrm {true}.;}r, D(s)=mathrm{true}.;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f09c5058a5e14e9a63a8da7548be5b8d53c598ed" style="vertical-align: -0.838ex; width:36.556ex; height:2.843ex;"/>

Um exemplo é dado por um programa D que define a raiz do cubo de 3. Assumindo 0;}" xmlns="http://www.w3.org/1998/Math/MathML">q>0{displaystyle q>0;}0;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/635f269fd2363378fcc30e18cc61cfa2e815c9a9" style="vertical-align: -0.671ex; width:5.976ex; height:2.509ex;"/> isto é definido por:

<math alttext="{displaystyle p^{3}p3<3q3⇒ ⇒ D(p/q)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Rue{displaystyle p^{3}<3q^{3}Rightarrow D(p/q)=mathrm {true} ;}<img alt="p^3

3q^{3}Rightarrow D(p/q)=mathrm {false}.;}" xmlns="http://www.w3.org/1998/Math/MathML">p3>3q3⇒ ⇒ D(p/q)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =fumEu...Se.Não. p^{3}>3q^{3}Rightarrow D(p/q)=mathrm {false}.;}3 q^3 Rightarrow D(p/q)=mathrm{false}.;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a8f9335cfedea0ca7bb13e9cb4ca589c52132c1" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:28.47ex; height:3.176ex;"/>

Um número real é computável se e somente se houver um corte de Dedekind D computável correspondente a ele. A função D é única para cada número computável (embora, é claro, dois programas diferentes possam fornecer a mesma função).

Um número complexo é chamado computável se suas partes real e imaginária são computáveis.

Propriedades

Não é computavelmente enumerável

Atribuir um número Gödel a cada definição da máquina de Turing produz um subconjunto SNão. S. dos números naturais correspondentes aos números computáveis e identifica uma surjeção de SNão. S. para os números computáveis. Há apenas muitas máquinas de Turing, mostrando que os números computáveis são subcontáveis. O conjunto SNão. S. destes números Gödel, no entanto, não é computavelmente enumerável (e, consequentemente, nem são subconjuntos de SNão. S. que são definidos em termos dele). Isso porque não há nenhum algoritmo para determinar quais números Gödel correspondem a máquinas de Turing que produzem reais computáveis. Para produzir um real computável, uma máquina de Turing deve computar uma função total, mas o problema de decisão correspondente está em grau de Turing 0′′′′′. Consequentemente, não há nenhuma função computável surjetiva dos números naturais para os reais computáveis, e o argumento diagonal de Cantor não pode ser usado construtivamente para demonstrar incontavelmente muitos deles.

Enquanto o conjunto de números reais é incontável, o conjunto de números computáveis é classicamente contável e, portanto, quase todos os números reais não são computáveis. Aqui, para qualquer número computável dado x,- Sim. o princípio de ordenação bem fornece que há um elemento mínimo em SNão. S. que corresponde a xNão., e, portanto, existe um subconjunto que consiste nos elementos mínimos, em que o mapa é uma bijeção. O inverso desta bijeção é uma injeção nos números naturais dos números computáveis, provando que eles são contáveis. Mas, novamente, este subconjunto não é computável, mesmo que os reais computáveis sejam eles mesmos ordenados.

Propriedades como um campo

As operações aritméticas em números computáveis são elas próprias computáveis no sentido de que sempre que os números reais um e b) são computáveis, então os seguintes números reais também são computáveis: a + b, a - b, Ae A/B se b) é Nonzero. Estas operações são realmente uniformemente computável; por exemplo, há uma máquina de Turing que na entrada (A,B,ε ε - Sim.) produz saída R, onde A é a descrição de uma máquina de Turing aproximando um, B é a descrição de uma máquina de Turing aproximando b)e R é um ε ε - Sim. aproximação das legislações um+b).

O fato de que números reais computáveis formam um corpo foi provado pela primeira vez por Henry Gordon Rice em 1954.

Reais computáveis, entretanto, não formam um campo computável, porque a definição de um campo computável requer igualdade efetiva.

Não computabilidade da ordenação

A relação de ordem sobre os números computáveis não é computável. Vamos. A ser a descrição de uma máquina de Turing aproximando o número umNão.. Então não há nenhuma máquina de Turing que na entrada A saídas "YES" se 0}" xmlns="http://www.w3.org/1998/Math/MathML">um>0- Sim.0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f34a80ea013edb56e340b19550430a8b6dfd7b9" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;"/> e "não" se um≤ ≤ 0.Não. Para ver o porquê, suponha a máquina descrita por A mantém a saída 0 como ε ε - Sim. aproximações. Não é claro quanto tempo esperar antes de decidir que a máquina vai nunca produzir uma aproximação que força um para ser positivo. Assim, a máquina terá eventualmente de adivinhar que o número será igual 0, a fim de produzir uma saída; a sequência pode mais tarde tornar-se diferente de 0. Esta ideia pode ser usada para mostrar que a máquina está incorreta em algumas sequências se computa uma função total. Um problema semelhante ocorre quando os reais computáveis são representados como cortes Dedekind. O mesmo se aplica à relação de igualdade: o teste de igualdade não é computável.

Embora a relação de ordem completa não seja computável, a restrição dele a pares de números desiguais é computável. Ou seja, há um programa que leva como entrada duas máquinas de Turing A e B números aproximados umNão. e b)Não., onde um≠ ≠ b)- Sim., e saídas se <math alttext="{displaystyle aum<b)- Sim.<img alt="a ou b.}" xmlns="http://www.w3.org/1998/Math/MathML">um>b).Não.b.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f3dbc209b9e7a3f89d6b918f0f67a5fd7cc2d6" style="vertical-align: -0.338ex; width:5.973ex; height:2.176ex;"/> É suficiente para usar ε ε - Sim.- aproximações onde <math alttext="{displaystyle epsilon ε ε <|b)- Sim. - Sim. um|/2,{displaystyle epsilon <|b-a|/2,}<img alt="{displaystyle epsilon assim por tomar cada vez mais pequeno ε ε - Sim. (aproximando-se 0), um eventualmente pode decidir se <math alttext="{displaystyle aum<b)- Sim.<img alt="a ou b.}" xmlns="http://www.w3.org/1998/Math/MathML">um>b).Não.b.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f3dbc209b9e7a3f89d6b918f0f67a5fd7cc2d6" style="vertical-align: -0.338ex; width:5.973ex; height:2.176ex;"/>

Outras propriedades

Os números reais computáveis não compartilham todas as propriedades dos números reais usados na análise. Por exemplo, o menor limite superior de uma sequência computável crescente limitada de números reais computáveis não precisa ser um número real computável. Uma sequência com esta propriedade é conhecida como sequência de Specker, pois a primeira construção deve-se a Ernst Specker em 1949. Apesar da existência de contra-exemplos como estes, partes do cálculo e da análise real podem ser desenvolvidas no campo dos números computáveis, levando para o estudo da análise computável.

Todo número computável é aritmeticamente definível, mas não vice-versa. Existem muitos números reais não computáveis aritmeticamente definíveis, incluindo:

• qualquer número que codifique a solução do problema de parada (ou qualquer outro problema indecidível) de acordo com um esquema de codificação escolhido.
• A constante do Chaitin, Ω Ω Não. - Sim., que é um tipo de número real que é Turing equivalente ao problema de parada.

Ambos os exemplos de fato definem um conjunto infinito de números definíveis e não computáveis, um para cada máquina de Turing Universal. Um número real é computável se e somente se o conjunto de números naturais que ele representa (quando escrito em binário e visto como uma função característica) é computável.

O conjunto de números reais computáveis (assim como todo subconjunto contável e densamente ordenado de reais computáveis sem fins) é isomórfico de ordem ao conjunto de números racionais.

Cordas de dígitos e os espaços de Cantor e Baire

O artigo original de Turing definiu números computáveis da seguinte forma:

Um número real é computável se sua sequência de dígitos pode ser produzida por algum algoritmo ou máquina de Turing. O algoritmo leva um inteiro n≥ ≥ 1{displaystyle ngeq 1} como entrada e produz o nNão.-o dígito da expansão decimal do número real como saída.

(A expansão decimal de a refere-se apenas aos dígitos após o ponto decimal.)

Turing sabia que esta definição é equivalente à ε ε - Sim.- definição de aproximação dada acima. O argumento prossegue da seguinte forma: se um número for computável no sentido Turing, também é computável no ε ε - Sim. sentido: se log _{10}(1/epsilon)}" xmlns="http://www.w3.org/1998/Math/MathML">n>log10.⁡ ⁡ (1/ε ε ){displaystyle n>log _{10}(1/epsilon)} log_{10} (1/epsilon)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9bd94300e7f9be6774a24ce634de8d722b248b4" style="vertical-align: -0.838ex; width:14.419ex; height:2.843ex;"/>, então o primeiro n dígitos da expansão decimal para um fornecer um ε ε - Sim. aproximação das legislações um. Para o converso, escolhemos um ε ε - Sim. número real computável um e gerar aproximações cada vez mais precisas até o no dígito após o ponto decimal é certo. Isso sempre gera uma expansão decimal igual a um mas pode indevidamente terminar em uma sequência infinita de 9 em que caso deve ter uma expansão decimal adequada (e assim computável).

A menos que certas propriedades topológicas dos números reais sejam relevantes, muitas vezes é mais conveniente lidar com elementos de 2ω ω {displaystyle 2^{omega) (total 0,1 funções valorizadas) em vez de números reais em Não.0,1][0,1]}. Os membros de 2ω ω {displaystyle 2^{omega) pode ser identificado com expansões decimais binárias, mas desde as expansões decimais .D1D2...... Dn0111...... {displaystyle.d_{1}d_{2}ldots d_{n}0111ldots } e .D1D2...... Dn10.{displaystyle.d_{1}d_{2}ldots D_{n}10 denote o mesmo número real, o intervalo Não.0,1][0,1]} só pode ser bijetivamente (e homeomorphicamente sob a topologia subconjunto) identificado com o subconjunto de 2ω ω {displaystyle 2^{omega) não terminando em todos os 1's.

Note que esta propriedade de expansões decimais significa que é impossível identificar efetivamente os números reais computáveis definidos em termos de expansão decimal e aqueles definidos na ε ε - Sim. sentido de aproximação. Hirst mostrou que não há nenhum algoritmo que leva como entrada a descrição de uma máquina de Turing que produz ε ε - Sim. aproximações para o número computável um, e produz como saída uma máquina de Turing que enumera os dígitos de um no sentido da definição de Turing. Da mesma forma, significa que as operações aritméticas sobre os reais computáveis não são eficazes em suas representações decimais como ao adicionar números decimais. Para produzir um dígito, pode ser necessário olhar arbitrariamente longe para o direito de determinar se há um transporte para o local atual. Esta falta de uniformidade é uma razão pela qual a definição contemporânea de números computáveis usa ε ε - Sim. aproximações em vez de expansões decimais.

No entanto, a partir de uma perspectiva teórico ou teórica computabilidade, as duas estruturas 2ω ω {displaystyle 2^{omega) e Não.0,1][0,1]} são essencialmente idênticos. Assim, os teóricos da computabilidade muitas vezes se referem a membros de 2ω ω {displaystyle 2^{omega) como reais. Enquanto 2ω ω {displaystyle 2^{omega) é totalmente desligado, para perguntas sobre D D 10{displaystyle Pi _{1}^{0}} classes ou aleatoriedade é mais fácil trabalhar em 2ω ω {displaystyle 2^{omega).

Elementos de ω ω ω ω (em inglês)) às vezes são chamados de reais também e embora contendo uma imagem homeomorphic de R{displaystyle mathbb {R} } }, ω ω ω ω (em inglês)) nem é localmente compacto (além de ser totalmente desconectado). Isso leva a diferenças genuínas nas propriedades computacionais. Por exemplo, x∈ ∈ R{displaystyle xin mathbb Não. satisfazendo Gerenciamento de contas Gerenciamento de contas (n∈ ∈ ω ω )φ φ (x,n){displaystyle forall (nin omega)phi (x,n)}, com φ φ (x,n)(x,n)} quantificador livre, deve ser computável enquanto o único x∈ ∈ ω ω ω ω {displaystyle xin omega ^{omega) satisfazer uma fórmula universal pode ter uma posição arbitrariamente alta na hierarquia hiperaritmética.

Use no lugar dos reais

Os números computáveis incluem os números reais específicos que aparecem na prática, incluindo todos os números algébricos reais, bem como e, π e muitos outros números transcendentes. Embora os reais computáveis esgotem aqueles reais que podemos calcular ou aproximar, a suposição de que todos os reais são computáveis leva a conclusões substancialmente diferentes sobre os números reais. A questão que surge naturalmente é se é possível descartar o conjunto completo de reais e usar números computáveis para toda a matemática. Essa ideia é atraente do ponto de vista construtivista e tem sido perseguida pelo que Errett Bishop e Fred Richman chamam de escola russa de matemática construtiva.

Para realmente desenvolver análises sobre números computáveis, alguns cuidados devem ser tomados. Por exemplo, se usarmos a definição clássica de uma sequência, o conjunto de números computáveis não é fechado sob a operação básica de tomar o supremo de uma sequência limitada (por exemplo, considere uma sequência de Specker, veja a seção acima). Essa dificuldade é abordada considerando apenas sequências que possuem um módulo de convergência computável. A teoria matemática resultante é chamada de análise computável.

Implementações de aritmética exata

Pacotes de computador representando números reais como aproximações de programas computacionais foram propostos já em 1985, sob o nome de "aritmética exata". Exemplos modernos incluem a biblioteca CoRN (Coq) e o pacote RealLib (C++). Uma linha de trabalho relacionada é baseada em pegar um programa RAM real e executá-lo com números racionais ou de ponto flutuante de precisão suficiente, como o pacote iRRAM.