Formalismo tipo máquina de Turing para o modelo de ator

8

As máquinas de Turing têm uma descrição formal do alfabeto de símbolos, estado e regras de transição de como é feita uma computação.

Às vezes, o modelo do ator é mencionado como um modelo computacional mais poderoso do que as máquinas de Turing (não no que ele pode calcular, mas em outros aspectos).

  1. O Modelo do Ator é uma alternativa de torneamento completa como modelo computacional?
  2. O Modelo do Ator também possui uma descrição formal de computação baseada em símbolos, semelhante à máquina de Turing?
  3. Os atores são considerados equivalentes à máquina de Turing - já que cada mensagem é processada sequencialmente (e atomicamente)?

Existem muitos resultados teóricos baseados em máquinas de Turing, por exemplo, o problema da parada, a decidibilidade, a relação com o teorema da incompletude de Gödel etc.

Essas provas podem ser formalmente generalizadas para o modelo de ator? Isso foi feito?

terminology computability reference-request programming-languages computation-models Adi Shavit
fonte
1
Eu acho que os atores (como em Erlang) geralmente são considerados completos como Turing. Há, no entanto, uma vasta pesquisa sobre todos os tipos de autômatos cooperantes. Também existem cálculos de processo . Eu acho que a pergunta é mais ampla do que você esperava. Talvez você deva focar a questão, fornecendo um exemplo específico de um sistema para o qual deseja ter modelos formais, para que as pessoas possam ver o que você procura.
Raphael
@Raphael: Você tem uma referência de que os atores do Modelo de Ator são considerados Turing completos? Estou interessado nos fundamentos da computação com esses modelos.
Adi Shavit
Realmente depende de onde você tira o termo "modelo de ator". Conheço Erlang e bibliotecas para outras linguagens que imitam Erlang, e essas não têm restrições ao poder de um único ator (portanto, no mundo das teorias, Turing é completo). A propósito, o artigo da Wikipedia que você vincula fornece inúmeras referências ; você já conferiu isso? Veja também este .
Raphael
1
Pesquisando por aí, encontrei um artigo recente com bons resultados sobre Turing completude e decidibilidade do ator Sistemas: Decidibilidade Problemas para o ator Sistemas
Vor
1
O cálculo pi vem à mente, que é um processo proci como estado de @Raphael acima. É um modelo de computação (Turing-complete, pois pode codificar o cálculo lambda). Todos os modelos de computação são equivalentes enfrentam os mesmos problemas (como em: nenhum deles pode resolver o problema de parada, etc.).
Paulotorrens # 15/17

Respostas:

-2

os cientistas da computação geralmente têm o consenso de que a tese de Church Turing [1] é correta e definitiva, ou seja, que as máquinas de Turing descrevem a computação e que formas mais poderosas não existem realmente, e afirmam que algum modelo é "mais poderoso" do que Turing máquinas com extremo ceticismo, mesmo perto da hostilidade. [2] os neófitos do campo que não entendem completamente o conceito são vítimas de slogans de marketing de alguma teoria como "mais poderosos" do que as máquinas de Turing, mas essas afirmações raramente são feitas por cientistas da computação tradicionais / respeitáveis.

mas, por outro lado, muitos modelos de computação são completos de Turing. portanto, na SC há na prática principalmente uma atitude tolerante, "viva e deixe viver", com muitos modelos diferentes de computação proliferando, dependendo do que é mais relevante e conveniente para o problema estudado. os modelos de programação mais básicos são Turing completos com estruturas básicas como memória, condicionais e loops, sub-rotinas etc. portanto, reivindicações mais razoáveis ​​são "o modelo [x] é mais adequado para estudar [y] porque [z]". o modelo de ator se concentra na passagem de mensagens, comunicação, concorrência e alguma segurança.

no entanto, existe um debate principalmente filosófico no CS sobre alguns modelos serem "mais poderosos".

[1] Tese de Church Turing

[2] Modelos interativos de computação versus tese de Church Turing

vzn
fonte
1
Como eu disse, os atores NÃO são mais poderosos no que podem calcular. Eles são (alegadamente) mais poderosos, apresentando "não determinismo ilimitado", que está relacionado à operação simultânea. O que você está se referindo é hipercomputação , que não é o assunto da minha pergunta.
Adi Shavit
?! Hã! vadio! não viu nada sobre o não determinismo ilimitado na sua pergunta real acima. também não fez referência direta à hipercomputação na minha resposta. que é de fato uma área de estudo de não-Turing completude, mas o árbitro Dei é outra envolvendo "modelos interativos"
vzn