No determinismo ilimitado

En informática , el no determinismo ilimitado o la indeterminación ilimitada se refiere a un comportamiento en la concurrencia (múltiples tareas ejecutándose a la vez) donde un proceso puede enfrentar retrasos impredecibles debido a la competencia por recursos compartidos ^{[ 1 ]} —como una impresora o memoria— o tener infinitas opciones para elegir en un momento dado. ^{[ 2 ]} Si bien estos retrasos o elecciones pueden ser arbitrariamente grandes, el proceso generalmente tiene la garantía de completarse eventualmente bajo ciertas condiciones (por ejemplo, equidad en la asignación de recursos).

Este concepto, explorado en modelos abstractos más que en sistemas prácticos, se volvió significativo en el desarrollo de descripciones matemáticas de dichos sistemas ( semántica denotacional ) y posteriormente contribuyó a la investigación sobre teorías de computación avanzadas ( hipercomputación ). ^{[ 3 ]}

El no determinismo ilimitado suele analizarse junto con el concepto de equidad . En este contexto, la equidad implica que si un sistema regresa indefinidamente a un estado determinado, eventualmente deberá intentar todos los pasos posibles a partir de ese estado. Por ejemplo, si una tarea espera para usar una herramienta compartida, como una impresora, no puede demorarse indefinidamente; la equidad garantiza que le llegue su turno, incluso si la espera es impredecible y prolongada. Esta garantía es importante cuando un sistema se ejecuta indefinidamente, ya que evita que se ignore alguna opción con el tiempo.

Esta idea de justicia no es como lanzar una moneda "justa" indefinidamente. Con una moneda, el azar implica que eventualmente saldrán cara y cruz, pero no hay ninguna regla que lo obligue; la pura suerte podría retrasar un resultado durante un tiempo arbitrariamente largo. En el no determinismo ilimitado, la justicia no consiste en esperar que cada paso ocurra; es un requisito estricto que ocurra, independientemente del azar.

Edsger Dijkstra argumentó que es imposible implementar sistemas con no determinismo ilimitado. ^{[ 5 ]} Por esta razón, Tony Hoare sugirió que "una implementación eficiente debería intentar ser razonablemente justa". ^{[ 6 ]}

A diferencia de los sistemas con no determinismo ilimitado, las máquinas de Turing no deterministas exhiben únicamente no determinismo limitado. Esto significa que sus elecciones —como qué camino tomar en un punto de decisión— se limitan a un número fijo de opciones en cada paso, lo que mantiene los retrasos predecibles y finitos. De manera similar, los programas secuenciales que utilizan comandos protegidos (reglas que eligen una acción de un conjunto en función de condiciones) como su única fuente de no determinismo también permanecen limitados, ya que el número de elecciones posibles no crece sin límite. ^{[ 5 ]} En estos casos, conocidos como no determinismo de elección, el comportamiento del sistema permanece restringido. El matemático Gordon Plotkin formalizó esto en su artículo original sobre dominios de potencia , demostrando que dicho no determinismo tiene límites claros, a diferencia de los retrasos ilimitados que se observan en los sistemas concurrentes:

Ahora bien, el conjunto de segmentos iniciales de secuencias de ejecución de un programa no determinista P dado , 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 finito. El lema de Kőnig establece que si cada rama de un árbol finito es finita, entonces también lo es el árbol mismo. En este caso, esto significa que si cada secuencia de ejecución de P termina, entonces solo hay un número finito de secuencias de ejecución. Por lo tanto, si un conjunto de salida de P es infinito, debe contener [un cálculo que no termina]. ^{[ 7 ]}

Spaan et al. han sugerido que el no determinismo no acotado podría resolver teóricamente el problema de la parada , un famoso desafío en la teoría de la computabilidad que pregunta si una máquina de Turing se detendrá o continuará indefinidamente con una entrada dada, un problema que se ha demostrado irresoluble por las máquinas estándar. Proponen un algoritmo dividido en dos partes: ^{[ 8 ]}

