En informática , el no determinismo ilimitado o la indeterminación ilimitada es una propiedad de la concurrencia por la cual la cantidad de demora en el servicio de una solicitud puede volverse ilimitada como resultado del arbitraje de la disputa por recursos compartidos y, al mismo tiempo, garantizar que la solicitud finalmente será atendida . El no determinismo ilimitado se convirtió en un tema importante en el desarrollo de la semántica denotacional de la concurrencia , y más tarde se convirtió en parte de la investigación sobre el concepto teórico de hipercomputación .
Justicia
La discusión sobre el no determinismo ilimitado tiende a involucrarse con discusiones sobre justicia . El concepto básico es que todas las rutas de cálculo deben ser "justas" en el sentido de que si la máquina entra en un estado infinitamente a menudo, debe realizar todas las transiciones posibles desde ese estado. Esto equivale a exigir que se garantice que la máquina dará servicio a una solicitud si puede, ya que solo se permitirá una secuencia infinita de estados si no hay una transición que lleve a que se atienda la solicitud. De manera equivalente, cada transición posible debe ocurrir eventualmente en un cálculo infinito, aunque puede tomar una cantidad ilimitada de tiempo para que ocurra la transición. Este concepto debe distinguirse de la equidad local de lanzar una moneda "justa", por lo que se entiende que es posible que el resultado sea siempre cara para cualquier número finito de pasos, aunque a medida que aumenta el número de pasos, esto es casi seguro que no sucederá.
William D. Clinger, en su tesis de 1981, dio un ejemplo del papel del no determinismo justo o ilimitado en la fusión de cuerdas. Él definió una "fusión justa" de dos cadenas como una tercera cadena en la que cada carácter de cada cadena debe ocurrir eventualmente. A continuación, considerado como el conjunto de todas las fusiones razonables de dos cadenas de combinación (S, T) , suponiendo que sea una función monótona. Luego argumentó que fusionar (⊥, 1 ω ) ⊆ fusionar (0,1 ω ) , donde ⊥ es el arroyo vacío. Ahora fusionar (⊥, 1 ω ) = {1 ω }, por lo que debe ser que 1 ω es un elemento de fusionar (0,1 ω ) , una contradicción. Concluyó que:
- Parece que una fusión justa no se puede escribir como un programa de flujo de datos no determinista que opera en flujos.
Sobre la posibilidad de implementar el no determinismo ilimitado
Edsger Dijkstra [1976] argumentó que es imposible implementar sistemas con no determinismo ilimitado. Por esta razón, Tony Hoare [1978] sugirió que "una implementación eficiente debería intentar ser razonablemente justa".
Autómatas no deterministas
Las máquinas de Turing no deterministas solo tienen un no determinismo limitado. Asimismo, los programas secuenciales que contienen órdenes cautelosas como las únicas fuentes de no determinismo sólo tienen no determinismo limitado ( Edsger Dijkstra [1976]). Brevemente, el no determinismo de elección está limitado. Gordon Plotkin dio una prueba en su artículo original de 1976 sobre dominios de poder:
- Ahora el conjunto de segmentos iniciales de secuencias de ejecución de un programa no determinista dado P , partiendo de un estado dado, formará un árbol. Los puntos de ramificación corresponderán a los puntos de elección en el programa. Dado que siempre hay un número finito de alternativas en cada punto de elección, el factor de ramificación del árbol es siempre finito. Es decir, el árbol es finitario. Ahora bien, el lema de Kőnig dice que si cada rama de un árbol finitario es finita, también lo es el árbol mismo. En el caso presente, esto significa que si cada secuencia de ejecución de P termina, entonces solo hay un número finito de secuencias de ejecución. Entonces, si un conjunto de salida de P es infinito, debe contener [un cálculo no terminal].
Indeterminación versus autómatas no deterministas
William Clinger [1981] proporcionó el siguiente análisis de la prueba anterior de Plotkin:
- Esta prueba depende de la premisa de que si cada nodo x de una cierta rama infinita se puede alcanzar mediante algún cálculo c , entonces existe un cálculo c que visita cada nodo x en la rama. ... Claramente, esta premisa se sigue no de la lógica sino más bien de la interpretación dada a los puntos de elección. Esta premisa falla para el no determinismo de llegada [en la llegada de mensajes en el modelo Actor] debido al retraso finito [en la llegada de mensajes]. Aunque cada nodo en una rama infinita debe estar en una rama con un límite, la rama infinita no necesita tener un límite en sí misma. Por tanto, la existencia de una rama infinita no implica necesariamente un cálculo no terminal.
No determinismo y no computabilidad ilimitados
Spaan y col. [1989] han argumentado que es posible que un programa ilimitadamente no determinista resuelva el problema de la detención ; su algoritmo consta de dos partes definidas de la siguiente manera:
La primera parte del programa solicita un número natural de la segunda parte; después de recibirlo, iterará la máquina de Turing deseada para esa cantidad de pasos, y aceptará o rechazará según si la máquina aún se ha detenido.
La segunda parte del programa elige de forma no determinista un número natural a pedido. El número se almacena en una variable que se inicializa a 0; luego, el programa elige repetidamente si incrementar la variable o atender la solicitud. La restricción de equidad requiere que la solicitud sea eventualmente atendida, ya que de lo contrario hay un bucle infinito en el que solo se toma la rama "incrementar la variable".
Claramente, si la máquina se detiene, este algoritmo tiene una ruta que acepta. Si la máquina no se detiene, este algoritmo siempre rechazará, sin importar el número que devuelva la segunda parte del programa.
Argumentos para lidiar con el no determinismo ilimitado
Clinger y Carl Hewitt [ cita requerida ] han desarrollado un modelo (conocido como el modelo Actor ) de computación concurrente con la propiedad del no determinismo ilimitado construido en [Clinger 1981; Hewitt 1985; Hewitt y Agha 1991; Hewitt 2006b]; esto permite cálculos que no pueden ser implementados por Turing Machines, como se vio arriba. Sin embargo, estos investigadores enfatizan que su modelo de cómputos concurrentes no puede implementar ninguna función que esté fuera de la clase de funciones recursivas [ cita requerida ] definida por Church, Kleene, Turing, etc. (Ver Indeterminación en cómputo concurrente ).
Hewitt [2006] justificó su uso del no determinismo ilimitado argumentando que no se puede establecer un límite en cuanto al tiempo que tarda un circuito computacional llamado árbitro en establecerse (ver metaestabilidad en electrónica ). Los árbitros se utilizan en las computadoras para hacer frente a la circunstancia de que los relojes de las computadoras operan de forma asincrónica con entradas del exterior, por ejemplo. , entrada de teclado, acceso a disco, entrada de red, etc. Por lo tanto, podría tomar un tiempo ilimitado para que se reciba un mensaje enviado a una computadora y, mientras tanto, la computadora podría atravesar una cantidad ilimitada de estados.
Además, argumentó que el correo electrónico permite el no determinismo ilimitado, ya que el correo puede almacenarse en servidores indefinidamente antes de ser entregado, y que los enlaces de datos a servidores en Internet también pueden estar fuera de servicio indefinidamente. Esto dio lugar a la controversia del no determinismo ilimitado .
El análisis de equidad de Hewitt
Hewitt argumentó que los problemas de justicia se derivan en parte del punto de vista del estado global. Los modelos de cálculo más antiguos (por ejemplo , máquinas de Turing , Postproducciones, cálculo lambda , etc.) se basan en matemáticas que utilizan un estado global para representar un paso computacional . Cada paso de cálculo va de un estado global del cálculo al siguiente estado global. El enfoque del estado global continuó en la teoría de los autómatas para las máquinas de estados finitos y las máquinas apiladas , incluidas sus versiones no deterministas . Todos estos modelos tienen la propiedad del no determinismo acotado: si una máquina siempre se detiene cuando arranca en su estado inicial, entonces hay un límite en el número de estados en los que puede detenerse.
Hewitt argumentó que existe una diferencia fundamental entre las elecciones en el no determinismo del estado global y la indeterminación del orden de llegada (no determinismo) de su modelo de actor . En el no determinismo de estado global, se hace una "elección" para el "próximo" estado global. En la indeterminación de la orden de llegada, el arbitraje decide localmente cada orden de llegada en un período de tiempo ilimitado. Mientras se lleva a cabo un arbitraje local, la actividad ilimitada puede tener lugar en otros lugares. No hay un estado global y, en consecuencia, no hay "elección" que se pueda hacer en cuanto al "próximo" estado global.
Referencias
- Carl Hewitt , Peter Bishop y Richard Steiger. Un formalismo universal de actor modular para la inteligencia artificial IJCAI 1973.
- Robin Milner. Procesos: un modelo matemático de agentes informáticos en el coloquio de lógica 1973.
- Carl Hewitt y col. Acta de la conferencia de inducción y metaevaluación de actores del simposio de ACM sobre principios de lenguajes de programación, enero de 1974.
- Carl Hewitt y col. Semántica conductual de estructuras de control no recursivas Actas de Colloque sur la Programmation, abril de 1974.
- Irene Greif. Semántica de la comunicación de profesiones paralelas Tesis doctoral EECS del MIT. Agosto de 1975.
- Gordon D. Plotkin . A powerdomain construction SIAM Journal on Computing, 5: 452-487, septiembre de 1976.
- Edsger Dijkstra . Una disciplina de programación Prentice Hall . 1976.
- Carl Hewitt y Henry Baker Actores y Actas de Funcionalidad Continua de la Conferencia de Trabajo de IFIP sobre Descripción Formal de Conceptos de Programación. 1-5 de agosto de 1977.
- Gilles Kahn y David MacQueen. Corutinas y redes de procesos paralelos IFIP. 1977
- Henry Baker. Actor Sistemas de Computación en Tiempo Real MIT EECS Tesis Doctoral. Enero de 1978.
- Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
- George Milne y Robin Milner. Procesos concurrentes y su sintaxis JACM. Abril de 1979.
- COCHE Hoare . Comunicación de procesos secuenciales CACM. Agosto de 1978.
- Nissim Francez , CAR Hoare, Daniel Lehmann y Willem de Roever. Semántica del no determinismo, concurrencia y comunicación Journal of Computer and System Sciences. Diciembre de 1979.
- Nancy Lynch y Michael Fischer . Sobre describir el comportamiento de sistemas distribuidos en Semántica de Computación Concurrente. Springer-Verlag. 1979.
- Jerald Schwartz Semántica denotacional del paralelismo en Semantics of Concurrent Computation. Springer-Verlag. 1979.
- William Wadge. Un tratamiento extensivo de la semántica del interbloqueo del flujo de datos de la computación concurrente. Springer-Verlag. 1979.
- Ralph-Johan Back. Semántica del no determinismo ilimitado ICALP 1980.
- David Park. Sobre la semántica del paralelismo justo Actas de la Escuela de Invierno sobre Especificación de Software Formal. Springer-Verlarg. 1980.
- Dana Scott . ¿Qué es la semántica denotacional? Serie de conferencias distinguidas del Laboratorio de Ciencias de la Computación del MIT. 17 de abril de 1980.
- William D. Clinger, Fundamentos de la semántica del actor . Tesis de Doctorado en Matemáticas del MIT, junio de 1981.
- William D. Clinger, La llamada no determinista por necesidad no es perezosa ni por su nombre Páginas 226-234 en el Simposio sobre LISP y Programación Funcional . Pittsburgh, Pensilvania, 1982.
- Stephen Brookes, Tony Hoare y Bill Roscoe Una teoría de la comunicación de procesos secuenciales JACM. Julio de 1984.
- Carl Hewitt, The Challenge of Open Systems Byte Magazine. Abril de 1985. Reimpreso en The foundation of artificial intelligence --- un libro de consulta de Cambridge University Press. 1990.
- Bill Roscoe . No determinismo ilimitado en CSP en "Two papers on CSP", monografía técnica PRG-67, Laboratorio de Computación de la Universidad de Oxford. Julio de 1988.
- Lenguajes de cláusulas de Carl Hewitt y Gul Agha Guarded Horn: ¿son deductivos y lógicos? Conferencia internacional sobre sistemas informáticos de quinta generación, Ohmsha 1988. Tokio. También en Inteligencia Artificial en MIT , Vol. 2. MIT Press 1991.
- AW Roscoe: La teoría y práctica de la concurrencia , Prentice Hall, ISBN 0-13-674409-5 .
- Edith Spaan, Leen Torenvliet y Peter van Emde Boas. No determinismo, equidad y una analogía fundamental . Boletín EATCS, 37: 186-193, 1989.
- David A. Schmidt, La estructura de los lenguajes de programación mecanografiados . MIT Press, Cambridge, Massachusetts, 1994.
- Butler, MJ y Morgan, CC Action Systems, Unbounded Nondeterminism y Infinite Traces Aspecto formal de la informática. 1995
- Thomas A. Sudkamp, Idiomas y máquinas . 2ª Edición. Addison-Wesley, Reading, Mass., 1997.
- Luca Aceto y Andrew D. Gordon (editores). Cálculos de procesos algebraicos: los primeros veinticinco años y más allá ' Álgebra de procesos. Bertinoro, Forl`ı, Italia, 1 a 5 de agosto de 2005
- Stephen Brooke. Remontando CSP en cálculos de procesos algebraicos: los primeros veinticinco años y más allá . Agosto de 2005.
- AW Roscoe: La teoría y práctica de la concurrencia , Prentice Hall, ISBN 0-13-674409-5 . Revisado en 2005.
- Carl Hewitt. La repetida desaparición de la programación lógica y por qué se reencarnará Lo que salió mal y por qué: lecciones de la investigación y las aplicaciones de la IA. Informe técnico SS-06-08. AAAI Press. Marzo de 2006.
- Carl Hewitt, ¿Qué es el compromiso? COIN @ AAMAS Físico, Organizacional y Social . 27 de abril de 2006.
- Toby Ord. Hipercomputación: calcular más de lo que la máquina de Turing puede calcular en arxiv.org .