Existe um nome oficial para uma noção de "reutilizável universal"?

10

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?

Aaron Sterling
fonte
11
Você pode alterar o título da pergunta para ser um pouco menos pessoal - talvez apenas "Universalidade reutilizável?"
Joshua Grochow

Respostas:

3

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

svrist
fonte
11
Do artigo: "Um programa é software, não hardware. Portanto, um programa deve ser um objeto de dados concreto que pode ser substituído para especificar ações diferentes". Obrigado novamente.
Aaron Sterling
Eu tropecei no trabalho de Michael Conrad: portal.acm.org/citation.cfm?id=3533 . Ele parece estar um pouco preocupado com a mesma distinção que você está tentando fazer em relação à "programação" da palavra que ele está usando. Me corrigir se estou errado :)
svrist
4

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

Joshua Grochow
fonte
Obrigado! Eu não tenho muita teoria da linguagem de programação. Hora de aprender um pouco, eu acho.
Aaron Sterling