Turingmaschinen haben eine formale Symbolalphabet-, Zustands- und Übergangsregel-basierte Beschreibung, wie eine Berechnung durchgeführt wird.
Das Akteurmodell wird manchmal als leistungsfähigeres Rechenmodell als Turing-Maschinen erwähnt (nicht in dem, was es berechnen kann, sondern in anderen Aspekten).
- Ist das Actor Model eine vollwertige Drehmaschinenalternative als Rechenmodell?
- Verfügt das Akteurmodell auch über eine solche symbolbasierte formale Berechnungsbeschreibung, die der Turing-Maschine ähnelt?
- Werden die Akteure als Turing-Maschinenäquivalent angenommen - da jede Nachricht nacheinander (und atomar) verarbeitet wird?
Es gibt viele theoretische Ergebnisse, die auf Turing-Maschinen basieren, z. B. das Halteproblem, die Entscheidbarkeit, die Beziehung zum Unvollständigkeitssatz von Gödel usw.
Können diese Beweise formal auf das Akteurmodell verallgemeinert werden? Wurde das getan?
terminology
computability
reference-request
programming-languages
computation-models
Adi Shavit
quelle
quelle
Antworten:
Informatiker sind sich im Allgemeinen einig, dass die These von Church Turing [1] korrekt und endgültig ist, dh dass Turing-Maschinen Berechnungen beschreiben und dass leistungsfähigere Formen nicht wirklich existieren, und behaupten, dass ein Modell "leistungsfähiger" ist als Turing Maschinen mit extremer Skepsis, sogar in der Nähe von Feindseligkeit. [2] Neulinge auf dem Gebiet, die das Konzept nicht vollständig verstehen, sind Opfer von Marketing-Slogans einiger Theorien, die als "leistungsfähiger" als Turing-Maschinen gelten, aber diese Behauptungen werden selten von etablierten / seriösen Informatikern aufgestellt.
Aber als Kehrseite dazu sind viele Rechenmodelle vollständig. Daher gibt es in der Praxis in der Praxis meist eine tolerante "Leben und Leben lassen" -Haltung mit vielen verschiedenen Berechnungsmodellen, die sich vermehren, je nachdem, was für das untersuchte Problem am relevantesten und bequemsten ist. Die meisten grundlegenden Programmiermodelle sind Turing mit grundlegenden Strukturen wie Speicher, Bedingungen und Schleifen, Unterprogrammen usw. Vernünftigere Behauptungen lauten daher: "Modell [x] ist besser geeignet, um [y] zu studieren, weil [z]". Das Actor-Modell konzentriert sich auf Nachrichtenübermittlung, Kommunikation, Parallelität und Sicherheit.
Dennoch gibt es in CS eine meist philosophische Debatte darüber, dass einige Modelle "mächtiger" sind.
[1] These von Church Turing
[2] Interaktive Computermodelle vs. Church Turing-These
quelle