Существует несколько различных (возможно, неэквивалентных) понятий универсальности вычислений (см., Например, последние пару страниц http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ), и нет единого мнения среди эксперты о том, какие понятия являются наиболее правильными (см., например, http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Я пытаюсь что-то сказать о конкретной модели биомолекулярных вычислений. Я хотел бы доказать, что он «более универсален» или «полезнее универсален», чем некоторые другие модели, потому что вы можете создать универсальный компьютер, который запускает программу, а затем удаляет входные данные в конце и готов запустить другую программу. Сравните это, скажем, с клеточными автоматами, которые могут эмулировать любую машину Тьюринга, но затем в конце вычислений вы получите окончательную неизменяемую конфигурацию. Чтобы эмулировать другую ТМ, вам нужно определить совершенно отдельный ЦС. Поэтому я хотел бы сказать, что что-то «универсально многократно», если оно ведет себя как ваш рабочий стол, а не как ЦС (то есть может выполнять несколько программ без необходимости воссоздания юниверса). Это понятие было формализовано где-нибудь?
источник
Ответы:
Как вы упомянули в теме «Теория автоматов / тема формального языка», у моих руководителей есть, по крайней мере, некоторая та же интуиция относительно «универсальности многократного использования», что и «лучше», чем в стиле CA. Я не уверен, что имя дано, хотя: http://www.diku.dk/~neil/blobentcs.pdf
Я не уделял много внимания этой части, но, как я понимаю, при изучении литературы по биокомпьютеру основное различие заключается в значении слова «программирование / программирование», например, что на самом деле программируется? Это, и часть "сохраненной программы", но я ценю нюанс, поставленный вашим вопросом
У меня нет легкодоступного ответа на то, как это называется, хотя
источник
В сообществе PL / systems была проведена работа по семантике и моделированию операционных систем. Как вы указали, то, о чем вы говорите, во многом похоже на ОС: она что-то делает, но гарантированно (ну, в случае ОС, гарантированный выход) возвращается в «основное состояние». Люди из ЛП, возможно, и не оформили ваше представление об универсальности, но вы можете найти там вдохновение.
Ваша формализация должна будет отразить разницу между «универсальной машиной, которая после запуска с одним входом, если вы замените ввод другой вводом, которую он готов к работе», и «универсальной машиной, которая, учитывая последовательность программ ввода, запускает их подряд ". И, конечно, все разумные представления об универсальной машине, вероятно, удовлетворяют последнему требованию. Так что это выглядит довольно сложно ...
источник