Transcript Short presentation on Natural Algorithms

Natural Algorithms
Joshua J. Arulanandham
Supervisors:
Professor Cristian S. Calude and Dr. Michael J. Dinneen
The wonders of the world come in two flavours!
How water “finds” the average
l1
l2 l3 (l1 + l2 + l3 ) / 3
Water finds the same level in all limbs due to atmospheric pressure.
Calculating shortest path using strings and beads
E (Destination)
Shortest
path
D
A
C
B
(Source)
As the source, destination nodes in the physical graph-model are stretched apart, the shortest path forms a
straight line between them.
New ideas in the Thesis
Our work is a braid of three ideas/inventions:
A gravity based “computer”—constructed out of beads and rods of an abacus—
that can perform data processing tasks like sorting, searching, etc. with an
efficiency that is unmatched by any conceivable classical computer algorithm.
Bilateral Computing, a paradigm for the construction of natural physical
computing devices which are “bilateral” in nature—devices that do not
distinguish between “computing” and “inverting” a function. These devices can
spontaneously compute as well as invert a given function and can be used to
solve problems that are considered intractable for digital computers.
Balance Machine, a generic natural computational model consisting of
components that resemble an ordinary physical balance. We have shown that
this mechanical model of computation has the same rich “computing repertoire”
of a digital computer.
Bilateral computing devices
?
7919
46239041
?
factor
multiply
?
5839
1
l
A=lxb
b
A “computer” that runs on gravity
How to make a “computer” with beads , rods and
gravity
+
+
=
A “computer” that runs on gravity
4
3
3
4
A “computer” that runs on gravity
3
2
2
2
4
2
3
4
A “computer” that runs on gravity
Sorting {3, 1, 2}
1. Drop 3 beads
(Remember, always from left-to-right)
2. Drop 1 bead
3. Drop 2 beads
1
2
3
A “computer” that runs on gravity
Sorting {2, 4, 3, 2}
1. Drop 2 beads
(Remember, always from left-to-right)
2
2
2. Drop 4 beads
3. Drop 3 beads
3
4. Drop 2 beads
4
The bead-sort computer
The “tilt” operation
900
Bead-Search
1
1
2
2
3
3
4
4
5
5
6
6
Bilateral Computing: Solving SAT
SAT = satisfiability of Boolean formulas
a
b
a’
b
0
1
OR
AND
1
1
?
OR
Evaluating a Boolean function
a
b
a’
b
?
?
1
?
?
Inverting a Boolean function
Input: A Boolean formula such as (a+b) (a’+b)
Question: Is there an assignment (of 0s and 1s) to the variables
(a and b) such that the formula evaluates to 1?
A different approach to invert functions
Setting up inputs and observe outputs
Can we set up the “output” and maneuver “input” settings?
Solving SAT: a different approach
a
b
a’
b
Evaluating a Boolean function
a
b
a’
b
Inverting a Boolean function
Bilateral computing devices
- AND, OR gates
OR gate
AND gate
a b
a+ b
a b
a.b
0 0
0
0 0
0
1 0
1
1 0
0
0 1
1
0 1
0
1 1
1
1 1
1
Inputs (use weights): “push” = 1; “no-push” = 0
Outputs (use fluid level): “up” = 1; “down” = 0
Note: AND gates use a higher threshold (liquid-level) for signaling a 1-output
A computer made of pipes and pistons
Is (~a + b)(a + b) satisfiable?
(~a + b) (a + b)
1. The seesaw always keeps pistons
one up and the other down.
2. Push inputs are “restrained” (one
can use standard weights to give the
exact “push” required rather than
actually pushing).
3. There is a stop-cock in the
apparatus (the weakest spot in the
whole machinery) ready to be
released if pressure exceeds a (~a + b)
certain limit.
(a + b)
a
b
~a
a
b
b (~a + b) (a + b)
0 0
0
1 0
0
0 1
1
1 1
1
Time complexity
OR gates
λ
AND gate
d
Speed =
distance travelled / time taken
t = t1 + t2 = (d/ λ) + t2
t1: time taken for the impulse to reach the pistons
t2: time taken for the pistons to react (due to friction)
d grows linearly with no. of gates; t2, λ (speed of sound in water) are constants
Fluidic logic
Is (x + y) (x + y’) satisfiable?
Balance Machine:
A universal natural computational model
A self-regulating balance
The Balance-Machine
infinite source
filler
+
spiller
X
Y
INPUT pan
(fixed weight)
X+Y
OUTPUT pan
(variable weight)
x
Z
y
Addition
x+y=Z
Schematic representation
+
x
Z
y
Addition
x+y=Z
represents a balance; weights on both sides must balance
+
represents combination of two weights that add up.
(The weights needn’t balance each other.)
small letters, numerals
represent fixed weights (inputs)
capital letters
represent variable weights (outputs)
The balance can compute!
Addition
Increment
+
Z=x+1
+
Z
Z
x
y
1
x
Subtraction
+
Decrement
z
X+1=z
+
X
x+y=Z
z
1
x
X=z-1
Y
x+Y=z
Y=z-x
The balance can compute!
Weights (or pans) themselves can take the form of a balance-machine.
Example 1: Multiplication by 2
1) a + B = A
A
a
B
output
2) a = B
Therefore, A = 2a.
input
Example 2: Division by 2
1) A + B = a
2) A = B
Therefore, A = a/2.
a
A
B
Note: The weight of a balance-machine is the sum of the individual weights on its pans.
The balance can compute!
Multiplication by 4
A = 4d
A
output
B
C
d
input
Division by 4
D = a/4
a
input
B
C
D
output
Sharing pans between balances
Example: Solving simultaneous equations
X+Y=8
X–Y=2
1
+
2
+
8
X1
Y1
Y2
X2
2
outputs
3
X1
4
X2
Y1
Y2
Computation universality of balances
NOT(x)
x + Y = 15
+
x
15
5 + 10 = 15
10 + 5 = 15
Y
NOTE:
Input
true = 10; false = 5;
Output
Interpreted as 1, if > 5 and as 0, otherwise.
Computation universality of balances
AND(x,y)
x + y = Z + 10
+
y
Z
x
+
10
5+5
5 + 10
10 + 5
10 + 10
=
=
=
=
0 + 10
5 + 10
5 + 10
10 + 10
OR(x,y)
x+y=Z+5
+
y
Z
x
+
5
5+5
5 + 10
10 + 5
10 + 10
NOTE:
Input
true = 10; false = 5;
Output
Interpreted as 1, if > 5 and as 0, otherwise.
=5+5
= 10 + 5
= 10 + 5
= 15 + 5
Computation universality of balances
(1)
(2)
(3)
Balance as a transmission line
Balance (2) acts as transmission line, feeding output from (1) into the input of (3).
Solving SAT with balances
Consider the satisfiability of (a + b) (~a + b)
Assumptions
+
+
+
• true = 10; false = 5
+
• Fluid let out in “drops” (of 5 units)
A
B
10
5
Extra1
A’
(1)
B
10
5
Extra2
• Max. weight held by pan = 10 units
(2)
+
A
15
A’
(3)
a
b (~a+b)(a+b)
0
0
0
1
0
0
0
1
1
1
1
1
Machines 1-3 work together, sharing the variables A, B, and A’. The only possible configuration in
which they can “stop” is one of the satisfiable configurations, if any. If the machine keeps
“staggering”, then the expression is not satisfiable.
Why natural algorithms?
“Physics is like sex. Sure,
it may give some practical
results, but that's not
why we do it.”
Which is easier: flipping a coin or its numerical simulation?
Which is faster: protein folding or its numerical simulation?
Given a linear sequence of amino acids, into what three
dimensional configuration will the sequence fold?
A new vocabulary
Boolean logic,
automata theory, etc.
Natural physical processes
“Can your Natural-Computer beat my PC ?”
“It’s not that the bear dances so well, it’s that he dances at all.”