Arthur-Polak technology evolution
Arthur and Polak's evolution of technology, which builds logic functions from NAND gates.
- Name:
arthur_polak - Field:
economics/innovation - Formalism: agent-based model
- References: Thurner et al. 2018; Arthur and Polak 2006
Factory
@register_model(
field='economics/innovation',
tags=('innovation', 'technology', 'combinatorial evolution', 'agents'),
references=('Thurner et al. 2018', 'Arthur and Polak 2006'),
defaults={'until': 200},
)
def arthur_polak(*, max_components: int = 12, max_inputs: int = 3) -> System:
"""Return Arthur and Polak's evolution of technology, which builds logic functions from NAND gates.
The pool starts with the NAND gate and the constants 0 and 1. Every step wires a random circuit from the pool and
keeps it when it computes a wanted function, negation, two-input and, or, exclusive or, nor, equivalence, and
implication, or three-input and, or, parity, and majority, so simple inventions become the building blocks of
complex ones.
Args:
max_components:
The largest number of technologies in a circuit.
max_inputs:
The largest number of inputs of a circuit.
Returns:
system:
The model, with the pool `technologies`, whose size is the reporter `technologies.count`.
Examples:
>>> from skcomplex.models.economics.innovation import arthur_polak
>>> arthur_polak().elements[0].check().prepare().size_
3
"""
primitives = (NAND, FALSE, TRUE)
technologies = GroupElement(
'technologies',
element=TechnologyElement,
size=len(primitives),
values={
'arity': [float(arity) for arity, _ in primitives],
'table': [float(table) for _, table in primitives],
'cost': [1.0, 0.0, 0.0],
},
variable=True,
)
invention = InventionInteraction(
'invention',
technologies='technologies',
max_components=float(max_components),
max_inputs=float(max_inputs),
)
return System(elements=[technologies], interactions=[invention])
Components
class TechnologyElement(Element):
"""Logic circuit in the pool of technologies, described by the truth table of the function it computes.
Bit `r` of the table is the output on the inputs whose bits form `r`, with the first input as the lowest bit.
Args:
label:
The label of the agent or group.
visual:
How the element is drawn, or `None` for `default_visual_`.
arity:
The number of inputs.
table:
The truth table.
cost:
The number of NAND gates in the circuit.
Examples:
>>> from skcomplex.models.economics.innovation import TechnologyElement
>>> GroupElement(
... 'technologies', element=TechnologyElement, size=3, values={'arity': [2, 0, 0], 'table': [7, 0, 1]}
... ).size
3
"""
def __init__(
self,
label: str,
visual: VisualSpec | None = None,
*,
arity: Annotated[float, StateSpec(domain=NN)] = 2,
table: Annotated[float, StateSpec(domain=NN)] = NAND[1],
cost: Annotated[float, StateSpec(domain=NN)] = 1,
) -> None:
super().__init__(label, visual=visual)
self.arity = arity
self.table = table
self.cost = cost
@classmethod
def _get_view(cls) -> type[TechnologyView]:
"""Return the view of the agents of the element."""
return TechnologyView
def _get_laws(self, s: SimpleNamespace) -> list[BaseLaw]:
"""Return no laws, since inventions combine several technologies at once.
Args:
s:
The namespace of the symbols the laws can use.
Returns:
laws:
The laws of the component.
"""
return []
class InventionInteraction(Interaction):
"""Random wiring of technologies of the pool into a circuit, kept if it computes a wanted function more cheaply.
A circuit has between one and `max_inputs` inputs and wires between two and `max_components` technologies in a
row, each pin to an input or to the output of an earlier technology. The output of the last one is the circuit's
output. A circuit that computes a wanted function joins the pool, or replaces the technology of that function when
it uses fewer NAND gates.
Args:
label:
The label of the interaction.
technologies:
The path of the group of technologies.
max_components:
The largest number of technologies in a circuit.
max_inputs:
The largest number of inputs of a circuit.
Examples:
>>> from skcomplex.models.economics.innovation import InventionInteraction
>>> InventionInteraction('invention', technologies='technologies', max_components=6).max_components
6
"""
def __init__(
self,
label: str,
*,
technologies: Annotated[str, RoleSpec()],
max_components: Annotated[float, ParameterSpec(domain=RealSet.open(0, oo))] = 12,
max_inputs: Annotated[float, ParameterSpec(domain=RealSet.open(0, oo))] = 3,
) -> None:
super().__init__(label)
self.technologies = technologies
self.max_components = max_components
self.max_inputs = max_inputs
def _wire(self, pool: list[TechnologyView], model: ModelView) -> tuple[int, int, int]:
"""Return the arity, the truth table, and the cost of a random circuit of technologies of the pool."""
rng = model.rng
n_inputs = int(rng.integers(1, int(model.parameter('max_inputs')) + 1))
n_parts = int(rng.integers(2, int(model.parameter('max_components')) + 1))
signals, cost = InventionInteraction._input_signals(n_inputs), 0
for _ in range(n_parts):
part = pool[int(rng.integers(len(pool)))]
pins = [signals[int(rng.integers(len(signals)))] for _ in range(int(part.arity))]
signals.append(InventionInteraction._apply(int(part.table), int(part.arity), pins, n_inputs))
cost += int(part.cost)
return n_inputs, signals[-1], cost
def _get_laws(self, s: SimpleNamespace) -> list[BaseLaw]:
"""Return the invention rule.
Args:
s:
The namespace of the symbols the laws can use.
Returns:
laws:
The laws of the component.
"""
return [RuleLaw(self.invent)]
def invent(self, model: ModelView) -> None:
"""Wire a random circuit and add it to the pool if it computes a wanted function better.
Args:
model:
The model.
"""
pool = model.agents('technologies', TechnologyView)
arity, table, cost = self._wire(pool, model)
if (arity, table) not in GOALS:
return
known = [technology for technology in pool if (technology.arity, technology.table) == (arity, table)]
if not known:
model.create('technologies', arity=arity, table=table, cost=cost)
elif cost < known[0].cost:
known[0].cost = cost
@staticmethod
def _input_signals(n_inputs: int) -> list[int]:
"""Return the truth tables of the primary inputs of a circuit."""
rows = range(2**n_inputs)
return [sum(1 << row for row in rows if row >> pin & 1) for pin in range(n_inputs)]
@staticmethod
def _apply(table: int, arity: int, signals: Sequence[int], n_inputs: int) -> int:
"""Return the truth table of a gate with a table and an arity, wired to the signals of a circuit."""
output = 0
for row in range(2**n_inputs):
index = sum((signal >> row & 1) << pin for pin, signal in enumerate(signals[:arity]))
output |= (table >> index & 1) << row
return output