Une version bruyante du jeu de la vie de Conway prend-elle en charge le calcul universel?

30

Citant Wikipedia , "[Le jeu de la vie de Conway] a le pouvoir d'une machine de Turing universelle: c'est-à-dire que tout ce qui peut être calculé de manière algorithmique peut être calculé dans le jeu de la vie de Conway."

Ces résultats s'étendent-ils aux versions bruyantes de Game of Life de Conway? La version la plus simple est qu'après chaque tour, chaque cellule vivante meurt avec une petite probabilité et chaque cellule morte devient vivante avec une petite probabilité s (indépendamment).ts

Une autre possibilité consiste à considérer la variante probabiliste suivante de la règle du jeu elle-même.

  • Toute cellule vivante avec moins de deux voisins vivants meurt avec une probabilité de .1t
  • Toute cellule vivante avec deux ou trois voisins vivants vit avec probabilité jusqu'à la génération suivante.1t
  • Toute cellule vivante avec plus de trois voisins vivants meurt avec une probabilité de .1t
  • Toute cellule morte avec exactement trois voisins vivants devient une cellule vivante avec une probabilité de .1t

Question: Ces versions bruyantes du Game of Life prennent-elles toujours en charge les calculs universels? Sinon, que dire de leur "puissance de calcul"?

Des informations connexes sur la puissance de calcul des automates cellulaires et les versions bruyantes des automates cellulaires seront également très appréciées.

