Czy istnieje oficjalna nazwa pojęcia „uniwersalnego użytku”?

10

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?

Aaron Sterling
źródło
1
Możesz zmienić tytuł pytania na nieco mniej osobisty - może po prostu „Uniwersalność wielokrotnego użytku?”
Joshua Grochow

Odpowiedzi:

3

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

Svrist
źródło
1
Z artykułu: „Program jest oprogramowaniem, a nie sprzętem. Dlatego sam program powinien być konkretnym obiektem danych, który można zastąpić w celu określenia różnych działań”. Dzięki jeszcze raz.
Aaron Sterling
Właśnie natknąłem się na pracę Michaela Conrada: portal.acm.org/citation.cfm?id=3533 . Wydaje się, że jest on nieco zdziwiony tym samym rozróżnieniem, które próbujesz wprowadzić w odniesieniu do „programowalności”, jak słowo, którego używa. Popraw mnie, jeśli się mylę :)
svrist
4

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

Joshua Grochow
źródło
Dzięki! Nie mam za dużo teorii języka programowania. Chyba czas się nauczyć.
Aaron Sterling