CAGEN: Universal Logic Gates Challenge

Home

CAGEN Challenge Problem

Prev

Next

WARNING: THIS COMPETITION PROPOSAL IS STILL IN DRAFT FORM This CAGEN challenge problem is still considered in draft form and may be revised. This banner will be removed when challenge has been finalized and selected by the CAGEN steering committee. For more information, see the CAGEN home page.

Synopsis: This challenge requires the demonstration of a scalable and robust NAND (“not and”) or NOR (“not or”) logic gate. Successful designs will allow the use of multiple coupled gates in a cell to compute arbitrarily complex logic. Circuits should employ commonly available inputs (e.g. IPTG) and output a fluorescent signal.

Motivation: Every Boolean logic gate can be constructed entirely out of NAND gates, and can also be constructed entirely out of NOR gates. For this reason, NAND and NOR gates are said to be universal‹they can be wired together to express arbitrarily complex logic. The main difference between electronic logic gates and current implementations of biological logic gates is that current biological logic gates cannot be used in multiple contexts in a single cell. Constructing complex logic statements out of universal gates in biological systems will require a rethinking of current biological logic gate design.

Impact: The availability of truly scalable logic gates will enable the construction of multiple complex circuits which can be linked together in a modular fashion. This would provide a basic framework for the the construction of complex synthetic devices such as biological counters and sensors which can give a defined output based on a combination of complex inputs. Applications would be diverse, including basic biology, medicine, environmental science, and agriculture.

Metric: Competitors should demonstrate the construction of three Boolean logic gates using various combinations of a single universal logic gate. Entrants will be judged based on:

• Switch-like response of device to inputs
• Complexity with regards to the logic statements constructed (i.e. an XNOR gate is more difficult to construct with NAND logic than an OR gate)
• Parsimony with regards to the number of gates in the circuit (e.g. an optimal OR gate will be made out of 3 NAND gates)

Selection of the winner shall be done by a jury consisting of the CAGEN steering committee.

Contact: To provide feedback on this challenge, send e-mail to Richard Murray (murray-at-caltech-dot-edu), representing the steering committee.