Existem várias noções diferentes (provavelmente inequívocas) de universalidade computacional (veja, por exemplo, as últimas páginas de http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) e não há consenso entre especialistas sobre quais noções são mais corretas (veja, por exemplo, http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Estou tentando dizer algo sobre um modelo específico de computação biomolecular. Eu gostaria de argumentar que é "mais universal" ou "mais universalmente útil" do que alguns outros modelos, porque você pode construir uma máquina universal que executa um programa e exclui a entrada no final e está pronta para executar outro programa. Compare isso com, digamos, autômatos celulares, que podem emular qualquer máquina de Turing, mas, no final do cálculo, você tem uma configuração final e imutável. Para emular outra TM, você precisa definir uma CA completamente separada. Então, eu gostaria de dizer que algo é "reutilizável universal" se comportar como sua área de trabalho, não uma CA (ou seja, pode executar vários programas sem a necessidade de recriar o universo). Essa noção foi formalizada em algum lugar?
fonte
Respostas:
Como você mencionou no tópico da teoria da automação / tese da linguagem formal, meus supervisores têm pelo menos algumas das mesmas intenções sobre "universalidade reutilizável" como "melhores" que o estilo CA. No entanto, não tenho certeza de que seja dado um nome: http://www.diku.dk/~neil/blobentcs.pdf
Ainda não me concentrei muito nessa parte, mas, ao ver a literatura de biocomputação, a principal diferença está no significado da palavra "programação / programável", por exemplo, o que é de fato programável? Isso e a parte "programa armazenado" também, mas eu aprecio as nuances colocadas por sua pergunta
Eu não tenho resposta prontamente disponível para o que é chamado embora
fonte
Houve um trabalho na comunidade de sistemas / PL na semântica e modelagem de sistemas operacionais. Como você ressalta, o que você está falando é muito parecido com um sistema operacional: ele faz alguma coisa, mas é garantido (bem, no caso de um sistema operacional, com garantia) retornar ao "estado fundamental". O pessoal do PL pode não ter formalizado sua noção de reutilizável universal, mas você pode encontrar alguma inspiração lá.
Sua formalização terá que capturar a diferença entre "uma máquina universal que, depois de executada com uma entrada, se você substituir a entrada por outra entrada, ela estará pronta para funcionar" e "uma máquina universal que, dada uma sequência de programas de entrada, os executa em sucessão ". E, é claro, todas as noções razoáveis de máquina universal provavelmente atendem ao último requisito. Então parece bastante complicado ...
fonte