Hay varias nociones diferentes (probablemente no equivalentes) de universalidad computacional (ver, por ejemplo, las últimas dos páginas de http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) y no hay consenso entre expertos sobre las nociones más correctas (ver, por ejemplo, http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Estoy tratando de decir algo sobre un modelo particular de computación biomolecular. Me gustaría argumentar que es "más universal" o "más útil universalmente" que algunos otros modelos, porque puede construir una máquina universal que ejecute un programa y luego elimine la entrada al final y esté listo para ejecutar otro programa. Compare esto con, digamos, autómatas celulares, que pueden emular cualquier máquina de Turing, pero luego, al final del cálculo, tiene una configuración final e inmutable. Para emular otra TM, debe definir una CA completamente separada. Así que me gustaría decir que algo es "reutilizable universalmente" si se comporta como su escritorio, no como una CA (es decir, puede ejecutar múltiples programas sin necesidad de recrear el universo). ¿Se ha formalizado esta noción en alguna parte?
fuente
Respuestas:
Como usted menciona en la teoría de autómatas / tema de tesis de lenguaje formal, mis supervisores tienen al menos algo de la misma intuición sobre "universalidad reutilizable" como "mejor" que el estilo CA. Sin embargo, no estoy seguro de que se dé un nombre: http://www.diku.dk/~neil/blobentcs.pdf
No me he centrado mucho en esa parte, pero tal como lo veo, cuando reviso la literatura de biocomputación, la principal diferencia radica en el significado de la palabra "programación / programable", por ejemplo, ¿qué es realmente programable? Eso y la parte del "programa almacenado" también, pero agradezco los matices planteados por su pregunta
Sin embargo, no tengo una respuesta disponible para lo que se llama
fuente
Se ha trabajado en la comunidad PL / systems en la semántica y el modelado de sistemas operativos. Como usted señala, de lo que está hablando es muy parecido a un sistema operativo: hace algo, pero está garantizado (bueno, en el caso de un sistema operativo, garantizado) para volver a un "estado fundamental". Es posible que las personas de PL no hayan formalizado su noción de universalmente reutilizable, pero es posible que encuentre algo de inspiración allí.
Su formalización tendrá que capturar la diferencia entre "una máquina universal que, después de que se ejecuta con una entrada, si reemplaza la entrada con otra entrada, está lista para funcionar" y "una máquina universal que, dada una secuencia de programas de entrada, los ejecuta en sucesión ". Y, por supuesto, todas las nociones razonables de máquina universal probablemente satisfacen el último requisito. Entonces parece bastante complicado ...
fuente