stringtranslate.com

No determinismo ilimitado

En informática , el no determinismo ilimitado o indeterminación ilimitada es una propiedad de la concurrencia por la cual la demora en atender una solicitud puede volverse ilimitada como resultado del arbitraje de la contención por recursos compartidos mientras se garantiza 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 [1] .

Justicia

El debate sobre el no determinismo ilimitado tiende a mezclarse con debates sobre la equidad . 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 atenderá 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, todas las transiciones posibles deben ocurrir eventualmente en un cálculo infinito, aunque puede llevar una cantidad ilimitada de tiempo para que la transición ocurra. Este concepto debe distinguirse de la equidad local de lanzar una moneda "justa", por la cual se entiende que es posible que el resultado siempre sea cara para cualquier número finito de pasos, aunque a medida que aumenta el número de pasos, esto casi seguramente no sucederá.

Un ejemplo del papel del no determinismo justo o ilimitado en la fusión de cadenas fue dado por William D. Clinger , en su tesis de 1981. Definió una "fusión justa" de dos cadenas como una tercera cadena en la que cada carácter de cada cadena debe aparecer eventualmente. Luego consideró el conjunto de todas las fusiones justas de dos cadenas merge (S, T) , asumiendo que es una función monótona. Luego argumentó que merge (⊥,1 ω )⊆ merge (0,1 ω ) , donde ⊥ es la secuencia vacía. Ahora merge (⊥,1 ω ) = {1 ω }, por lo que debe ser que 1 ω es un elemento de merge (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 secuencias. [2]

Sobre la posibilidad de implementar el no determinismo ilimitado

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

Autómatas no deterministas

Las máquinas de Turing no deterministas solo tienen un no determinismo acotado. Del mismo modo, los programas secuenciales que contienen comandos protegidos como únicas fuentes de no determinismo solo tienen un no determinismo acotado. [3] En resumen, el no determinismo de elección es acotado. Gordon Plotkin dio una prueba en su artículo original sobre dominios de potencia:

Ahora bien, el conjunto de segmentos iniciales de secuencias de ejecución de un programa no determinista dado P , a partir de un estado dado, formará un árbol. Los puntos de ramificación corresponderán a los puntos de elección en el programa. Puesto 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. Ahora bien, el lema de König dice que si cada rama de un árbol finito es finita, entonces también lo es el árbol mismo. En el presente 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ómputo no terminante]. [5]

Indeterminación versus autómatas no deterministas

William Clinger 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 determinada rama infinita puede alcanzarse mediante algún cálculo c , entonces existe un cálculo c que visita cada nodo x de la rama. ... Claramente, esta premisa no se desprende 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 del Actor] debido al retraso finito [en la llegada de mensajes]. Aunque cada nodo de 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 lo tanto, la existencia de una rama infinita no implica necesariamente un cálculo no terminal. [2]

No determinismo ilimitado y no computabilidad

Spaan et al. han argumentado que es posible que un programa no determinista ilimitado resuelva el problema de detención ; su algoritmo consta de dos partes definidas de la siguiente manera: [6]

La primera parte del programa solicita un número natural a la segunda parte; después de recibirlo, iterará la máquina de Turing deseada durante esa cantidad de pasos y lo aceptará o rechazará según si la máquina ya se ha detenido.

La segunda parte del programa elige de manera no determinista un número natural cuando se lo solicita. 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 imparcialidad requiere que la solicitud sea atendida en algún momento, ya que de lo contrario se produce 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 la acepta. Si la máquina no se detiene, este algoritmo siempre la rechazará, sin importar qué número devuelva la segunda parte del programa.

Argumentos para abordar el no determinismo ilimitado

Clinger y Carl Hewitt [ cita requerida ] han desarrollado un modelo (conocido como el modelo de Actor ) de computación concurrente con la propiedad de no determinismo ilimitado incorporada en [Clinger 1981; [7] ; [8] ; [9] ]; esto permite cálculos que no pueden ser implementados por las Máquinas de Turing, como se vio anteriormente. Sin embargo, estos investigadores enfatizan que su modelo de cálculos concurrentes no puede implementar ninguna función que esté fuera de la clase de funciones recursivas [ cita requerida ] definidas por Church, Kleene, Turing, etc. (Ver Indeterminación en computación concurrente ).

