Joint work with Daria Pchelina (LIPN), Shinnosuke Seki (UEC Tokyo), and Guillaume Theyssier (I2M)

Oritatami est un modèle de calcul discret introduit par [Geary et al, 2016] pour étudier les capacités de calcul du pliage moléculaire co-transcriptionnel tel qu'il a été mis en œuvre expérimentalement à l'aide d'ARN synthétique [Geary et al, Science 2014]. Le principe est qu'une molécule grossit progressivement et se plie sur elle-même et son environnement en adoptant à chaque étape la forme qui maximise le nombre de liens créés (i.e. qui minimise l'énergie). Il a été démontré en 2018 et 2020 que ce modèle avait la puissance de calcul Turing. Nous démontrons ici qu'il permet également de calculer des formes indécidables, c-à-d telle que la fonction f(x) = 0 ou 1 suivant la position x est occupée ou non, est non-calculable. Un résultat similaire était connu pour l'auto-assemblage de tuiles [Lathrop et al 2011]; ce résultat utilise de façon cruciale le caractère distribué de l'auto-assemblage par tuiles. Il est donc intéressant de constater que le même type de résultat puisse être obtenu pour le modèle séquentiel des oritatami. Notre résultat repose sur la simulation d'un type particulier de machine de Turing, appelé les Turmites auto-évitantes, dont nous démontrons qu'elles peuvent construire des configurations limites non-calculables.