1. La primera parte solicita a la segunda un número natural y, a continuación, ejecuta la máquina de Turing durante exactamente ese número de pasos. Si la máquina se detiene dentro de ese plazo, el algoritmo acepta (indicando que "se detiene"); de lo contrario, rechaza ("no se ha detenido").
2. La segunda parte elige de forma no determinista un número natural cuando se le solicita, comenzando en 0. Elige repetidamente entre dos acciones: incrementar el número en 1 o devolver el número actual a la primera parte. La restricción de equidad garantiza que finalmente se envíe el número, evitando un bucle infinito de solo incrementarlo.

Si la máquina de Turing se detiene después de un número finito de pasos (por ejemplo, 50), el algoritmo tiene una ruta donde la segunda parte selecciona 50 o más, lo que permite a la primera parte detectar la parada y aceptar. Si la máquina nunca se detiene, la primera parte rechaza para cualquier número finito elegido, ya que ninguna ejecución fija puede confirmar un proceso infinito. El no determinismo ilimitado permite a la segunda parte explorar cada número posible a lo largo de un tiempo infinito, y la equidad garantiza que se haga una elección, lo que implica que se evalúan todas las posibilidades. Esto sugiere que el algoritmo podría resolver el problema de la parada, aunque se basa en un proceso infinito, una construcción teórica que utiliza pasos ilimitados para evaluar un comportamiento ilimitado, lo que lo distingue de las capacidades finitas de las máquinas de Turing estándar y lo vincula con la no computabilidad .

Clinger y Carl Hewitt desarrollaron un modelo (conocido como el modelo de actor ) de computación concurrente con la propiedad de no determinismo ilimitado, incorporado en [Clinger 1981; ^{[ 9 ]} ; ^{[ 10 ]} ; ^{[ 11 ]} ]; esto permite realizar computaciones que no pueden ser implementadas por máquinas de Turing, como se mencionó anteriormente. Sin embargo, estos investigadores enfatizan que su modelo de computación concurrente no puede implementar ninguna función que esté fuera de la clase de funciones recursivas definidas por Church, Kleene, Turing, etc. (Véase Indeterminación en la computación concurrente ).

Hewitt justificó su uso del no determinismo ilimitado argumentando que no existe un límite para el tiempo que tarda un circuito computacional llamado árbitro en estabilizarse (véase metaestabilidad en electrónica ). Los árbitros se utilizan en las computadoras para gestionar la circunstancia de que los relojes de las computadoras operan de forma asíncrona con la entrada externa, por ejemplo , la entrada del teclado, el acceso al disco, la entrada de red, etc. Por lo tanto, podría tardar un tiempo ilimitado en recibir un mensaje enviado a una computadora y, mientras tanto, la computadora podría pasar por un número ilimitado de estados.

Además, argumentó que el correo electrónico permite un 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 origen a la controversia del no determinismo ilimitado . ^{[ 12 ]}

Hewitt argumentó que los problemas de equidad se derivan en parte del punto de vista del estado global. Los modelos de computación más antiguos (por ejemplo, las máquinas de Turing , las postproducciones, el cálculo lambda , etc.) se basan en matemáticas que utilizan un estado global para representar un paso computacional . Cada paso computacional va de un estado global de la computación al siguiente. El enfoque del estado global se continuó en la teoría de autómatas para máquinas de estados finitos y máquinas de pila descendente , incluidas sus versiones no deterministas . Todos estos modelos tienen la propiedad de no determinismo acotado: si una máquina siempre se detiene al comenzar 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 decisiones en el no determinismo del estado global y la indeterminación (no determinismo) del orden de llegada de su modelo de actor . En el no determinismo del estado global, se toma una "elección" para el "siguiente" estado global. En la indeterminación del orden de llegada, el arbitraje decide localmente cada orden de llegada en un lapso de tiempo ilimitado. Mientras se lleva a cabo un arbitraje local, puede haber actividad ilimitada en otros lugares. No hay un estado global y, por consiguiente, no hay ninguna "elección" que tomar respecto al "siguiente" estado global.

