Les machines de Turing ont un alphabet de symboles formel, une description basée sur les règles d'état et de transition de la façon dont un calcul est effectué.
Le modèle d'acteur est parfois mentionné comme un modèle de calcul plus puissant que les machines de Turing (pas dans ce qu'il peut calculer, mais dans d'autres aspects).
- L'Actor Model est-il une alternative à part entière aux tours en tant que modèle informatique?
- Le modèle d'acteur a-t-il également une description de calcul formelle basée sur des symboles semblable à la machine de Turing?
- Les acteurs sont-ils supposés être équivalents à la machine de Turing - puisque chaque message est traité séquentiellement (et atomiquement)?
Il existe de nombreux résultats théoriques basés sur les machines de Turing, par exemple le problème d'arrêt, la décidabilité, la relation avec le théorème d'incomplétude de Gödel, etc.
Ces preuves peuvent-elles être formellement généralisées au modèle d'acteur? Cela a-t-il été fait?
terminology
computability
reference-request
programming-languages
computation-models
Adi Shavit
la source
la source
Réponses:
les informaticiens sont généralement d'accord sur le fait que la thèse de Church Turing [1] est correcte et définitive, c'est-à-dire que les machines de Turing décrivent le calcul, et que des formes plus puissantes n'existent pas vraiment, et assument que certains modèles sont "plus puissants" que Turing machines avec un scepticisme extrême, même près de l'hostilité. [2] les néophytes du domaine qui ne comprennent pas complètement le concept sont la proie de slogans de marketing proche d'une théorie comme "plus puissante" que les machines de Turing, mais ces affirmations sont rarement faites par des informaticiens de renom / réputés.
mais en contrepartie, de nombreux modèles de calcul sont Turing complets. par conséquent, dans CS, il existe en pratique une attitude tolérante, "vivre et laisser vivre" avec de nombreux modèles de calcul différents proliférant selon ce qui est le plus pertinent et le plus pratique pour le problème étudié. la plupart des modèles de programmation de base sont Turing avec des structures de base telles que la mémoire, les conditions et les boucles, les sous-programmes, etc. des affirmations plus raisonnables sont donc "le modèle [x] est mieux adapté pour étudier [y] parce que [z]". le modèle Actor se concentre sur la transmission de messages, la communication, la simultanéité et une certaine sécurité.
néanmoins, il y a un débat principalement philosophique dans CS sur le fait que certains modèles sont "plus puissants".
[1] Thèse de Church Turing
[2] Modèles interactifs de calcul vs thèse de Church Turing
la source