¿Qué operaciones deben realizarse para realizar cualquier cálculo analógico arbitrario ? ¿Serían suficientes la suma, la resta, la multiplicación y la división?
Además, ¿alguien sabe exactamente qué problemas son manejables con el cálculo analógico, pero no con el digital?
computability
computation-models
turing-completeness
Matthew Matic
fuente
fuente
Respuestas:
Desafortunadamente, no existe un concepto "universal" de universalidad en la computación analógica. Sin embargo, este artículo de Delvenne propone un formalismo unificador para la universalidad en sistemas dinámicos discretos (por ejemplo, máquinas de Turing) y continuos (por ejemplo, ecuaciones diferenciales) y revisa algunos sistemas universales estudiados en la literatura. Aquí hay un extracto del documento que describe informalmente el procedimiento para probar la universalidad de un sistema dinámico:
Jean-Charles Delvenne, ¿Qué es una máquina de computación universal ?, Matemática aplicada y computación, Volumen 215, Número 4, 15 de octubre de 2009, páginas 1368-1374
fuente
No creo que la pregunta pueda responderse a menos que tengamos una definición de qué tipo de cálculos estamos hablando.
La universalidad de un modelo de máquina con una clase de cálculo significa que cualquier cálculo en esa clase puede ser calculado por una máquina. A menos que defina la clase de "computaciones analógicas arbitrarias", no podemos responder qué es la universalidad que tienen para ellos.
Si su pregunta es si hay sistemas físicos que a partir de un estado inicial alcanzarán otro estado en algún momento y si eso es siempre computable, entonces la respuesta depende de qué tipo de física estamos hablando y qué significa configurar una configuración inicial y observar el resultado, etc.
Si solo estamos hablando matemáticamente de física clásica (podemos establecer cualquier configuración inicial con una precisión infinita y sin ninguna consideración sobre cosas como la energía necesaria para establecer la configuración y observar el resultado es similar desde el punto de vista matemático), entonces se ha sabido durante mucho tiempo que existen ecuaciones diferenciales sobre funciones computables, su solución no es computable, ver Marian B. Pour-El y J. Ian Richards, " Computability in Analysis and Physics ", 1989.
En general, si podemos verificar la igualdad de dos números reales que proporciona una función que no es continua, las tipologías típicas de información sobre números reales y, por lo tanto, no pueden ser calculadas por una máquina de Turing ya que cualquier función (incluidas las funciones de tipo superior) es una máquina de Turing puede calcular es continuo (wrt la topología de la información).
fuente
TL; DR: Si por "computadoras analógicas", se refiere a analizadores diferenciales , la respuesta es sumadores, unidades constantes e integrador. Bournez, Campagnolo, Graça y Hainry han demostrado en 2006 ( reimpresión de pago / libre ) que un modelo idealizado permite calcular todas las funciones computables en el marco del análisis computable , y este modelo solo necesita estos 3 tipos de unidades.
Funciones trascendentales
Modelos de computación analógica
Como lo subrayaron otros, el concepto de "computación universal" es menos claro para las computadoras analógicas que para la computadora estándar, donde la noción natural de computabilidad en diferentes modelos de computación se encontró equivalente en la década de 1930 ( para más detalles, consulte la página de Wikipedia en la Tesis de Turing de la Iglesia para más detalles ) .
Para definir tal universalidad, primero se debe definir un buen modelo para el cómputo analógico, y es una tarea difícil, ya que el modelo debe ser idealizado y lo suficientemente natural como para ser útil, pero su idealización no debe dar un poder poco realista al modelo. Un ejemplo de tan buena idealización es la cinta infinita de las máquinas de Turing. El problema con las computadoras analógicas viene con números reales que podrían permitir construir cosas irrazonables como la máquina Zeno . Sin embargo, varios de estos modelos han sido propuestos y utilizados en la literatura (el GPAC es el tema principal de esta respuesta, pero trato de completar la lista a continuación, sin ningún hipercomputador ):
Poder del modelo GPAC
Bournez, Graça y Pouly mostraron en 2013 que estas computadoras analógicas pueden simular eficientemente una máquina Turing ( p.181 de un gran pdf ) y, en 2014, que las clases de complejidad P y NP son equivalentes en este modelo.
fuente
¿Sería útil proponer que un sistema analógico universal podría ser modelado por una red neuronal infinita, es decir, cualquier otro valor de entrada / salida del sistema analógico puede replicarse en una red neuronal compatible para una operación dada, y las operaciones pueden encadenarse según sea necesario?
Si bien formulé este pensamiento por mi cuenta, una búsqueda posterior ha mostrado una propuesta similar:
Podría decirse que todo lo que necesitaría son las operaciones primitivas para mover el valor de un nodo a otro. Fuera del puño que podría ser más, menos y dividir para obtener una relación entre las conexiones.
Ahora, en cuanto a los problemas intratables, observe dónde se han aplicado con éxito las redes neuronales, o si están funcionando mal debido a que se implementaron en una computadora discreta.
(y disculpas si mi punto de vista casi laico sobre este tema es muy obvio)
fuente