Gibt es einen offiziellen Namen für den Begriff „wiederverwendbar universell“?

10

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?

Aaron Sterling
quelle
1
Sie könnten den Fragentitel etwas weniger persönlich ändern - vielleicht nur "Wiederverwendbare Universalität?"
Joshua Grochow

Antworten:

3

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

svrist
quelle
1
Aus ihrem Artikel: "Ein Programm ist Software, keine Hardware. Daher sollte ein Programm selbst ein konkretes Datenobjekt sein, das ersetzt werden kann, um verschiedene Aktionen anzugeben." Danke noch einmal.
Aaron Sterling
Ich bin gerade auf die Arbeit von Michael Conrad gestoßen: portal.acm.org/citation.cfm?id=3533 . Er scheint ein wenig von der gleichen Unterscheidung betroffen zu sein, die Sie in Bezug auf "Programmierbarkeit" machen wollen, wie das Wort, das er verwendet. Korrigieren Sie mich, wenn ich falsch
liege
4

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 ...

Joshua Grochow
quelle
Vielen Dank! Ich habe nicht viel Programmiersprachtheorie. Zeit, etwas zu lernen, denke ich.
Aaron Sterling