Hewitt justificó su uso del no determinismo ilimitado argumentando que no hay límite que se pueda establecer en el tiempo que tarda un circuito computacional llamado árbitro en establecerse (ver metaestabilidad en electrónica ). Los árbitros se utilizan en computadoras para lidiar con la circunstancia de que los relojes de la computadora operan de manera asincrónica con la entrada desde el 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 un número ilimitado de estados.

Sostuvo además 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 lugar a la controversia del no determinismo ilimitado . [10]

El análisis de Hewitt sobre la equidad

Hewitt argumentó que los problemas de equidad se derivan en parte del punto de vista del estado global. Los modelos más antiguos de computación (por ejemplo, las máquinas de Turing , las posproducciones, 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 del cómputo al siguiente estado global. El enfoque del estado global se continuó en la teoría de autómatas para las máquinas de estados finitos y las máquinas de pila descendente , incluidas sus versiones no deterministas . Todos estos modelos tienen la propiedad del no determinismo acotado: si una máquina siempre se detiene cuando se inicia 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 del estado global, se hace una "elección" para el "próximo" estado global. En la indeterminación del orden de llegada, el arbitraje decide localmente cada orden de llegada en una cantidad de tiempo ilimitada. Mientras se lleva a cabo un arbitraje local, puede tener lugar una actividad ilimitada en otro lugar. No hay un estado global y, en consecuencia, no hay "elección" que hacer en cuanto al "próximo" estado global.

Referencias

  1. ^ Ord, Toby (2002). "Hipercomputación: computación más allá de la máquina de Turing". arXiv : math/0209332 .
  2. ^ ab Clinger, William D. (1 de mayo de 1981). Fundamentos de la semántica de actores (Informe técnico sobre inteligencia artificial). Instituto Tecnológico de Massachusetts. hdl :1721.1/6935.
  3. ^ de Dijkstra, Edsger (1976). Una disciplina de programación . Serie Prentice-Hall sobre computación automática. Prentice-Hall. ISBN 9780613924115.
  4. ^ Hoare, CAR (agosto de 1978). "Comunicación de procesos secuenciales". Comunicaciones de la ACM . 21 (8): 666–677. doi : 10.1145/359576.359585 . S2CID  849342.
  5. ^ Plotkin, Gordon (septiembre de 1976). "Una construcción de dominio de potencia". Revista SIAM de Computación . 5 (3): 452–487. doi :10.1137/0205035.
  6. ^ Spaan, Edith; Torenvliet, Leen; van Emde Boas, Peter (febrero de 1989). "No determinismo, imparcialidad y una analogía fundamental". Boletín de la EATCS . 37 : 186–193.
  7. ^ Hewitt, Carl (abril de 1985). "El desafío de los sistemas abiertos". BYTE . McGraw Hill. págs. 223–242. ISSN  0360-5280.Reimpreso como Hewitt, Carl (abril de 1990). "El desafío de los sistemas abiertos". En Partridge, Derek; Wilks, Yorick (eds.). Los fundamentos de la inteligencia artificial: un libro de consulta . Cambridge University Press. págs. 383–395. ISBN 9780521359443.
  8. ^ Hewitt, Carl ; Agha, Gul (1988). "Lenguajes con cláusulas Horn protegidas: ¿son deductivos y lógicos?". Actas de la Conferencia Internacional sobre Sistemas Informáticos de Quinta Generación . FGCS 1988. Tokio, Japón: OHMSHA Ltd. Tokio y Springer-Verlag. pp. 650–657. ISBN 3540195580.También como Hewitt, Carl ; Agha, Gul (junio de 1991). "Lenguajes con cláusulas de Horn protegidas: ¿son deductivos y lógicos?". En Winston, Patrick Henry ; Shellard, Sarah Alexandra (eds.). Inteligencia artificial en el MIT: expandiendo fronteras . MIT Press. págs. 582–593. ISBN. 9780262231503.
  9. ^ Hewitt, Carl (mayo de 2006). "¿Qué es el compromiso? Físico, organizacional y social". Coordinación, organizaciones, instituciones y normas en sistemas de agentes II . Taller internacional AAMAS 2006, COIN. Hakodate, Japón: Springer Berlin Heidelberg. págs. 293–307. doi :10.1007/978-3-540-74459-7_19.
  10. ^ Hewitt, Carl (marzo de 2006). "La repetida desaparición de la programación lógica y por qué se reencarnará". Qué salió mal y por qué: lecciones de la investigación y las aplicaciones de la IA . Simposio de primavera de la AAAI de 2006 (informe técnico). Stanford, California: AAAI. págs. 2–9. SS-06-08 . Consultado el 10 de marzo de 2022 .