(Cette question s'est développée à partir de cette question sur MathOverflow. La réponse de Vincent Beffara sur MO a donné des références intéressantes pour des résultats connexes sur les aspects informatiques des automates cellulaires bruyants.)

Gil Kalai
la source
2
@vzn 1) non, ce n'est pas la "vraie question", c'est une question tout à fait différente; La question de Gil porte sur la robustesse d'un modèle de calcul simple au bruit, et non sur la puissance de l'aléatoire; 2) Les MT avec une bande aléatoire ne sont pas plus puissantes que les MT déterministes, voir cette réponse: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov
2
La vraie question ici est de savoir si les versions stochastiques / bruyantes du "Game of Life" supportent toujours le calcul. (Si ces versions prennent en charge les calculs en P, leur puissance peut aller jusqu'à BPP.) Il est possible que la puissance de calcul de ces versions stochastiques du jeu de la vie soit beaucoup plus faible.
Gil Kalai
3
Je dis peut-être l'évidence, mais vous pouvez simplement dupliquer une configuration suffisamment de fois afin de garantir avec une forte probabilité qu'une version de la configuration n'a même pas une cellule retournée. Ma conviction personnelle est que nous pouvons faire beaucoup, beaucoup mieux, mais au moins c'est une simple borne inférieure.
user834
4
Je ne suis pas sûr que la question soit bien définie. Supposons que . Il me semble que vous pourriez être en mesure de trouver un ordinateur qui traite toutes les erreurs d'un bit dans le "Game of Life", vous donnant un calcul tolérant aux pannes, sauf si vous obtenez spontanément un gros bloc d'erreurs à la fois. Mais je ne pense pas que quelque chose puisse être robuste contre toutes les erreurs. Par exemple, supposons que les erreurs créent spontanément un adversaire malveillant déterminé à perturber le calcul. Vous pourrez peut-être montrer que votre calcul réussit avec une probabilité > 1 - 10 - 9 mais échoue avec une probabilité > 10 - 10000 . Est-ce que cela compte?t=109>1109>1010000
Peter Shor
2
Peter, si votre calcul réussit avec une probabilité 2/3, je suis content.
Gil Kalai

Réponses:

8

Voici quelques "meilleures références à proximité", pour ce que ça vaut. Il semblerait que la voie à suivre sur cette question soit de la réduire à une question sur les "machines de Turing bruyantes", qui ont été étudiées (un peu récemment) et qui sont apparemment le domaine pertinent le plus proche de la littérature. La réponse de base / générale / raisonnable semble être que si le TM peut résister / corriger le bruit (comme cela est démontré dans ces références), il est très probable que le CA peut aussi, dans certaines limites / seuils.

La question de savoir comment réduire un «CA bruyant» en un «MC bruyant» (et vice versa) est plus ouverte. Ce n'est peut-être pas difficile, mais il ne semble pas y avoir de recherche publiée dans le domaine. Un autre problème est que le Noisy TM est un nouveau modèle et qu'il peut donc y avoir plusieurs façons (naturelles?) De représenter un Noisy TM. Par exemple, les articles suivants examinent les perturbations dans la fonction de transition d'état, mais un autre modèle naturel est celui des perturbations dans les symboles de bande (ce dernier étant plus connecté aux CA bruyantes?). Il peut y avoir une relation entre les deux.

  • Machine de Turing tolérante aux pannes par Ilir Capuni, 2012 (thèse de doctorat)

    La machine de Turing est le modèle universel de calcul le plus étudié. Cette thèse étudie la question de savoir s'il existe une machine de Turing qui peut calculer de manière fiable même lorsque les violations de sa fonction de transition se produisent indépendamment les unes des autres avec une faible probabilité.

    Dans cette thèse, nous prouvons l'existence d'une machine de Turing qui avec un overhead polynomial peut simuler n'importe quelle autre machine de Turing, même lorsqu'elle est soumise à des défauts du type ci-dessus, répondant ainsi à la question ouverte depuis 25 ans.

  • Une machine de Turing résistant aux éclats de défauts isolés par Ilir Capuni et Peter Gacs, 2012
  • Noisy Turing Machines par Eugene Asarin et Pieter Collins, 2005
(Une autre question: pourrait-il y avoir un lien entre les MT bruyantes et les machines de Turing probabilistes ?)

vzn
la source
7

Gil demande si le GL oublie tout de sa configuration initiale dans le temps indépendamment de la taille, lorsque chaque cellule "désobéit" à la fonction de transition indépendamment des autres cellules avec une faible probabilité.

À ma connaissance, ce n'est pas connu pour le GL. C'est une question très intéressante cependant. S'il peut résister au bruit, il doit conserver son universalité.

Un aperçu rapide de l'état de l'art est le suivant.

  1. La règle de Toom peut enregistrer un bit pour toujours des défauts qui se produisent indépendamment les uns des autres avec une faible probabilité.
  2. Il était largement admis (la conjecture des taux positifs) que tous les 1 dim CA sont ergodiques jusqu'à ce que P. Gacs construise son CA multi-échelle qui peut simuler n'importe quel autre CA avec des frais généraux modérés même lorsqu'il est soumis au bruit susmentionné.
  3. La question de savoir si la règle G (acs) K (urdiumov) L (evin) peut économiser un bit pour toujours en présence du bruit ci-dessus est toujours ouverte. Kihong Park - un étudiant de Gacs --- a montré que ce n'est pas le cas lorsque le bruit est biaisé.
  4. Lorsque le travail en 2 a été publié, M. Blum a demandé si une MT peut poursuivre son calcul si à chaque étape, la transition ne se fait pas selon la fonction de transition avec une faible probabilité indépendamment des autres étapes, en supposant que les informations stockées sur la bande loin de la tête ne se décompose pas. Une réponse positive a été donnée par I. Capuni (un autre étudiant de Gacs) en 2012.
user8719
la source
"S'il n'est pas ergodique, alors il conservera son universalité" ... avez-vous des preuves de cette affirmation? Est-ce un théorème? Où est-il prouvé? Je crois que le travail de Gacs montre que cela est vrai dans au moins un cas, mais je ne vois pas comment cela prouve que cela vaut pour le jeu de la vie de Conway.
Peter Shor
Merci d'avoir souligné. Ce n'est pas un théorème mais une question ouverte intéressante. Ne pas être ergodique semble trop peu pour demander une déclaration aussi forte.
user8719
3

Pour commencer, gardez à l'esprit que la recherche dans le jeu de la vie de Conway est toujours en cours et que les développements futurs pourraient présenter une solution beaucoup moins compliquée.

Maintenant. Il est intéressant de noter que c'est un sujet qui est en réalité tout aussi conforme à la biologie et à la physique quantique qu'à l'informatique traditionnelle. La question à la racine du problème est de savoir si un appareil peut résister efficacement à des modifications aléatoires de son état. La réponse claire et simple est qu’il est impossible de fabriquer une telle machine parfaitementrésistant à de tels changements aléatoires. Bien sûr, cela est vrai de la même manière que la mécanique quantique pourrait provoquer des événements apparemment impossibles. Ce qui empêche ces événements de se produire (amenant la plupart des gens à les déclarer strictement impossibles), c'est la probabilité incroyablement faible qu'un tel événement a de se produire. Une probabilité rendue si petite par la grande différence d'échelle entre le niveau quantique et le niveau humain. Il est également possible de créer une machine d'état qui résiste à de petits degrés de changement aléatoire en la rendant simplement si grande et redondante que tout "changement" remarqué est effectivement nul, mais l'hypothèse est que ce n'est pas le but. En supposant que cela peut être accompli de la même manière que les animaux et les plantes résistent aux radiations ou aux dommages physiques.

La question peut alors ne pas être de savoir comment empêcher les perturbations de faible niveau de causer trop de dégâts, mais plutôt comment se remettre du plus de dégâts possible. C'est là que la biologie devient pertinente. Les animaux et les plantes ont en fait cette capacité même au niveau cellulaire (veuillez noter: je parle de cellules au sens biologique dans cette réponse). Maintenant, dans le jeu de la vie de Conway, la notion de construction d'un appareil informatique à l'échelle de cellules uniques est attrayant (il rend, après tout, ces créations beaucoup plus petites et plus efficaces), mais bien que nous puissions construire des ordinateurs auto-reproducteurs ( voir Gémeaux ), cela ignore le fait que l'objet constructeur lui-même peut être endommagé par des perturbations.

Une autre façon, plus résiliente, que je peux voir pour résoudre ce problème est de construire des ordinateurs à partir de parties redondantes auto-reproductrices (pensez aux cellules biologiques) qui effectuent leurs opérations, se reproduisent et sont remplacées.

À ce stade, nous pouvons voir un autre parallèle intéressant dans le monde réel. Ces perturbations de bas niveau s'apparentent aux effets des rayonnements. Ceci est plus appréciable lorsque vous considérez le type de dommages qui peuvent être causés à vos automates cellulaires. Il est facile de déclencher l'échec en cascade ou la «mort» d'une cellule dans Game of Life de Conway, à peu près comme ce qui arrive à de nombreuses cellules exposées aux radiations. Mais il existe la pire possibilité de mutation, créant une cellule "cancéreuse" qui continue de reproduire des copies erronées d'elle-même qui ne facilitent pas le processus de calcul ou ne produisent pas de résultats incorrects.

Comme je l'ai dit, il est impossible de construire un système entièrement à toute épreuve, vous ne pouvez que le rendre de moins en moins susceptible qu'un défaut compromet l'ensemble du système. Bien sûr, la question fondamentale ici est vraiment "les simulations probabilistes elles-mêmes sont-elles Turing complètes", ce qui a déjà été décidé comme vrai . J'aurais répondu à cette question fondamentale au départ, sauf que ce n'était pas ce que vous avez demandé.

Hawkwing
la source
Hou la la! Merci pour le vote direct! En tout cas, j'ai révisé mon article, en ajoutant quelques informations et sources. Désolé, je n'ai pas eu le temps de le faire lors de ma première publication. Je pourrais encore modifier cette réponse pour l'adapter aux normes de la communauté, sans le fait qu'aucune raison n'ait été donnée pour le downvote.
Hawkwing
5
En tant que non-votant, je ne vois pas comment cela répond à la question de Gil. Vous posez la question de savoir si "n'importe quel appareil peut résister efficacement à des modifications aléatoires de son état", ce qui n'est pas ce que Gil a demandé.
András Salamon
Merci (non sarcastiquement cette fois) pour le commentaire, András Salamon. Je le jugerais utile moi-même, mais je suis toujours un nouvel utilisateur sur ce site de débordement. Quoi qu'il en soit, je suis désolé, ma réponse semble hors sujet. J'ai peut-être abordé la question de manière plus lâche que je ne le pensais, mais je pense que ma réponse répond à la question d'origine en répondant à une question similaire et en établissant ensuite des parallèles entre les deux. Est-ce peut-être trop détourné une façon de répondre?
Hawkwing
0

Je me souviens de xkcd 505: A Bunch of Rocks .

Tout ordinateur du monde réel est soumis à un certain niveau de bruit. Une simulation d'un ordinateur universel dans l'univers de vie infini idéal de Conway aura un temps moyen entre les pannes dépendant des détails techniques de sa conception. Il calculera de manière fiable pour une période probabiliste quantifiable, de manière non fiable pour une période d'erreurs accumulées, puis pas du tout .

Je m'attendrais à ce qu'un modèle de logique floue ou de superposition quantique démontre clairement quelle fiabilité devrait être attendue d'une construction particulière. On peut vouloir simuler les sorties attendues de divers composants, plutôt que d'itérer sur toutes leurs cellules, à quelque degré qu'ils puissent être isolés les uns des autres. On pourrait être en mesure de quantifier les interférences attendues des composants défaillants. Un algorithme génétique devrait être le meilleur moyen de développer des composants {tolérant, résistant, corrigeant} aux défauts avec des MTBF aussi grands que souhaité pour une distribution de bruit donnée.

user130144
la source
(vote mystérieux ici) Une réponse quantitative serait très spéculative. Il ne peut y avoir de réponse plus précise que «oui, conditionnellement» sans une expérimentation approfondie sur une implémentation choisie d'une UTM. Un ordinateur normal dans un environnement à rayonnement élevé est toujours pratiquement un UTM, ne serait-ce que brièvement.
user130144