• Hewitt, Carl ; Bishop, Peter; Steiger, Richard (agosto de 1973). «Un formalismo ACTOR modular universal para la inteligencia artificial». Actas de la 3.ª conferencia internacional conjunta sobre inteligencia artificial . IJCAI'73. Stanford: Morgan Kaufmann. págs. 235-245 . 
• Milner, Robin (1973). "Procesos: un modelo matemático de agentes computacionales". Actas del Coloquio de Lógica . Coloquio de Lógica '73. Bristol: North Holland. págs. 157–173 . 
• Hewitt, Carl ; Bishop, Peter; Greif, Irene ; Smith, Brian; Matson, Todd; Steiger, Richard (octubre de 1973). "Inducción de actores y metaevaluación". Actas del primer simposio anual ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación . POPL'73. Boston, Massachusetts: Association for Computing Machinery. págs. 153–168 . doi : 10.1145/512927.512942 . 
• Hewitt, Carl ; Bishop, Peter; Steiger, Richard; Greif, Irene ; Smith, Brian; Matson, Todd; Hale, Roger (abril de 1974). «Semántica conductual de estructuras de control no recursivas». En Robinet, B. (ed.). Actas del Coloquio sobre la programación . Simposio de Programación. París: Springer Berlin Heidelberg. pp. 385–407 . doi : 10.1007/3-540-06859-7_147 . ISBN  9783540378198.
• Greif, Irene (agosto de 1975). Semántica de procesos paralelos comunicantes (tesis doctoral). Instituto Tecnológico de Massachusetts, Departamento de Ingeniería Eléctrica y Ciencias de la Computación. hdl : 1721.1/57710 .
• Hewitt, Carl ; Baker, Henry (agosto de 1977). «Actores y funcionales continuos». En Neuhold, Erich J. (ed.). Actas de la Conferencia de Trabajo de la IFIP sobre la Descripción Formal de Conceptos de Programación . IFIP'78. St. Andrews, NB, Canadá: North-Holland. ISBN 9780444851079.
• Kahn, Gilles ; MacQueen, David (1976). Coroutines and Networks of Parallel Processes (Informe de investigación) . Recuperado el 9 de marzo de 2022 .
• Baker, Henry (enero de 1978). Sistemas de actores para computación en tiempo real (tesis doctoral). Instituto Tecnológico de Massachusetts, Departamento de Ingeniería Eléctrica e Informática.
• Smyth, Michael (1978). "Dominios de poder" . Journal of Computer and System Sciences . 16 : 23–36 . doi : 10.1016/0022-0000(78)90048-X .
• Milne, George; Milner, Robin (abril de 1979). "Procesos concurrentes y su sintaxis" . Journal of the ACM . 6 (2): 302– 321. doi : 10.1145/322123.322134 . S2CID 16565064 . 
• Francez, Nissim ; Hoare, CAR ; Lehmann, Daniel J.; de Roever, Willem P. (diciembre de 1979). "Semántica del no determinismo, la concurrencia y la comunicación" . Journal of Computer and System Sciences . 19 (3): 290–308 . doi : 10.1016/0022-0000(79)90006-0 .
• Lynch, Nancy A.; Fischer , Michael J. (julio de 1979). «Sobre la descripción del comportamiento y la implementación de sistemas distribuidos». En Kahn, Gilles (ed.). Actas del Simposio Internacional sobre Semántica de la Computación Concurrente . Semántica de la Computación Concurrente. Evian, Francia: Springer-Verlag. pp. 147–171 . doi : 10.1007/BFb0022468 . ISBN  9783540351634.
• Schwartz, Jerald S. (julio de 1979). «Semántica denotacional del paralelismo». En Kahn, Gilles (ed.). Actas del Simposio Internacional sobre Semántica de la Computación Concurrente . Semántica de la Computación Concurrente. Evian, Francia: Springer-Verlag. pp. 191–202 . doi : 10.1007/BFb0022470 . ISBN  9783540351634.
• Wadge, William W. (julio de 1979). «Un tratamiento extensional del interbloqueo de flujo de datos». En Kahn, Gilles (ed.). Actas del Simposio Internacional sobre Semántica de la Computación Concurrente . Semántica de la Computación Concurrente. Evian, Francia: Springer-Verlag. pp. 285–299 . doi : 10.1007/BFb0022475 . ISBN  9783540351634.
• Back, Ralph-Johan (julio de 1980). "Semántica del no determinismo ilimitado". En de Bakker, Jaco ; van Leeuwen, Jan (eds.). Séptimo Coloquio sobre Autómatas, Lenguajes y Programación . Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Noordwijkerhout, Países Bajos: Springer-Verlag Berlin Heidelberg. pp. 51–63 . doi : 10.1007/3-540-10003-2_59 . 
• Park, David (1979). "Sobre la semántica del paralelismo justo". En Bjørner, Dines (ed.). Abstract Software Specifications . Escuela de Invierno de Copenhague de 1979. Copenhague: Springer-Verlag Berlin Heidelberg. pp. 504–526 . doi : 10.1007/3-540-10007-5_47 . 

