¿Máquina de Turing distribuida?

Soy un estudiante de maestría enfocado en sistemas distribuidos pero también interesado en informática teórica. Me preguntaba si hay una representación formal de un sistema distribuido encima de una máquina de turing. Es decir, ¿es posible extender (hacer una variante) el concepto de una máquina de turing para aprovechar la informática distribuida?

Una idea es hacer una cinta compartida (algo similar a Tuple Space ) entre TM.

[¿Hay] una representación formal de un sistema distribuido encima de una máquina de turing?

Con respecto a esto, la discusión (ver el enlace publicado por Jukka en los comentarios) es la forma de mirar. En mi opinión, la forma en que representaría formalmente un sistema distribuido depende en gran medida de cómo los vea, y eso depende de "sus supuestos favoritos del sistema" (es decir, los supuestos sobre la sincronía (es decir, el tiempo relativo de las acciones en el sistema distribuido). sistema), sobre comunicación (transmisión de mensajes vs. memoria compartida), sobre fallas (de procesos y / o enlaces, benignos o bizantinos, etc.) Como la comunidad no está de acuerdo con este punto, tampoco hay acuerdo sobre el formalismo básico .

[¿Es posible ampliar (hacer una variante) el concepto de una máquina de turing para aprovechar la informática distribuida?

Supongo que es completamente posible, pero nadie (que yo sepa) lo ha investigado. Lo que sé son estos:

1. Autómatas IO cronometrados también utilizados en el libro de Computación Distribuida de Lynch
2. Comunicando procesos secuenciales
3. Lógica temporal de acciones.
4. Pi-Calculus (también ya mencionado por Alex)
5. Y más (han sido y serán mencionados aquí) ...

Es posible que desee mirar en Pi-Calculus.

http://en.wikipedia.org/wiki/%CE%A0-calculus

Es un cálculo basado en procesos diseñado para razonar sobre sistemas distribuidos.

¡Me sorprende que las Redes de Petri aún no hayan sido mencionadas! Las extensiones de las redes de Petri como las redes de Petri coloreadas o las redes de Petri con arcos inhibidores están completas en Turing.

( Advertencia: vistas algo sesgadas, simplificaciones excesivas y generalizaciones descaradas por delante ) .

A menudo, la diferencia entre la computación distribuida y la computación paralela se puede resumir de la siguiente manera:

• En la informática distribuida , las medidas de complejidad primarias están relacionadas con los flujos de comunicación e información : cuántas rondas de comunicación ("tiempo"); cuantos bits transmiten
• En computación paralela , las medidas de complejidad primarias están relacionadas con la computación y el procesamiento de la información : cuántos pasos elementales ("tiempo"); cuántos bits almacenados

Si toma esta perspectiva, a menudo resulta que para modelar sistemas distribuidos, realmente no importa qué tipo de poder computacional tengan sus nodos (o procesadores o computadoras).

$O(n)$

$X$$X$

$T$$T$

Por lo tanto, usar máquinas de Turing como punto de partida para modelar sistemas distribuidos me parece un poco antinatural: si este es un aspecto irrelevante, ¿por qué construir todo sobre él? Por otro lado, en computación paralela esto sería natural (excepto que el modelo generalmente es algo así como PRAM en lugar de máquinas Turing).

Algunos sostienen que, según su punto de vista, podría pensar en los sistemas distribuidos como algo más poderoso que una máquina de Turing, debido a las diferentes interpretaciones de la limitación del no determinismo y la equidad. Este enlace tiene una discusión interesante sobre el tema. Herlihy / Shavit en su libro "El arte de la programación multiprocesador" argumentan que la computabilidad de Turing se refiere inherentemente a la noción de un algoritmo (secuencial) y, en cierto sentido, no es apropiado para razonar sobre la computación distribuida. Debo mencionar que esto es discutible y controvertido, así que espero que nadie me arroje piedras porque estoy diciendo esto.