Computation underlies the organization of cells into higher-order structures; for example, during development or the spatial association of bacteria in a biofilm. Each cell performs a simple computational operation, but when combined with cell-cell communication, intricate patterns emerge. Here, we study this process by combining a simple genetic circuit with quorum sensing in order to produce more complex computations in space. A simple NOR gate is constructed by arranging two tandem promoters that function as inputs to drive the transcription of a repressor. The repressor inactivates a promoter that serves as the output. Individual colonies of E. coli carry the same NOR gate, but the inputs and outputs are wired to different orthogonal quorum sensing “sender” and “receiver” devices. The quorum molecules form the wires between gates. By arranging the colonies in different spatial configurations, all possible 2-input gates are produced, including the difficult XOR and EQUALS functions. The response is strong and robust, with 5- to >300-fold changes between the ON and OFF states. This work helps elucidate the design rules by which simple logic can be harnessed to produce diverse and complex calculations by rewiring communication between cells.