Istnieje kilka różnych (prawdopodobnie nierównych) pojęć uniwersalności obliczeniowej (patrz na przykład kilka ostatnich stron http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) i nie ma zgody między eksperci o tym, które pojęcia są najbardziej poprawne (patrz na przykład http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Próbuję powiedzieć coś o konkretnym modelu obliczeń biomolekularnych. Chciałbym argumentować, że jest „bardziej uniwersalny” lub „bardziej użyteczny uniwersalny” niż niektóre inne modele, ponieważ można zbudować uniwersalną maszynę, która uruchamia program, a następnie usuwa dane wejściowe na końcu i jest gotowa do uruchomienia innego programu. Porównaj to, powiedzmy, z automatami komórkowymi, które mogą emulować dowolną maszynę Turinga, ale pod koniec obliczeń masz ostateczną, niezmienną konfigurację. Aby emulować inną bazę TM, musisz zdefiniować całkowicie oddzielny urząd certyfikacji. Chciałbym więc powiedzieć, że coś jest „uniwersalnie wielokrotnego użytku”, jeśli zachowuje się jak pulpit, a nie urząd certyfikacji (tzn. Może uruchamiać wiele programów bez konieczności ponownego tworzenia wszechświata). Czy to pojęcie jest gdzieś sformalizowane?
źródło
Odpowiedzi:
Jak wspomniałeś w Automacie Theory / Formal Language Thesis Temat, moi przełożeni mają przynajmniej takie same zdanie na temat „uniwersalności wielokrotnego użytku”, co „lepsze” niż w stylu CA. Nie jestem jednak pewien, czy podano nazwę: http://www.diku.dk/~neil/blobentcs.pdf
Nie skupiłem się zbytnio na tej części, ale widzę to, kiedy przeglądam literaturę biokomputerową, główna różnica polega na znaczeniu słowa „programowanie / programowalne”, np. Co to właściwie jest programowalne? To i część „programu przechowywanego”, ale doceniam niuans związany z twoim pytaniem
Nie mam jednak łatwo dostępnej odpowiedzi na to, co się nazywa
źródło
W społeczności PL / systems były prace nad semantyką i modelowaniem systemów operacyjnych. Jak zauważyłeś, to, o czym mówisz, przypomina system operacyjny: robi coś, ale ma gwarancję (cóż, w przypadku systemu operacyjnego, gwarantowanej), aby powrócić do „stanu podstawowego”. Ludzie z PL mogli nie sformalizować twojego pojęcia uniwersalnego użytku, ale możesz znaleźć tam inspirację.
Twoja formalizacja będzie musiała uchwycić różnicę między „maszyną uniwersalną, która po uruchomieniu z jednym wejściem, jeśli zastąpisz ją inną, jest gotowa do pracy”, a „maszyną uniwersalną, która, biorąc pod uwagę sekwencję programów wejściowych, uruchamia je kolejno ”. I oczywiście wszystkie rozsądne pojęcia uniwersalnej maszyny prawdopodobnie spełniają ten ostatni wymóg. Wydaje się to dość trudne ...
źródło