Las máquinas de Turing tienen un alfabeto de símbolos formales , un estado y una descripción basada en reglas de transición de cómo se realiza un cálculo.
El Modelo de actor a veces se menciona como un modelo computacional más poderoso que las máquinas de Turing (no en lo que puede calcular, sino en otros aspectos).
- ¿Es The Actor Model una alternativa completa a la máquina de torneado como modelo computacional?
- ¿El modelo de actor también tiene una descripción de cálculo formal basada en símbolos similar a la máquina de Turing?
- ¿Se supone que los actores son equivalentes a la máquina de Turing, ya que cada mensaje se procesa secuencialmente (y atómicamente)?
Hay muchos resultados teóricos basados en máquinas de Turing, por ejemplo, el problema de detención, la capacidad de decisión, la relación con el teorema de incompletitud de Gödel, etc.
¿Se pueden generalizar formalmente estas pruebas al modelo de actor? ¿Se ha hecho esto?
terminology
computability
reference-request
programming-languages
computation-models
Adi Shavit
fuente
fuente
Respuestas:
Los informáticos generalmente están de acuerdo en que la tesis de Church Turing [1] es correcta y definitiva, es decir, que las máquinas de Turing describen la computación y que las formas más poderosas realmente no existen, y asumen que algún modelo es "más poderoso" que Turing máquinas con escepticismo extremo, incluso cerca de la hostilidad. [2] Los neófitos del campo que no entienden completamente el concepto son presa de los eslóganes de marketing de alguna teoría como "más poderosos" que las máquinas de Turing, pero esas afirmaciones rara vez son hechas por científicos informáticos de renombre.
pero, por otro lado, muchos modelos de computación están completos. por lo tanto, en CS existe en la práctica una actitud tolerante, "vive y deja vivir" con muchos modelos diferentes de computación que proliferan dependiendo de lo que sea más relevante y conveniente para el problema estudiado. La mayoría de los modelos de programación básicos son Turing completos con estructuras básicas como memoria, condicionales y bucles, subrutinas, etc. así que las afirmaciones más razonables son: "el modelo [x] es más adecuado para estudiar [y] porque [z]". El modelo de actor se centra en la transmisión de mensajes, la comunicación, la concurrencia y cierta seguridad.
sin embargo, existe un debate mayormente filosófico en CS sobre algunos modelos que son "más poderosos".
[1] Tesis de la Iglesia de Turing
[2] Modelos interactivos de computación vs tesis de Church Turing
fuente