O que é necessário para a computação analógica universal?

Quais operações precisam ser executadas para realizar qualquer cálculo analógico arbitrário ? Adição, subtração, multiplicação e divisão seriam suficientes?

Além disso, alguém sabe exatamente quais problemas são tratáveis ​​usando computação analógica, mas não com digital?

Infelizmente, não existe um conceito "universal" de universalidade na computação analógica. No entanto, este artigo de Delvenne propõe um formalismo unificador para a universalidade em sistemas dinâmicos discretos (por exemplo, máquinas de Turing) e contínuas (por exemplo, equações diferenciais) e revisa alguns sistemas universais estudados na literatura. Aqui está um trecho do artigo que descreve informalmente o procedimento para provar a universalidade de um sistema dinâmico:

Mas a maioria dos sistemas dinâmicos estudados em matemática e física tem um espaço de estado incontável, por exemplo, autômatos celulares, equações diferenciais, mapas lineares por partes, etc. Exemplos desses sistemas foram universais. Seu problema de parada é imitado da máquina de Turing da seguinte maneira. Escolhemos uma família contável específica de estados iniciais e uma família contável de estados finais ou conjuntos finais de estados. Então, o problema de parada recebe um estado inicial e um estado final / conjunto de estados, se a trajetória iniciada no estado inicial alcançará o estado final / conjunto de estados. Exemplos mais específicos são dados na Seção 7.

Jean-Charles Delvenne, O que é uma máquina de computação universal ?, Matemática Aplicada e Computação, Volume 215, Edição 4, 15 de outubro de 2009, Páginas 1368-1374

Acho que a pergunta não pode ser respondida, a menos que tenhamos uma definição de que tipo de computação estamos falando.

A universalidade de um modelo de máquina em uma classe de computaçãow significa que qualquer computação nessa classe pode ser calculada por uma máquina. A menos que você defina a classe de "cálculos analógicos arbitrários", não podemos responder o que é universalidade escrita para eles.

Agora, as funções listadas fornecerão apenas polinômios e seu quociente, que é uma classe bastante pequena de funções reais, você não pode nem mesmo calcular funções simples como , , , ... usando eles. ⌊ x ⌋ $2^x$$\lfloor x \rfloor$$\sqrt x$

Se sua pergunta é se existem sistemas físicos que, a partir de um estado inicial, atingem outro estado em algum tempo e se isso é sempre computável, então a resposta depende de que tipo de física estamos falando e o que significa configurar uma configuração inicial e observação do resultado, etc.

Se estamos apenas falando matematicamente sobre física clássica (podemos definir qualquer configuração inicial com precisão infinita e sem nenhuma consideração sobre coisas como a energia necessária para definir a configuração e observar o resultado da mesma forma do ponto de vista matemático), então já se sabe há muito tempo que há equações diferenciais sobre funções computáveis, e sua solução não é computável, veja Marian B. Pour-El e J. Ian Richards, " Computabilidade em Análise e Física ", 1989.

$n>4$

Geralmente, se pudermos apenas verificar a igualdade de dois números reais, que fornece uma função que não é contínua, por meio de tipologias típicas de informação sobre números reais e, portanto, não podem ser computadas por uma máquina de Turing, pois qualquer função (incluindo funções de tipo superior) que uma máquina de Turing A computação pode ser contínua (escreva a topologia da informação).

TL; DR: Se por "computadores analógicos", você quer dizer analisadores diferenciais , a resposta é somadores, unidades constantes e integrador. Bournez, Campagnolo, Graça e Hainry mostraram em 2006 ( reimpressão paywalled / free ) que um modelo idealizado dele permite calcular todas as funções computáveis ​​no âmbito da análise computacional , e esse modelo precisa apenas desses 3 tipos de unidades.

Funções transcendentais

$\sin$$\exp$$\log$

Modelos de computação analógica

Conforme enfatizado por outros, o conceito de “computação universal” é menos claro para computadores analógicos do que para computadores comuns, onde a noção natural diferente de computabilidade em diferentes modelos de computação foi encontrada na década de 1930 (equivalente à tese de Church Turing para detalhes ). .

Para definir tal universalidade, deve-se primeiro definir um bom modelo para computação analógica, e é uma tarefa difícil, uma vez que o modelo deve ser idealizado e natural o suficiente para ser útil, mas sua idealização não deve dar poder irrealista ao modelo. Um exemplo de uma idealização tão boa é a fita infinita das máquinas de Turing. O problema com computadores analógicos vem com números reais que podem permitir criar coisas irracionais como a máquina Zeno . No entanto, vários desses modelos foram propostos e utilizados na literatura (o GPAC é o principal assunto desta resposta, mas tento estar completo na lista abaixo, sem nenhum hipercomputador ):

• o General Purpose Analogue Computer (GPAC), definido por Claude E. Shannon em 1941 ( paywalled pdf ) para modelar analisadores diferenciais . A definição do GPAC foi refinada recentemente e seu poder de computação foi revisado para cima;
• a máquina Blum-Shub-Smale , que atua em momentos discretos em números reais. Está intimamente relacionado ao modelo Real RAM , freqüentemente usado em geometria computacional;
• $\mathbb R$
• Redes neurais ;
• Análise computável , que analisa os números reais computáveis ​​por uma máquina de Turing.

Poder do modelo GPAC

$\Gamma$$\zeta$$y(t)=\Gamma(t)$Parece que há muito tempo esse computador analógico não é "universal", pois não pode gerar algumas funções computáveis ​​razoáveis, usadas por matemáticos.

$f$$y(t)$$f(x)$$x$$\gamma$$\zeta$.

Bournez, Graça e Pouly mostraram em 2013 que esses computadores analógicos podem simular com eficiência uma máquina de Turing ( p.181 de um grande pdf ) e, em 2014, que as classes de complexidade P e NP são equivalentes neste modelo.

Seria útil propor que um sistema analógico universal pudesse ser modelado por uma rede neural infinita, ou seja, qualquer outro valor de entrada / saída de sistema analógico pode ser replicado como rede neural correspondente a uma determinada operação, e as operações podem ser encadeadas conforme necessário?

Embora eu tenha formulado esse pensamento por conta própria, uma pesquisa subsequente mostrou uma proposta semelhante:

O que surge é uma tese do tipo Church-Turing, aplicada ao campo da computação analógica, que apresenta o modelo de rede neural no lugar da máquina de Turing digital (veja aqui ).

Indiscutivelmente, tudo o que você precisa é de operações primitivas para mover o valor de um nó para outro. Solte o manguito que pode ser mais, menos e divida para obter a relação entre as conexões.

Agora, quanto aos problemas intratáveis, observe onde as redes neurais foram aplicadas com sucesso ou estão com desempenho insuficiente devido à implementação em um computador discreto.

(e peço desculpas se a minha visão quase leiga sobre esse assunto for flagrantemente óbvia)