Es gibt verschiedene (wahrscheinlich nicht äquivalente) Begriffe der rechnerischen Universalität (siehe zum Beispiel die letzten Seiten von http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ), und es besteht kein Konsens zwischen diesen Experten, welche Begriffe am zutreffendsten sind (siehe zum Beispiel http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Ich versuche etwas über ein bestimmtes Modell der biomolekularen Berechnung zu sagen. Ich möchte argumentieren, dass es "universeller" oder "nützlicher universell" ist als einige andere Modelle, da Sie eine universelle Maschine erstellen können, die ein Programm ausführt und dann die Eingabe am Ende löscht und bereit ist, ein anderes Programm auszuführen. Vergleichen Sie dies beispielsweise mit zellularen Automaten, die jede Turing-Maschine emulieren können. Am Ende der Berechnung erhalten Sie jedoch eine endgültige, unveränderliche Konfiguration. Um ein anderes TM zu emulieren, müssen Sie eine vollständig separate Zertifizierungsstelle definieren. Daher möchte ich sagen, dass etwas "wiederverwendbar universell" ist, wenn es sich wie Ihr Desktop verhält, nicht wie eine Zertifizierungsstelle (dh mehrere Programme ausführen kann, ohne das Universum neu erstellen zu müssen). Wurde dieser Begriff irgendwo formalisiert?
quelle
Antworten:
Wie Sie im Thema Automatentheorie / Formale Spracharbeit erwähnen, haben meine Vorgesetzten mindestens die gleiche Vorstellung von "wiederverwendbarer Universalität" wie "besser" als CA-Stil. Ich bin mir nicht sicher, ob ein Name angegeben ist: http://www.diku.dk/~neil/blobentcs.pdf
Ich habe mich nicht sehr auf diesen Teil konzentriert, aber wie ich sehe, liegt der Hauptunterschied beim Durchgehen der Biocomputing-Literatur in der Bedeutung des Wortes "Programmieren / Programmierbar", z. B. was ist tatsächlich programmierbar? Das und der Teil "Gespeichertes Programm" auch, aber ich schätze die Nuance, die Ihre Frage aufwirft
Ich habe jedoch keine sofort verfügbare Antwort auf das, was es heißt
quelle
In der PL / Systems-Community wurde an der Semantik und Modellierung von Betriebssystemen gearbeitet. Wie Sie hervorheben, ähnelt das, worüber Sie sprechen, einem Betriebssystem: Es tut etwas, aber es ist garantiert (im Fall eines Betriebssystems garantiert), in einen "Grundzustand" zurückzukehren. Die PL-Leute haben Ihre Vorstellung von wiederverwendbar universell vielleicht nicht formalisiert, aber Sie könnten dort Inspiration finden.
Ihre Formalisierung muss den Unterschied zwischen "einer Universalmaschine, die, nachdem sie mit einer Eingabe ausgeführt wurde, wenn Sie die Eingabe durch eine andere Eingabe ersetzen, ist sie einsatzbereit" und "einer Universalmaschine, die bei einer bestimmten Folge von Eingabeprogrammen bereit ist" erfassen. führt sie nacheinander aus. " Und natürlich erfüllen wahrscheinlich alle vernünftigen Vorstellungen von Universalmaschinen die letztere Anforderung. Es scheint also ziemlich schwierig zu sein ...
quelle