The set with components { 3 , 7 , 10 }
Mixing
produces all sums and all differences:
0=10-7-3, 3, 4=7-3,
6=10+3-7, … , 20=10+7+3
The "simon problem", conceived by Daniel Simon in 1994, changed that: It showcases the efficiency of an alternative computational models using superposition over digital computers. In other words, certain problems have no equivalent in conventional Turing languages.
The idea in the text below is to create a dialect of python. To allow a programming language to have an intermodulation system of an analogue computer at it's core. Intermodulation, the distortion of a signal, is a form of superposition. As Thomas Toffoli wrote: " one attains a closer correspondence between the behavior of abstract computing systems and the microscopic physical laws (which are presumed to be strictly reversible) that underly any concrete implementation of such systems
".
Source material
Snippets
NP Problems by Example: The Subset Sum Problem
The total of a cash register in a shop should match the prices of goods that were disappeared from the stock inventory at the end of the day. If the cash total is smaller than the sum of the prices of the disappeared goods, we suspect that some goods are stolen.
But, what goods were sold and what goods were stolen?
|
CASH TOTAL: |
1’205 1’205 = 35 + 95 + 870 + 155 + 50 |
|
PRICES: |
155, 870, 35,
50, |
In the example above a product with price 12 was stolen.
To find a components from a sum, we use this implementation in “R”:
> library(adagio)
> components = c(155 , 870 , 35 , 50 , 12 ,95 )
> components[subsetsum(components, 1205 )$inds]
[1] 155 870 35 50 95
> sum(components[is$inds])
[1] 1205
The general solution to know what items from a given set are part of a sum is a “NP” problem: It is complex and very time consuming to solve.
A more simple example of this modulation mixer is shown in the table below with as input { 3 , 7 , 10 }.
|
The set with components { 3 , 7 , 10 } |
Mixing
produces all sums and all differences: |