Skip to content

Digital Logic & Finite-State Machines

← Back to Domain-Specific Families

Abstractions about circuits and abstract machines that compute with discrete states, spanning logic-gate technologies (NOR logic, inverter logic gate, integrated injection logic, high-threshold logic), finite-state computation models (Moore machine, Wang B-machine, switching circuit theory), and circuit-related complexity classes (TC, NEXPTIME) alongside learned networks (artificial neural network).

10 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

  • Artificial Neural Network — A learned parameterized network of connected computational units that transforms input signals into outputs through weighted aggregation, activation, and architecture-specific operations.
  • High-Threshold Logic — A diode–transistor logic variant with widely separated input-voltage thresholds for noise tolerance, traded against speed and power.
  • Integrated Injection Logic — A bipolar logic family using a current injector and multiple-collector open-collector inverter, with logic determined by steering injected current through or away from the inverter base.
  • Inverter Logic Gate — A one-input logic gate whose Boolean output is the complement of its input.
  • Moore machine — A finite-state transducer whose output is determined solely by its current state, while input affects output only indirectly by selecting later states.
  • NEXPTIME — The decision-problem class solvable by nondeterministic Turing machines in time exponential in a polynomial of input length.
  • NOR logic — Digital logic implemented with negated-disjunction gates, exploiting NOR's functional completeness to synthesize any Boolean function through NOR-only composition.
  • Switching circuit theory — The mathematical analysis and synthesis of binary switch networks as Boolean combinational functions or sequential state machines.
  • TC (Complexity) — The threshold-circuit complexity hierarchy whose level TC^i contains languages decided by polynomial-size, unbounded-fan-in Boolean circuit families of depth O(log^i n) with threshold or majority gates, and whose union over fixed i is TC.
  • Wang B-machine — A four-instruction, mark-only sequential tape machine—left, right, mark, and conditional jump—that retains Turing-complete computational power without a primitive erase operation.