# 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? – Kaveh Apr 26 '13 at 17:40
• "Circle bit" doesn't make any sense — "bit" is short for "binary digit". Why not just "angle"? – Jeffε 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. – Sasho Nikolov 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. – Sasho Nikolov Apr 27 '13 at 5:31
• @vzn: Qbits are Quantum superpositions of BInary digITS. – Jeffε 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.