Il existe plusieurs notions différentes (probablement inéquivalentes) d'universalité informatique (voir par exemple les deux dernières pages de http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) et il n'y a pas de consensus entre des experts sur les notions les plus correctes (voir par exemple http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
J'essaie de dire quelque chose sur un modèle particulier de calcul biomoléculaire. Je dirais que c'est "plus universel" ou "plus utilement universel" que certains autres modèles, car vous pouvez construire une machine universelle qui exécute un programme, puis supprime l'entrée à la fin et est prête à exécuter un autre programme. Comparez cela à, disons, les automates cellulaires, qui peuvent émuler n'importe quelle machine de Turing, mais à la fin du calcul, vous avez une configuration finale, immuable. Pour émuler une autre MT, vous devez définir une autorité de certification complètement distincte. Je voudrais donc dire que quelque chose est "universellement réutilisable" s'il se comporte comme votre bureau, pas comme une autorité de certification (c'est-à-dire qu'il peut exécuter plusieurs programmes sans avoir à recréer l'univers). Cette notion a-t-elle été formalisée quelque part?
la source
Réponses:
Comme vous le mentionnez dans la rubrique Théorie des automates / Thème du langage formel, mes superviseurs ont au moins une partie des mêmes propos sur «l'universalité réutilisable» que «mieux» que le style CA. Je ne suis pas sûr qu'un nom soit donné cependant: http://www.diku.dk/~neil/blobentcs.pdf
Je ne me suis pas beaucoup concentré sur cette partie, mais comme je le vois, en parcourant la littérature sur le bio-informatique, la principale différence réside dans le sens du mot "programmation / programmable", par exemple qu'est-ce qui est en fait programmable? Cela, ainsi que la partie "programme enregistré", mais j'apprécie la nuance posée par votre question
Je n'ai pas de réponse facilement disponible à ce qu'on appelle
la source
Il y a eu des travaux dans la communauté PL / systèmes sur la sémantique et la modélisation des systèmes d'exploitation. Comme vous le faites remarquer, ce dont vous parlez ressemble beaucoup à un système d'exploitation: il fait quelque chose, mais il est garanti (enfin, dans le cas d'un système d'exploitation, garanti-ish) de revenir à un «état fondamental». Les personnes PL n'ont peut-être pas officialisé votre notion d'universel réutilisable, mais vous pourriez y trouver de l'inspiration.
Votre formalisation devra saisir la différence entre "une machine universelle qui, après avoir fonctionné avec une entrée, si vous remplacez l'entrée par une autre entrée, elle est prête à fonctionner" et "une machine universelle qui, étant donné une séquence de programmes d'entrée, les dirige successivement. " Et bien sûr, toutes les notions raisonnables de machine universelle satisfont probablement à cette dernière exigence. Cela semble donc assez délicat ...
la source