• Dana Scott . ¿Qué es la semántica denotacional? Ciclo de conferencias magistrales del Laboratorio de Ciencias de la Computación del MIT. 17 de abril de 1980.

• Clinger, William (agosto de 1982). "La llamada no determinista por necesidad no es ni perezosa ni de nombre". En Park, David MR; Friedman, Daniel P. (eds.). Actas del simposio de la ACM de 1982 sobre LISP y programación funcional . LFP'82. Pittsburgh, Pensilvania: Association for Computing Machinery. págs. 226–234 . doi : 10.1145/800068.802154 . 
• Brookes, SD; Hoare, CAR ; Roscoe, AW (julio de 1984). "Una teoría de los procesos secuenciales comunicantes" . Journal of the ACM . 31 (3): 560– 599. doi : 10.1145/828.833 . S2CID 488666 . 
• Roscoe, AW (enero de 1988). "No determinismo ilimitado en CSP". Dos artículos sobre CSP (PDF) (Monografía técnica). Laboratorio de Computación de la Universidad de Oxford. PRG67 . Recuperado el 10 de marzo de 2022 .
• Roscoe, AW (10 de noviembre de 1997). Teoría y práctica de la concurrencia . Prentice-Hall. ISBN 9780136744092.
• Schmidt, David A. (marzo de 1994). La estructura de los lenguajes de programación tipados . The MIT Press. ISBN 9780262193498.
• Butler, Michael ; Morgan, Carroll (enero de 1995). "Sistemas de acción, no determinismo ilimitado y trazas infinitas" . Aspectos formales de la computación . 7 (1): 37– 53. doi : 10.1007/BF01214622 . S2CID 2135743 . 
• Sudkamp, ​​Thomas A. (3 de enero de 1997). Lenguajes y máquinas: Una introducción a la teoría de la informática (2.ª  ed.). Addison-Wesley. ISBN 9780201821369.
• Aceto, Luca; Gordon, Andrew D. , eds. (agosto de 2005). Cálculos de procesos algebraicos: los primeros veinticinco años y más allá . PA'05. Centro Residencial Bertinoro (Forlì) de la Universidad de Bolonia, Italia: BRICS.
• Brookes, Stephen (agosto de 2005). "Retracing CSP" (PDF) . En Aceto, Luca; Gordon, Andrew D. (eds.). Algebraic Process Calculi: The First Twenty Five Years and Beyond . PA'05. University of Bologna Residential Center Bertinoro (Forlì), Italia: BRICS. pp. 75–80 . Recuperado el 10 de marzo de 2022 .