0
\$\begingroup\$

Biologist here but I've been reading about functional completeness in digital logic and I am wondering if there is a universally complete circuit that can be modified to express any boolean function for 2 or 3 inputs? Maybe this could be done by having a big circuit and turning on/off certain logic pathways of the circuit to change its boolean function? Or modifying connections as to skip certain gates altogether?

I am sorry if this is a dumb question but couldn't find any information on this. I am thinking this could be interesting for synthetic genetic circuits.

---------------- NEW EDIT

Clearly, my question was too vague. In synthetic biology, we are starting to create what we are calling "genetic circuits" (like a genetic flip-flop, circuits with memory, or any other simple circuits), emulating the electrical engineering discipline. But instead of cables that transport electrons, it is genes that produce transcpritors (or RNAP flux) that activate or repress other genes. We are even at the point where we are creating genetic design automation tools.

However, the endeavor of building a genetic circuit and implementing it into a host organism is one that takes a lot of time, money, and effort. So my question is more like: Could a universal genetic circuit be built once, to implement into a host organism once, and then turning one or more gates ON or OFF, have the circuit behave with different behaviors?

So I imagine something like this: enter image description here

Where one could cancel/knock out one or two gates or cables and change the function of the circuit to one which the researcher would like.

\$\endgroup\$
10
  • \$\begingroup\$ Just as a comment, in biology, genetic circuits can be more adaptable/modifiable than electrical ones (like changing connections, silencing gates, etc). So maybe if there is a solution that would be impractical for electrical circuits, it could be useful for synthetic biology. \$\endgroup\$ Commented Jan 8, 2020 at 19:11
  • 1
    \$\begingroup\$ static memory could be used for that ... some of the address bits would be inputs and some of the address bits would be function selectors \$\endgroup\$
    – jsotola
    Commented Jan 8, 2020 at 19:12
  • 1
    \$\begingroup\$ Yes it can be done with many more inputs using Programmable Logic Chips and uC with a lookup table (Karnaugh Map) I thought Biology was mostly analog circuits with saturation limits and comparators then that go into logic. Consider defining it as a lookup table ( see Karnaugh Map) using an addressable Mux/Selector \$\endgroup\$ Commented Jan 8, 2020 at 19:35
  • \$\begingroup\$ Machine learning and the concept of neurons in artificial neural networks may also interest you. \$\endgroup\$
    – rdtsc
    Commented Jan 8, 2020 at 19:56
  • 1
    \$\begingroup\$ Part of the problem here is that you haven't explained how exactly you would customize the function. You talk about "cancel/knock out...gates or cables" but it is not clear what that means. If you can change connections between things then the FPGA approach is what you want. \$\endgroup\$ Commented Jan 9, 2020 at 16:23

3 Answers 3

4
\$\begingroup\$

Any PLD, CPLD, or FPGA (three generations of programmable logic chips) has a programmable gate array that can emulate a wide range of logic functions.

In terms of a non-programmable, off-the-shelf chip, the closest thing probably is an AND-OR-Invert gate.

https://en.wikipedia.org/wiki/AND-OR-Invert

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You don't even need a CPLD/FPGA; an EEPROM can be programmed to be a lookup table, using the address bits as inputs and data bits as outputs. \$\endgroup\$
    – Hearth
    Commented Jan 8, 2020 at 19:25
2
\$\begingroup\$

If you are looking for an off the shelf part having two inputs and one output, a multiplexer can be used to do the job. Inputs on control lines and MUX inputs connect to the appropriate logic levels to produce the functionality needed.

\$\endgroup\$
1
\$\begingroup\$

Parallel PROM and RAM chips are the simplest form of programmable logic.

When most people think about these chips, they simply see it as a medium for data storage, not too different from a hard drive. When software programmers think about them, sometimes they visualize it as a table lookup or array indexing process: one sends a n-bit address to the chip, and retrieves the corresponding n-bit word, the RAM is just a huge array.

A 28C16 EEPROM

But alternatively, ROM and RAM chips can be seen as a universal logic circuit - Physically, the chip maps an arbitrary n-bit input signals (A0-A11) to an arbitrary n-bit output signal (D0-D7). As long as the control signals and timings are appropriate, they can be used to implement any Boolean function by writing the wanted pattern of data to the memory chip.

Speaking of PROM, it's a type of ROM, which one can change its stored data by taking it offline, reprogram it, and put it back online (the most commonly used variant is EEPROM, which can be reprogramed electrically). Thus, it can implement any combinational logic (the type of logic without memory and state, giving the same input, it always returns the same output), and one can change its functionality by reprogramming it.

Speaking of RAM, the data on the chip can be modified on-the-fly, thus, it can implement sequential logic (the type of logic with memory and state, the output depends on its current and previous input).

With only RAM and ROM, building a Turing-complete digital computer is not impossible.

Later development of programmable logic, such as PAL, CPLD, and FPGA, all originated from PROM.

\$\endgroup\$
2
  • \$\begingroup\$ You can also make sequential circuits using current state (output) feedback; I did this for an 8 phase differentially gray coded modulator many years ago. \$\endgroup\$ Commented Jan 9, 2020 at 15:56
  • 1
    \$\begingroup\$ Simplest? Hardly. Do you know how many transistors (or 2-input gate equivalents) it takes to build even a small ROM? \$\endgroup\$
    – Dave Tweed
    Commented Jan 10, 2020 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.