Sou um estudante de mestrado focado em sistemas distribuídos, mas também interessado em ciência da computação teórica. Eu queria saber se existe uma representação formal de um sistema distribuído em cima de uma máquina de turing? Ou seja, é possível estender (criar uma variante) o conceito de uma máquina de turing para aproveitar a computação distribuída?
Uma idéia é fazer uma fita compartilhada (algo semelhante ao Tuple Space ) entre a TM.
turing-machines
dc.distributed-comp
Marcos Roriz Junior
fonte
fonte
Respostas:
Com relação a isso, a discussão (veja o link postado por Jukka nos comentários) é o caminho a seguir. A maneira como vejo formalmente como você representaria um sistema distribuído depende muito de como você os vê, e isso depende de "suas premissas favoritas do sistema" (ou seja, as premissas da sincronia) (ou seja, o tempo relativo das ações no sistema distribuído sistema), na comunicação (passagem de mensagem versus memória compartilhada), falhas (de processos e / ou links, benignos ou bizantinos, etc.) Como a comunidade não concorda com esse ponto, também não há acordo sobre o formalismo básico .
Eu acho que é inteiramente possível, mas ninguém (que eu conheça) investigou. O que eu sei são:
fonte
Você pode querer examinar o Pi-Calculus.
http://en.wikipedia.org/wiki/%CE%A0-calculus
É um cálculo baseado em processamento, projetado para raciocinar sobre sistemas distribuídos.
fonte
Estou surpreso que as redes de Petri ainda não tenham sido mencionadas! Extensões de redes de Petri como redes coloridas de Petri ou redes de Petri com arcos inibidores são completas em Turing.
fonte
( Aviso: visões um tanto tendenciosas, simplificações excessivas e generalizações flagrantes à frente. )
Frequentemente, a diferença entre computação distribuída e computação paralela pode ser resumida da seguinte forma:
Se você adota essa perspectiva, geralmente acontece que, para modelar sistemas distribuídos, não importa realmente que tipo de poder computacional seus nós (ou processadores ou computadores) possuem.
Portanto, o uso de máquinas de Turing como ponto de partida para modelar sistemas distribuídos me parece um pouco natural: se esse é um aspecto irrelevante, por que construir tudo sobre ele? Por outro lado, na computação paralela isso seria natural (exceto que o modelo geralmente é algo como PRAM em vez de máquinas de Turing).
fonte
Alguns argumentam que, dependendo da sua visão, você poderia pensar em sistemas distribuídos como algo mais poderoso que uma Máquina de Turing, devido a diferentes interpretações de limites do não-determinismo e da justiça. Este link tem uma discussão interessante sobre o tópico. Herlihy / Shavit, em seu livro "A arte da programação de multiprocessadores", argumenta que a computabilidade de Turing se refere inerentemente à noção de um algoritmo (seqüencial) e, em certo sentido, não é apropriada para raciocinar sobre a computação distribuída. Devo mencionar que isso é discutível e controverso, por isso espero que ninguém me atire porque estou dizendo isso.
fonte