Unconventional computation 1/2 - univ-orleans.fr · molecules (Fu and Seeman 1993) or other branched constructs. This study uses molecules whose design was previously report-ed (Winfree

Unconventional computation 1 / 2

Unconventional computation 1 / 2Introduction aux et tour d'horizon desmodèles non conventionnels de calcul

Jérôme Durand-Lose

Laboratoire d'Informatique Fondamentale d'Orléans

Université d'Orléans, Orléans, FRANCE

ÉNS Cachan � 2 septembre 2014

1 / 71


1 Calcul conventionnel ?

2 Calcul in�ni

3 Manipulation des réels

4 Natural computing

5 Assemblage de tuiles

6 Automates cellulaires

7 Modèles à base de géométrie euclidienne

8 Intuition d'un mode /monde continu

9 Formalisation

10 Propriétés

11 Fractales et calcul fractal

12 Hypercalcul

2 / 71


Calcul conventionnel ?


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

3 / 71



L'Informatique est une science

Théorie, prédiction, réfutation

MathématisationModèle, prédiction. . .

ExpérimentationPrototypage, mesure de performances. . .

ApplicationOrdinateur, internet, intelliphone. . .

4 / 71



Paradigmes ?

Modèles

Machine de Turing, machine RAM. . .

Fonctions récursives, λ-calcul. . .

Modèles du parallélisme, du distribué, des communications. . .

Réseaux de Pétri, Abstract state machine. . . (véri�cation. . .)

( logique et mathématiques discrètes)

Paradigme implicite

Action atomique ( temps discret)

Valeurs discrètes

5 / 71



Paradigme conventionnel

� correspond� à nos ordinateurs et y est � implantable �

Machines de Turing (ou équivalent) :Calcul des données au résultat

Espace, valeurs, états discrets

Temps discret

Classes de calculabilité

Classes de complexité

Autant de façons de ne pas être conventionnel !

6 / 71



Sortir des bornes

Comportement et non production de résultats

Décider la Halte

Hyper-computing

Classes de complexité incomparables

ce que l'on peut encore faire en limitant une ressource

Valeurs continues

Analog computation

Temps continu

Continuous computation

7 / 71



Déplacement du paradigme, monde ouvert

Sans arrêt

système d'exploitation

serveur

Interactionagents

dialogue

Communication

transmission, acheminement de l'information

π-calcul

8 / 71



Machines de Turing

Automate �ni

Tête Lecture/Écriture

Ruban

q

^ entrée/mémoire/sortie

Entrée écrite sur le ruban

Résultat écrit sur le ruban. . .quand la machine s'arrête

Itérations

^

qf

b b a b #

^

qf

b b a b #

^

q2

b b a # #

^

q1

b b # # #

^

q1

b a # # #

^

q1

a a # # #

^

qi

a b # # #

^

qi

a b # # #

^

qi

a b # # #9 / 71


Calcul in�ni


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

10 / 71


Calcul in�ni

Variations sur les machines de Turing

Quasi-conventionnelles

aléatoires

non-déterministes

alternantes

Sans arrêt

à essais et erreurs �nis (change d'avis un nombre �ni de fois)On peut déjà décider la Halte !

11 / 71


Calcul in�ni

À l'in�ni, et après

À temps in�ni

dé�nition d'une limite pour chaque case

Accélérante (vers la � réalisation�)

chaque transition est deux fois plus rapide que la précédente

in�nité d'itérations mais durée totale �nie connue

Trans�nie / ordinale (Hamkins, 2007)

on repart de la limite...

limite pour l'état et la position de la tête

état initial, transition suivante, transition limite échelle de temps ordinale

le ruban (espace) peut aussi être ordinal !

12 / 71


Calcul in�ni

Réalisable ?

Variations et � démonstrations � de la thèse de Church-Turingà partir de

causalité, localité

densité �nie d'information, granularité espace-temps

� discrétisation� à une certaine échelle( automates cellulaires)

(espace euclidien)

Calcul quantique

basé sur la superposition quantique(+ opérateur hermitiens + observations)

classes de complexité di�érentes

� téléportation quantique�

13 / 71


Calcul in�ni

Relativité restreinte, générale, cosmologie. . .

À grande échelle, notre espace-temps n'est pas euclidienIl véri�e(rait) les équations de la RGIl existe beaucoup de solutions � intéressantes �

Accélération relative

Deux time-like curve, l'une accélérée par rapport à l'autre

Premier exemple

célérité ↗ écoulement du temps ↘atteindre la vitesse de la lumière

atteindre la �n des temps en un temps �ni

récupère le résultat (mais plus grand chose à faire)

14 / 71


Calcul in�ni

Utilisation de singularités

Trou noir où on plongerait (Etesi and Németi, 2002)

et on y serait freiné

Trou noir où on lancerait une machine

qui y serait accélérée

on resterait l'oreille collée à l'horizon

Structures emboîtées (Hogarth, 2004)

monter la hiérarchie arithmétique

et pourquoi pas. . . (Stannett, 2013)

revenir mais en inversant temps et espace

modi�er le passé (p.e. la valeur d'une variable)

15 / 71


Manipulation des réels


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

16 / 71



�Vrais � réels

Implantésdouble 3.54e41

nombre �ni de valeurs / Approximation

Symbolique√2.π

nombre dénombrable de valeurs / Exact

General Purpose Analog Computer (Shannon, Pour-El)

Système linéaire d'équations di�érentielles

Analyse récursive (Weihrauch, 2000)

Représentation in�nie, approximation convergenteρ($q0$q1$ . . . $qi$ . . . ) = x ssi qi ∈ Q et |qi − x | < 2−i

Machine qui lit et écrit (sans raturer) dans ce format

Temps in�ni pour une réponse complète / exacte

17 / 71



Modèle Blum, Shub et Smale (Blum et al., 1998)

Valeursexactes

pas de question de représentations

Manipulation

évaluation de polynôme en les variables

branchement en fonction du signe

en temps constant

� extension� des automates à compteurs

généralisation :remplacer R par n'importe quelle structure (semi-)algébrique

18 / 71



Fonction R-Récursive (Moore, 1996)

Ensemble de fonctions. . .

contenant constantes 0 et 1 (et projections)

clos par composition

clos par récursion di�érentielle :

h(~x , y) = f (~x) +

∫ y

0

g(~x , t, h(~x , t))dt

clos par recherche de zéro :

h(x) = infy selon |.| puis signe

h(~x , y) = 0

19 / 71


Natural computing


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

20 / 71


Natural computing

Physique et Biologie

Inspiration pour l'informatique (p.e. méta-heuristiques)

recuit simulé

algorithmes génétiques / évolutionnistes

colonies de fourmis

L'utiliser pour calculer, p.e. optique

communication, �bre optique, multiplexeurs optiques. . .

déformation d'images, transformée de Fourrier. . .(Naughton and Woods, 2001)

prismes, caches. . . (Goliaei and Jalili, 2012)

21 / 71


Natural computing

Reaction Systems (Ehrenfeucht and Rozenberg, 2010)

soupe chimique

réactions

Population protocols (Angluin et al., 2007)

nuée d'automates simples

rencontres au hasard

mise à jour locale

22 / 71


Natural computing

Membrane computing / P-Systems (P un, 2002)

a a a

a

a

b b

b

c

Membranes incluses les unes dans les autres

Objets (symboles) sont dans les espaces délimités

Règles pour ajouter / enlever des objets /membranes

23 / 71


Natural computing

DNA computing (P un et al., 1998)

Soupe / action / sélection

Grand nombre de valeurs di�érentes engendrées

Ne garder que celles représentant une solution

Modi�cations

Grosse molécule codant les données

Modi�cations chimiques faisant un calcul

Construction de formes

Repliement des protéines

Interaction / assemblage

(auto-assemblage des tuiles)

24 / 71


Assemblage de tuiles


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

25 / 71



Algorithmic Self-Assembly of DNA (Winfree, 2000)

Fig .3

ends; this necessitates the use of DNA double-crossover (DX)molecules (Fu and Seeman 1993) or other branched constructs.

This study uses molecules whose design was previously report-ed (Winfree et a. 1998a). As an initial demonstration of molecu-

lar Wang tiles, we chose the simplest non-trivial set of tiles: thetwo tiles, A and B, from Figure 1. Translated into molecularterms, as shown in Figure 6, we obtain a DX system (using theDAO variety of DX (Fu and Seeman 1993)) that self-assemblesin solution into two-dimensional crystals with a well-definedsubunit structure, as reported in Winfree et al. (1998a).

2 Materials and Methods

2.1 DNA Sequences and Synthesis

All oligonucleotides were synthesized by standard methods,PAGE purified, and quantitated by UV absorption at 260 nm inH2O. The exact sequences are given in Winfree et al. (1998a).

2.2 Annealing of Oligonucleotides

The strands of each DX unit were mixed stoichiometrically anddissolved to concentrations of 0.2 to 2 µM in TAE/Mg++ buffer(40 mM Tris·HCl (pH 8.0), 1 mM EDTA, 3 mM Na+, 12.5 mMMg++). The solutions were annealed from 90°C to room temper-ature over the course of several hours in a Perkin-Elmer PCRmachine (to prevent concentration by evaporation). To producelattices, equal amounts of each DX were mixed and annealedfrom 50°C to 20°C over the course of up to 36 hours. In somecases (Figure 11abc and Figure 10def) all strands were mixedtogether from the very beginning.

2.3 Gel Electrophoresis Studies

For gel-based studies, T4 polynucleotide kinase (Amersham) wasused to phosphorylate strands with 32P; these strands were thenPAGE purified and mixed with an excess of unlabeled strands. Non-denaturing 5% PAGE (19:1 acrylamide:bis-acrylamide) inTAE/Mg++ was performed at 4°C. For denaturing experiments, afterannealing in T4 DNA ligase buffer (Amersham) (66 mM Tris·HCl

Algorithmic Self-Assembly of DNA 265

A BBB

BB

A

AA

AAA

BBB

AAAB

BA

A

BBBBB

AAAA

A B

Figure 1: A system of 2 tiles that form a periodic striped lattice.

AAAA

BBBBB

CCCC

DDDDD

AAA

ABBBBB

C

CC

C

A B

C D


S

0

0 1

1

S

1 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

1 0 1 0 0 0 0

0 1 1 0 0 0

1 1 1 0 0

0 0 0 1

1 0

rollover

no rollover

bit = 0

bit = 1

Figure 3: A system of 3 input tiles and 4 rule tiles that form an aperiodic tiling.The rows in the tiling are the consecutive integers, represented in binary.

programtiles

computation

output0 0 0 0 0 1 1 0 0 0 0 1

inputpreassembled

1 100 1 0 0 1 1 0 01

Figure 4: The framework for universal computation by tiling. An input arrange-ment is presented at the bottom. The sequence of exposed shapes encodes theinput information. The program, a set of rule tiles (top), determines the continu-ation of the tiling pattern. The output is encoded in the final, uppermost layer ofthe tiling.

Tuiles : grosses molécules

S'attachent grâce à desbrins d'ADN

On part d'une graine

Formes apparaissent paragrégation

Motivations théoriques

Expériences d'assemblages(tapis Serpinski)

Nanotechnologies

26 / 71



Calculer

À partir de la graine,mise en place de l'entrée

Ligne du dessus commence avecla représentation de la transition

Mise à jour distribuéeni séquentielle ni parallèle synchrone

^ qfb b a b #

^ qfb b a b #

^ q2b b a # #

^ q1b b # # #

^ q1b a # # #

^ q1a a # # #

^ qia b # # #

^ qia b # # #

^ qi a b # # #

27 / 71



Construction de formes

un carré ?

tous les carrés ?

en temps optimal ? (Becker et al., 2008)

Questions (Becker, Pattitz, Woods)

formes/�gures atteignables ?

séparations des températures ?

universalité intrinsèque : un jeu de tuiles simulant tous lesautres

28 / 71


Automates cellulaires


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

29 / 71



(von Neumann et Ulam 1952)

agencement bi-in�ni de cellules

à chaque itération, toutes les cellules changent d'état enfonction des voisines

mode de fonctionnement des cellules identique(règle de transition unique)

Diagramme espace-temps

. . . . . .

30 / 71








. . . . . .

30 / 71








. . . . . .

30 / 71








. . . . . .

30 / 71








. . . . . .

30 / 71



Propriétés

dynamique uniforme dans le temps et l'espace

massivement parallèle

synchronisation forte

Modélisation

parallélisme à grain �n

tout phénomène physique uniforme dans l'espace

Temps �ni

localement simulable en temps polynomial

espace hyperbolique : résout SAT en temps polynomial(Margenstern and Morita, 2001)

31 / 71



Problématique propre

Synchronisation d'une ligne de fusiliersun seul généralpas de communication globaleinterdiction de tirer avant

Approche récursive (Goto, 1966, Fig. 3+6)

32 / 71



Unconventional computation 2 / 2géométrie euclidienne et machines à signaux

Jérôme Durand-Lose

Laboratoire d'Informatique Fondamentale d'Orléans

Université d'Orléans, Orléans, FRANCE

ÉNS Cachan � 2 septembre 2014

33 / 71




2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

34 / 71


Modèles à base de géométrie euclidienne


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

35 / 71



Règle et compas (Huckenbeck, 1989)

Objets

points, droites, cercles

Primitives

nouveau point (intersection cercles, droites)

nouvelle droite

nouveau cercle

avoir une intersection ?

appartenir à ?

Automates

basé sur ces primitives

36 / 71



À dérivée constante par morceau(Asarin and Maler, 1995; Bournez, 1999)

Régions polygonales

Vitesse constante parrégion

Calculer

zone départ

zone d'arrêt

Coe�cients entiers

évolution indécidable

degré d'indicidabilitédépendant dimension

37 / 71






Calculer

zone départ

zone d'arrêt




37 / 71






Calculer

zone départ

zone d'arrêt




37 / 71



Automate cellulaire et assemblage de tuiles

D. E.-T. dé�nis par des contraintes

locales

discrètes

(liens pavages)

Fig .3

ends; this necessitates the use of DNA double-crossover (DX)molecules (Fu and Seeman 1993) or other branched constructs.

This study uses molecules whose design was previously report-ed (Winfree et a. 1998a). As an initial demonstration of molecu-

lar Wang tiles, we chose the simplest non-trivial set of tiles: thetwo tiles, A and B, from Figure 1. Translated into molecularterms, as shown in Figure 6, we obtain a DX system (using theDAO variety of DX (Fu and Seeman 1993)) that self-assemblesin solution into two-dimensional crystals with a well-definedsubunit structure, as reported in Winfree et al. (1998a).

2 Materials and Methods

2.1 DNA Sequences and Synthesis

All oligonucleotides were synthesized by standard methods,PAGE purified, and quantitated by UV absorption at 260 nm inH2O. The exact sequences are given in Winfree et al. (1998a).

2.2 Annealing of Oligonucleotides

The strands of each DX unit were mixed stoichiometrically anddissolved to concentrations of 0.2 to 2 µM in TAE/Mg++ buffer(40 mM Tris·HCl (pH 8.0), 1 mM EDTA, 3 mM Na+, 12.5 mMMg++). The solutions were annealed from 90°C to room temper-ature over the course of several hours in a Perkin-Elmer PCRmachine (to prevent concentration by evaporation). To producelattices, equal amounts of each DX were mixed and annealedfrom 50°C to 20°C over the course of up to 36 hours. In somecases (Figure 11abc and Figure 10def) all strands were mixedtogether from the very beginning.

2.3 Gel Electrophoresis Studies

For gel-based studies, T4 polynucleotide kinase (Amersham) wasused to phosphorylate strands with 32P; these strands were thenPAGE purified and mixed with an excess of unlabeled strands. Non-denaturing 5% PAGE (19:1 acrylamide:bis-acrylamide) inTAE/Mg++ was performed at 4°C. For denaturing experiments, afterannealing in T4 DNA ligase buffer (Amersham) (66 mM Tris·HCl

Algorithmic Self-Assembly of DNA 265

A BBB

BB

A

AA

AAA

BBB

AAAB

BA

A

BBBBB

AAAA

A B


AAAA

BBBBB

CCCC

DDDDD

AAA

ABBBBB

C

CC

C

A B

C D


S

0

0 1

1

S

1 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

1 0 1 0 0 0 0

0 1 1 0 0 0

1 1 1 0 0

0 0 0 1

1 0

rollover

no rollover

bit = 0

bit = 1

Figure 3: A system of 3 input tiles and 4 rule tiles that form an aperiodic tiling.The rows in the tiling are the consecutive integers, represented in binary.

programtiles

computation

output0 0 0 0 0 1 1 0 0 0 0 1

inputpreassembled

1 100 1 0 0 1 1 0 01

Figure 4: The framework for universal computation by tiling. An input arrange-ment is presented at the bottom. The sequence of exposed shapes encodes theinput information. The program, a set of rule tiles (top), determines the continu-ation of the tiling pattern. The output is encoded in the final, uppermost layer ofthe tiling.

38 / 71



Automates de Mondrian (Jacopini and Sontacchi, 1990)

Contraintes

locales

continues

Une dimension pour le temps

39 / 71


Intuition d'un mode /monde continu


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

40 / 71



Automate cellulaire : utilisation de signaux

Synchronisation d'une ligne de fusiliers (Goto, 1966)

41 / 71



Analyse en terme de signaux

Das et al. (1995)

in a chromosome. This de�nes one generation of the GA; it is repeated G times for one GA run.FI(�) is a random variable since its value depends on the particular set of I ICs selected toevaluate �. Thus, a CA's �tness varies stochastically from generation to generation. For thisreason, we choose a new set of ICs at each generationFor our experiments we set P = 100, E = 20; I = 100, m = 2; and G = 50. M was chosenfrom a Poisson distribution with mean 320 (slightly greater than 2N). Varying M preventsselecting CAs that are adapted to a particular M . A justi�cation of these parameter settings isgiven in [9].We performed a total of 65 GA runs. Since F100(�) is only a rough estimate of performance,we more stringently measured the quality of the GA's solutions by calculating PN104(�) withN 2 f149; 599; 999g for the best CAs in the �nal generation of each run. In 20% of the runsthe GA discovered successful CAs (PN104 = 1:0). More detailed analysis of these successful CAsshowed that although they were distinct in detail, they used similar strategies for performing thesynchronization task. Interestingly, when the GA was restricted to evolve CAs with r = 1 andr = 2, all the evolved CAs had PN104 � 0 for N 2 f149; 599; 999g. (Better performing CAs withr = 2 can be designed by hand.) Thus r = 3 appears to be the minimal radius for which the GAcan successfully solve this problem.β γ

δν

β γ

(a) Space-time diagram. (b) Filtered space-time diagram.Site0 74Site0 74

0

74

Tim

e

α

γδ

µ

Figure 1: (a) Space-time diagram of �sync starting with a random initial condition. (b) The same space-time diagram after �ltering with a spatial transducer that maps all domains to white and all defects toblack. Greek letters label particles described in the text.Figure 1a gives a space-time diagram for one of the GA-discovered CAs with 100% perfor-mance, here called �sync. This diagram plots 75 successive con�gurations on a lattice of sizeN = 75 (with time going down the page) starting from a randomly chosen IC, with 1-sites col-ored black and 0-sites colored white. In this example, global synchronization occurs at time step58. How are we to understand the strategy employed by �sync to reach global synchronization?Notice that, under the GA, while crossover and mutation act on the local mappings comprising a442 / 71



Conception avec des signaux

Fischer (1965)

43 / 71


Formalisation


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

44 / 71


Formalisation

SignauxTim

e(N

)

Space (Z)

Tim

e(R

+)

Space (R)

Signal (meta-signal)

Collision (règle)

45 / 71


Formalisation

Vocabulaire et exemple : trouver le milieu

M M

Meta-signaux (vitesse)

M (0)

div (3)hi (1)lo (3)

back (-3)

Règles de collision

{ div, M }→ { M, hi, lo }{ lo, M }→ { back, M }

{ hi, back }→ { M }

46 / 71


Formalisation


div M M


M (0)div (3)

hi (1)lo (3)

back (-3)



{ hi, back }→ { M }

46 / 71


Formalisation


div M

M hi lo

M


M (0)div (3)hi (1)lo (3)

back (-3)


{ div, M }→ { M, hi, lo }

{ lo, M }→ { back, M }{ hi, back }→ { M }

46 / 71


Formalisation


div M

lo

M

M hi

backM


M (0)div (3)hi (1)lo (3)

back (-3)



{ hi, back }→ { M }

46 / 71


Formalisation


div M

lo

M

hi

backM

MM


M (0)div (3)hi (1)lo (3)

back (-3)



{ hi, back }→ { M }

46 / 71


Formalisation

Dynamique complexe

47 / 71


Formalisation

Dynamique complexe

47 / 71


Formalisation

Dynamique complexe

47 / 71


Formalisation

Dynamique complexe

47 / 71


Propriétés


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

48 / 71


Propriétés

Calcul par simulation d'une machine de Turing

^

qf

b b a b #

^

qf

b b a b #

^

q2

b b a # #

^

q1

b b # # #

^

q1

b a # # #

^

q1

a a # # #

^

qi

a b # # #

^

qi

a b # # #

^

qi

a b # # #^

^

^

a

a

b

b

b

a

b

b

#

a

a

b

−→qi

−→qi

−→qi

←−q1

−→q1

−→q1

−→q2←−#

−→#

←−qf

←−#

−→#

←−qf

←−#

−→# −→

#

#

←−qf

←−qf

←−qf

49 / 71


Propriétés

Dynamique à trois vitesses sur Q (Becker et al., 2013)

Vitesses ∈ QPositions initiales ∈ Q

Collisions à coordonnées rationnelles(solution d'un système linéaire à deux équations sur Q)

Implanté en Java

précision exacte (sur Q)

(tonnes de diagrammes espace-temps)

50 / 71


Propriétés


Engendre tout à chaque fois

50 / 71


Propriétés


Diagramme inclus dans une grille

0 1 2 3

Pas d'accumulation

Pas de calcul

50 / 71


Propriétés

Algorithme d'Euclide

wb−→init

←−zag

w0

wb

−→zig

wa

−−→ZIG

←−zag

w0

←−−ZAG

−−→ZIG

wb

−→zig

←−−ZAG−−→ZIG

←−zag

w0

←−−ZAG

wb

←−−ZAG−→zigw0

wr

a

b

a mod b

calcul du modulo

ré-itère en changeant les rôles

pgcd

pgcd converge (sur les entiers)

51 / 71


Fractales et calcul fractal


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

52 / 71



Génération de fractales

53 / 71



Génération de fractales

Fractale Construction

cell

seed

cell

border

cell

right

right

left

right

left

right

left

1 ϕ

ϕ-1 1

ϕ est le nombre d'or

54 / 71



Calculer avec 3 vitesses ? (Durand-Lose, 2013)

utiliser la fractale... mais sans l'engendrer

a b cq0

. . .

b b cq0

. . .

b c cq0

. . .

b c bq0

. . .

b b bq0

. . .

c b bq0

. . .

c c bq0

. . .

c c c #

q0. . .

c c c bq1

. . .

c c b bq1

. . .

c c b c #

q1. . .

c c b c a #

q1. . .

q0a

q0b

q0

c

c

q0

b

q0

q0

b

q0

b

q0

border

c

enlarge

c

left right

q0

rightc

right

q0c q1

q1b

q1

border

c

c

bc

enlargeq1

55 / 71



Satisfaction de formules booléennes quanti�ées

QSAT

∃x1∀x2∀x3x1 ∧ (¬x2 ∨ x3)

Duchier et al. (2011)

une formule QSAT une machine à signaux

56 / 71



Création de l'arbre de tous les cas

−−−→startlo w

−→m0

←−aw

←−a −→aw

−→a←−m1

−→m1

←−aw

←−a −→a

x1

←−a −→aw

←−m2−→m2

←−m2−→m2

x2 x2

w bl x3br x2 bl x3

br x1 bl x3br x2 bl x3

br w

57 / 71



Propagation dans l'arbre

58 / 71



Duplication du faisceau

−→m0

←−a−→xl1

−→xrlc2

−→¬rl

−→xrr3

−→∨r

−→∧

−−→store

←−a

−−−−→collect

−→a

←−m1

−→m1

←−fl

−→tl

←−xrlc2

−→xrlc2

←−¬rl

−→¬rl

←−xrr3

−→xrr3

←−∨r

−→∨r

←−∧

−→∧

←−−store

−−→store

←−−−−collect

−−−−→collectL∃

59 / 71



Évaluation de la formule

∧

x1 ∨

¬

x2

x3

cas :

x1 vrai

x2 faux

x3 vrai−→m3

←−a

−→tl

br−→frlc

←−Tl−→

¬rl

←−Tl

−→frlc

br

−→trr

←−Tl

−→¬rl

←−Frlc

−→∨r←−Tl

−→trl

br

−→∧←−Tl

−→trr

←−Trl

−→∨r←−Trl −→

trr

br

−→t()r ←−Trr

−→tr

br−→id

←−Tr

−→tbr−−→

store

←−T

−→T∅

br−−−−→collect

T

←−−−−success

60 / 71



Agrégation du résultat

−→a ←−a

w←−a

−→aL∃

←−a −→aw

−→a ←−a −→a ←−aw

←−a−→a

R∀

←−a −→aL∃

←−a−→a

L∀

←−a −→aw

−→a ←−a −→a ←−a −→a ←−a −→a ←−a

−→Fail

R∀

←−Fail

−→Fail

L∀

←−Fail −−−−→success

R∀

←−−−−success−→Fail

L∀

←−−−−success

−→Fail

R∀

←−Fail −−−−→success

L∀

←−Fail

−→Fail

L∃

←−Fail

w

←−Fail

w

61 / 71



Complexité

durée constante

profondeur de collisions quadratique

largeur de collisions exponentielle

Machine générique pour QSAT (Duchier et al., 2012)

formule codée uniquement dans la con�guration initiale

durée constante

profondeur de collisions cubique

largeur de collisions exponentielle

62 / 71


Hypercalcul


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

63 / 71


Hypercalcul

Primitives géométriques : accélération et repliement

NormalRéduit

Itéré contracté

64 / 71


Hypercalcul

Hypercomputation

Contraction de l'espace et du temps

automatique

a�ne par morceau

Deux échelles de calcul di�érentes

permet d'observer un calcul in�ni depuis l'extérieur

on peut décider la Halte !

Contractions emboîtées (Durand-Lose, 2009)

65 / 71


Hypercalcul

Dynamiques à deux échelles (Durand-Lose, 2012)

Structure de contrôle

calcul

Ordre

Structure moteur

action

Redémarre

66 / 71


Hypercalcul

Déplacements spatiaux

67 / 71


Hypercalcul

Choisir le lieu de l'accumulation

68 / 71


Hypercalcul

Plus ou moins de retard

choisir la date de l'accumulation

Les accumulations sont exactement les points à coordonnéesc.e. dans le tempsd-c.e. dans l'espace

69 / 71


Hypercalcul

Références

Communautés

Revues Unconventional computation et Natural computation

Conférences Unconventional computation and Naturalcomputation mais aussi DNA, Membrane Computing. . .

Physics and computation workshop

. . .

Lecture

Syropoulos (2010) livre où une grande partie des sujetsprésentés sont abordés

Rozenberg et al. (2012) Handbook of Natural Computing

70 / 71


Références


2 Calcul in�ni


4 Natural computing





9 Formalisation

10 Propriétés


12 Hypercalcul

71 / 71


Références

Angluin, D., Aspnes, J., Eisenstat, D., and Ruppert, E. (2007). Thecomputational power of population protocols. DistributedComputing, 20(4) :279�304.

Asarin, E. and Maler, O. (1995). Achilles and the Tortoise climbingup the arithmetical hierarchy. In FSTTCS '95, number 1026 inLNCS, pages 471�483.

Becker, F., Chapelle, M., Durand-Lose, J., Levorato, V., and Senot,M. (2013). Abstract geometrical computation 8: Small machines,accumulations & rationality. Submitted.

Becker, F., Rémila, E., and Schabanel, N. (2008). Time optimalself-assembly for 2d and 3d shapes : The case of squares andcubes. In Goel, A., Simmel, F. C., and Sosík, P., editors, DNAComputing, 14th International Meeting on DNA Computing,DNA 14, Prague, Czech Republic, June 2-9, 2008. RevisedSelected Papers, volume 5347 of LNCS, pages 144�155. Springer.

Blum, L., Cucker, F., Shub, M., and Smale, S. (1998). Complexityand real computation. Springer, New York.

71 / 71


Références

Bournez, O. (1999). Some bounds on the computational power ofpiecewise constant derivative systems. Theory Comput. Syst.,32(1) :35�67.

Das, R., Crutch�eld, J. P., Mitchell, M., and Hanson, J. E. (1995).Evolving globally synchronized cellular automata. In Eshelman,L. J., editor, International Conference on Genetic Algorithms '95,pages 336�343. Morgan Kaufmann.

Duchier, D., Durand-Lose, J., and Senot, M. (2011). SolvingQ-SAT in bounded space and time by geometrical computation.In Ganchev, H., Löwe, B., Normann, D., Soskov, I., and Soskova,M., editors, Models of computability in contecxt, 7th Int. Conf.Computability in Europe (CiE '11) (abstracts and handoutbooklet), pages 76�86. St. Kliment Ohridski University Press,So�a University.

Duchier, D., Durand-Lose, J., and Senot, M. (2012). Computing inthe fractal cloud: modular generic solvers for SAT and Q-SATvariants. In Agrawal, M., Cooper, B. S., and Li, A., editors,

71 / 71


Références

Theory and Applications of Models of Computations(TAMC '12), number 7287 in LNCS, pages 435�447. Springer.

Durand-Lose, J. (2009). Abstract geometrical computation 3:Black holes for classical and analog computing. Nat. Comput.,8(3) :455�472.

Durand-Lose, J. (2012). Abstract geometrical computation 7:Geometrical accumulations and computably enumerable realnumbers. Nat. Comput., 11(4) :609�622. Special issue onUnconv. Comp. '11.

Durand-Lose, J. (2013). Irrationality is needed to compute withsignal machines with only three speeds. In Bonizzoni, P.,Brattka, V., and Löwe, B., editors, CiE '13, The Nature ofComputation, number 7921 in LNCS, pages 108�119. Springer.Invited talk for special session Computation in nature.

Ehrenfeucht, A. and Rozenberg, G. (2010). Reaction systems : aformal framework for processes based on biochemicalinteractions. ECEASST, 26.

71 / 71


Références

Etesi, G. and Németi, I. (2002). Non-Turing computations viaMalament-Hogarth space-times. Int. J. Theor. Phys.,41(2) :341�370.

Fischer, P. C. (1965). Generation of primes by a one-dimensionalreal-time iterative array. J. ACM, 12(3) :388�394.

Goliaei, S. and Jalili, S. (2012). An optical solution to the 3-satproblem using wavelength based selectors. The Journal ofSupercomputing, 62(2) :663�672.

Goto, E. (1966). Otomaton ni kansuru pazuru [Puzzles onautomata]. In Kitagawa, T., editor, Johokagaku eno michi [TheRoad to information science], pages 67�92. Kyoristu ShuppanPublishing Co., Tokyo.

Hamkins, J. D. (2007). A survey of in�nite time Turing machines.In Durand-Lose, J. and Margenstern, M., editors, Machines,Computations and Universality (MCU '07), number 4664 inLNCS, pages 62�71. Springer.

71 / 71


Références

Hogarth, M. L. (2004). Deciding arithmetic using SAD computers.Brit. J. Philos. Sci., 55 :681�691.

Huckenbeck, U. (1989). Euclidian geometry in terms of automatatheory. Theoret. Comp. Sci., 68(1) :71�87.

Jacopini, G. and Sontacchi, G. (1990). Reversible parallelcomputation: an evolving space-model. Theoret. Comp. Sci.,73(1) :1�46.

Margenstern, M. and Morita, K. (2001). Np problems are tractablein the space of cellular automata in the hyperbolic plane.Theoret. Comp. Sci., 259(1�2) :99�128.

Moore, C. (1996). Recursion theory on the reals andcontinuous-time computation. Theoret. Comp. Sci.,162(1) :23�44.

Naughton, T. J. and Woods, D. (2001). On the computationalpower of a continuous-space optical model of computation. InMargenstern, M., editor, Machines, Computations, andUniversality (MCU '01), volume 2055 of LNCS, pages 288�299.

71 / 71


Hypercalcul

P un, G. (2002). Membrane Computing. An Introduction. Springer.

P un, G., Rozenberg, G., and Salomaa, A. (1998). DNAComputing. Springer.

Rozenberg, G., Bäck, T., and Kok, J. N., editors (2012). Handbookof Natural Computing. Springer-Verlag.

Stannett, M. (2013). Computation and spacetime structure. IJUC,9(1-2) :173�184.

Syropoulos, A. (2010). Hypercomputation. Springer.

Weihrauch, K. (2000). Introduction to computable analysis. Textsin Theoretical computer science. Springer, Berlin.

Winfree, E. (2000). Algorithmic self-assembly of dna : Theoreticalmotivations and 2d assembly experiments. Journal ofBiomolecular Structure and Dynamics, 2(11) :263�270.

71 / 71

Documents

Unconventional computation 1/2 - univ-orleans.fr · molecules (Fu and Seeman 1993) or other branched constructs. This study uses molecules whose design was previously report-ed (Winfree