stringtranslate.com

No determinismo ilimitado

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 atender una solicitud puede volverse ilimitada como resultado del arbitraje de la contienda por recursos compartidos y al mismo tiempo garantizar que la solicitud eventualmente será atendida . El no determinismo ilimitado se convirtió en una cuestión importante en el desarrollo de la semántica denotacional de la concurrencia y más tarde pasó a formar parte de la investigación sobre el concepto teórico de hipercomputación [1] .

Justicia

La discusión sobre el no determinismo ilimitado tiende a involucrarse con discusiones sobre la justicia . El concepto básico es que todos los caminos de cálculo deben ser "justos" en el sentido de que si la máquina entra en un estado con una frecuencia infinita, 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 conduzca 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 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 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. 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 ( S, T) , asumiendo que es una función monótona. Luego argumentó que fusionar (⊥,1 ω )⊆ fusionar (0,1 ω ) , donde ⊥ es la secuencia vacía. Ahora fusionar (⊥,1 ω ) = {1 ω }, entonces debe ser que 1 ω es un elemento de fusionar (0,1 ω ) , una contradicción. Concluyó que:

Parece que una fusión justa no puede escribirse como un programa de flujo de datos no determinista que opere en flujos. [2]

Sobre la posibilidad de implementar un no determinismo ilimitado

Edsger Dijkstra argumentó que es imposible implementar sistemas con no determinismo ilimitado [3] . Por este motivo, 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 sólo tienen un no determinismo limitado. Del mismo modo, los programas secuenciales que contienen órdenes cautelosas como únicas fuentes de no determinismo sólo tienen un no determinismo limitado. [3] Brevemente, el no determinismo de elección es acotado. Gordon Plotkin dio una prueba en su artículo original sobre dominios de poder:

Ahora 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 bifurcación corresponderán a los puntos elegidos 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 siempre es 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, también lo es el árbol mismo. En el presente caso, esto significa que si cada secuencia de ejecución de P termina, entonces sólo 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 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 ser alcanzado mediante algún cálculo c , entonces existe un cálculo c que visita cada nodo x en la rama. ... Claramente, esta premisa no se deriva de la lógica sino más bien de la interpretación dada a los puntos de elección. Esta premisa falla por 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. Por tanto, la existencia de una rama infinita no implica necesariamente un cálculo no final. [2]

No determinismo ilimitado y no computabilidad

Spaan et al. 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: [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 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 en 0; luego, el programa elige repetidamente si incrementa la variable o atiende la solicitud. La restricción de equidad requiere que la solicitud finalmente sea atendida, porque de lo contrario hay un bucle infinito en el que sólo 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 abordar el no determinismo ilimitado

Clinger y Carl Hewitt [ cita necesaria ] han desarrollado un modelo (conocido como modelo Actor ) de computación concurrente con la propiedad de no determinismo ilimitado construida en [Clinger 1981; [7] ; [8] ; [9] ]; esto permite cálculos que las máquinas de Turing no pueden implementar, como se vio arriba. 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 necesaria ] definida por Church, Kleene, Turing, etc. (Ver Indeterminación en cálculos concurrentes ).

Hewitt justificó su uso del no determinismo ilimitado argumentando que no se puede imponer ningún límite al tiempo que tarda un circuito computacional llamado árbitro en establecerse (ver metaestabilidad en electrónica ). Los árbitros se utilizan en las computadoras para abordar la circunstancia de que los relojes de las computadoras funcionan de forma asincrónica con entradas externas, por ejemplo. , entrada de teclado, acceso al disco, entrada de red, etc. Por lo tanto, un mensaje enviado a una computadora podría tardar un tiempo ilimitado en recibirse 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 sobre el no determinismo ilimitado . [10]

El análisis de la justicia de Hewitt

Hewitt argumentó que las cuestiones de justicia se derivan en parte del punto de vista del Estado global. Los modelos de computación más antiguos (p. ej. , 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 es desde 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 máquinas de estados finitos y máquinas de pila de empuje, 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 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 un período de tiempo ilimitado. Mientras se lleva a cabo un arbitraje local, una actividad ilimitada puede tener lugar en otros lugares. No existe un Estado global y, en consecuencia, no hay que hacer ninguna "elección" en cuanto al "próximo" Estado global.

Referencias

  1. ^ Ord, Toby (2002). "Hipercomputación: informática más que la máquina de Turing". arXiv : matemáticas/0209332 .
  2. ^ ab Clinger, William D. (1 de mayo de 1981). Fundamentos de la semántica de actores (Informe técnico de IA). Instituto de Tecnología de Massachusetts. hdl :1721.1/6935.
  3. ^ ab Dijkstra, Edsger (1976). Una disciplina de programación . Serie Prentice-Hall en 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 en el dominio del poder". Revista SIAM de Computación . 5 (3): 452–487. doi :10.1137/0205035.
  6. ^ Español, Edith; Torenvliet, Leen; van Emde Boas, Peter (febrero de 1989). "No determinismo, equidad 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 Perdiz, Derek; Wilks, Yorick (eds.). Los fundamentos de la inteligencia artificial: un libro de consulta . Prensa de la Universidad de Cambridge. págs. 383–395. ISBN 9780521359443.
  8. ^ Hewitt, Carl ; Agha, Gul (1988). "Lenguajes de cláusulas de Cuerno Guardado: ¿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. págs. 650–657. ISBN 3540195580.También como Hewitt, Carl ; Agha, Gul (junio de 1991). "Lenguajes de cláusulas de Cuerno Guardado: ¿son deductivos y lógicos?". En Winston, Patrick Henry ; Shellard, Sarah Alexandra (eds.). Inteligencia artificial en el MIT: fronteras en expansión . Prensa del MIT. 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 . AAMAS 2006 Taller Internacional, 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 2006 (Informe técnico). Stanford, California: AAAI. págs. 2–9. SS-06-08 . Consultado el 10 de marzo de 2022 .