# computing with gates on polar coordinates, functionally complete wrt boolean functions?

this question is inspired by a particular somewhat "natural" physical system specifically constructed to mimic another complex highly-studied physical computing system. (some may astutely guess at least half of this analogy correctly; the full details are involved but more details will be given if there is significant interest.)

consider a computing system of "c-bits" or "circle-bits" and a single gate that operates/combines them. a circle-bit is a single polar coordinate on the unit circle, eg denoted by a number in the range 0°-360° (degrees).

the sole gate operator $z=mid(x,y)$ takes two c-bits $x,y$ as input and computes as output $z$ the c-bit that is the midpoint of the arc between them.

now consider a c-bit circuit composed of inputs, "mid" gates, and a single output.

the question is related to whether the c-bit circuit can convert binary functions with a binary-to-cbit adapter/converter on the binary input wires, and a cbit-to-binary adapter/converter on a single final c-bit output gate. call this overall construction a "c-bit sandwich circuit".

• the binary-to-cbit adapter/converter is just a mapping of 0,1 bits (false,true) onto 0°,180° respectively.
• a single output function (ie cbit-to-binary adapter/converter) $test_{a,b}(x)$ on a c-bit $x$ is given where $a,b$ are c-bit constants and it returns true iff $a \leq x \leq b$.
• is the c-bit sandwich circuit functionally complete for boolean functions, or not? ie can it compute all boolean functions?
• if not, what is a characterization of the functions it can compute?
• looking for any refs to the "nearest" problem considered in published literature elsewhere.

(there are natural generalizations of this problem & may ask about those depending on response.)

note: know there is ambiguity on the c-bit gate where the c-bits are 180° apart. the computing scheme solution may choose a consistent rule in that case.

• What have you tried? E.g. have you tried computing AND and OR and NOT with your circuits? What do you know about what they can compute? Apr 26 '13 at 17:40
• "Circle bit" doesn't make any sense — "bit" is short for "binary digit". Why not just "angle"? Apr 26 '13 at 19:43
• this whole c-bit, polar coordinates, etc. business is absolutely unnecessary. all you are saying is: given binary inputs and a circuit whose only gate is $(a+b)/2$, and a single range gate at the top, what can the circuit compute. Apr 26 '13 at 21:39
• the wrap-around does not matter because when the inputs are all either 0 or 180, any intermediate value will be on the arc between 0 and 180 and wrap-around never occurs. that is why i said that your setup is equivalent to the $[0, 1]$ case. Apr 27 '13 at 5:31
• @vzn: Qbits are Quantum superpositions of BInary digITS. Apr 27 '13 at 17:07

First: all your inputs are either 0 or 180, and the midpoint gate always gives a point on the arc between its two inputs. So any intermediate value stays on the arc between 0 and 180, there is never wrap-around, and we may just assume that each input is a bit and the gates return $(a+b)/2$. Then there is a gate at the top that tests whether its input is in a range $[c, d]$.
Notice that any such circuit recognizes a set of the form $S(a, c, d)=\{x: c \leq \langle a, x\rangle \leq d\}$ where $a$ is $n$-dimensional and $c$ and $d$ are scalar constants. The way to see that is that the input to the top gate is a linear function of the input. In fact your setup is significantly more restricted, but nevermind that. The family of sets $S(a, c, d)$ has VC-dimension at most $2n+2$: halfspaces have VC-dimension $n+1$, and taking all pairwise intersections of sets in family can at most double the VC-dimension. Therefore the family of sets computed by your circuits cannot possibly shatter all $2^n$ possible binary inputs, even for $n=4$. There are boolean functions on $4$ bits that a circuit of this type does not compute.