<p>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]$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-04-27T15:40:58.703Z
interesting. not sure about this yet. wonder if its too limited. the sentence on "ambiguity" in the question is suggesting that different rules are possible for the 180/0 case other than choosing only 90 as the midpoint. some rule could also allow either 270 or 90 depending on some other criteria [as long as its somehow consistent & not arbitrary. although am thinking a random 50% probability case might be allowed too]. also, constants in the circuit might be another consideration. but the VC-dimension idea for analysis is a nice angle =) thx ... but ps why answer without upvoting? =(
vzn
CC BY-SA 3.0
2013-04-27T15:47:56.840Z
also was initially wondering if there is some connection to monotone boolean functions & this answer seems like it hints at that.... there is a sense in which monotone boolean functions can represent full boolean functions.... also based on the linear algebra wonder if there is any relation to [perceptrons](http://en.wikipedia.org/wiki/Perceptron)...
vzn
CC BY-SA 3.0
2013-04-27T16:49:03.453Z
I think the limitations are similar to perceptrons. you could add constants, allow addition (and keep everything mod 1), but i think this is still going to be a linear circuit at heart, and the VC dimension argument can be made to work. have not fully checked that.
Sasho Nikolov
CC BY-SA 3.0
2013-04-27T17:14:24.700Z
I interpreted the midpoint operator differently: mid(a,b) returns the midpoint of the _counterclockwise_ arc from a to b.  Then mid(0,180)=90, but mid(180,0)=270.  But a similar VC-dimension argument should still work for this interpretation.
Jeffε
CC BY-SA 3.0
2013-04-27T18:26:48.663Z
oops! suddenly realizing now I made a mistake in the problem formulation above. something closer to the original intention would be to have continuous inputs that are not at all restricted to 0,180 and could be any degree. wouldnt this change the analysis substantially? however, chging/editing this current question would probably not work & there is not much support for a new question. however would very much like to continue the discussion in [chat](http://chat.stackexchange.com/rooms/2710/computer-science) for anyone interested. think some may be intrigued by its connections to qm computing.
vzn
CC BY-SA 3.0
2013-04-28T03:01:07.227Z
Wait... you thought angles had to be integers???
Jeffε
CC BY-SA 3.0
2013-04-28T04:45:39.703Z
if the inputs are any arbitrary angle it doesn't make sense anymore to ask what boolean functions these circuits can compute
Sasho Nikolov
CC BY-SA 3.0
2013-04-27T05:49:46.587Z
2013-04-27T17:28:03.417Z
2013-04-27T17:28:03.417Z
Sasho Nikolov
<p>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.)</p>

<p>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).</p>

<p>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.</p>

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

<p>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".</p>

<ul>
<li>the binary-to-cbit adapter/converter is just a mapping of 0,1 bits (false,true) onto 0°,180° respectively.</li>
<li>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$.</li>
</ul>

<blockquote>
  <ul>
  <li>is the c-bit sandwich circuit functionally complete for boolean functions, or not? ie can it compute all boolean functions?</li>
  <li>if not, what is a characterization of the functions it can compute?</li>
  <li>looking for any refs to the "nearest" problem considered in published literature elsewhere.</li>
  </ul>
</blockquote>

<p>(there are natural generalizations of this problem &amp; may ask about those depending on response.)</p>

<p>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. </p>

CC BY-SA 3.0
2013-04-26T17:40:25.413Z
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
CC BY-SA 3.0
2013-04-26T19:43:57.943Z
"Circle bit" doesn't make any sense — "bit" is short for "**binary** digit".  Why not just "angle"?
Jeffε
CC BY-SA 3.0
2013-04-26T21:39:22.953Z
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
CC BY-SA 3.0
2013-04-26T22:35:10.390Z
@sasho its apparently not exactly the same problem with reals and a $(a+b)/2$ "midpoint" gate although that is very similar, did consider that case. (also a "mid" gate for reals seems not considered anywhere in the literature.) the point with polar coordinates is that the domain "wraps around" and there is no lowest or highest value as there is with reals and it precisely corresponds to the physical setup whereas the reals case does not. as for AND,OR,NOT, the intermediate values of the circuit are not boolean bits (as is done with other boolean-related gates/proofs), so it seems nontrivial.
vzn
CC BY-SA 3.0
2013-04-27T01:33:52.477Z
Sounds like you're thinking about something along the lines quantum circuit gates restricted to real valued entries.
Logan Mayfield
CC BY-SA 3.0
2013-04-27T02:34:38.460Z
@logan nice! close! & an answer to jeffe's complaint. "bit" is an english word that had a meaning prior to the use in computer science. also, jeffe's same argument could be applied to the naming of _qubits_
vzn
CC BY-SA 3.0
2013-04-27T05:31:10.680Z
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
CC BY-SA 3.0
2013-04-27T17:07:58.253Z
@vzn:  Qbits are Quantum superpositions of BInary digITS.
Jeffε
<reference-request><boolean-functions><arithmetic-circuits><natural-computing>
computing with gates on polar coordinates, functionally complete wrt boolean functions?
vzn
# computing with gates on polar coordinates, functionally complete wrt boolean functions?

(Asked by: username_0 on 2013-04-26)

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.

**Tags:** reference-request, boolean-functions, arithmetic-circuits, natural-computing
> **Comments:**
> **username_1**: 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?  
> **username_2**: "Circle bit" doesn't make any sense — "bit" is short for "**binary** digit".  Why not just "angle"?  
> **username_3**: 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.  
> **username_0**: @sasho its apparently not exactly the same problem with reals and a $(a+b)/2$ "midpoint" gate although that is very similar, did consider that case. (also a "mid" gate for reals seems not considered anywhere in the literature.) the point with polar coordinates is that the domain "wraps around" and there is no lowest or highest value as there is with reals and it precisely corresponds to the physical setup whereas the reals case does not. as for AND,OR,NOT, the intermediate values of the circuit are not boolean bits (as is done with other boolean-related gates/proofs), so it seems nontrivial.  
> **username_4**: Sounds like you're thinking about something along the lines quantum circuit gates restricted to real valued entries.  
> **username_0**: @logan nice! close! & an answer to jeffe's complaint. "bit" is an english word that had a meaning prior to the use in computer science. also, jeffe's same argument could be applied to the naming of _qubits_  
> **username_3**: 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.  
> **username_2**: @vzn:  Qbits are Quantum superpositions of BInary digITS.  

---

## 1 answers

### Answer by username_3 on 2013-04-27. Score: 6

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.

> **Comments:**
> **username_0**: interesting. not sure about this yet. wonder if its too limited. the sentence on "ambiguity" in the question is suggesting that different rules are possible for the 180/0 case other than choosing only 90 as the midpoint. some rule could also allow either 270 or 90 depending on some other criteria [as long as its somehow consistent & not arbitrary. although am thinking a random 50% probability case might be allowed too]. also, constants in the circuit might be another consideration. but the VC-dimension idea for analysis is a nice angle =) thx ... but ps why answer without upvoting? =(  
> **username_0**: also was initially wondering if there is some connection to monotone boolean functions & this answer seems like it hints at that.... there is a sense in which monotone boolean functions can represent full boolean functions.... also based on the linear algebra wonder if there is any relation to [perceptrons](http://en.wikipedia.org/wiki/Perceptron)...  
> **username_3**: I think the limitations are similar to perceptrons. you could add constants, allow addition (and keep everything mod 1), but i think this is still going to be a linear circuit at heart, and the VC dimension argument can be made to work. have not fully checked that.  
> **username_2**: I interpreted the midpoint operator differently: mid(a,b) returns the midpoint of the _counterclockwise_ arc from a to b.  Then mid(0,180)=90, but mid(180,0)=270.  But a similar VC-dimension argument should still work for this interpretation.  
> **username_0**: oops! suddenly realizing now I made a mistake in the problem formulation above. something closer to the original intention would be to have continuous inputs that are not at all restricted to 0,180 and could be any degree. wouldnt this change the analysis substantially? however, chging/editing this current question would probably not work & there is not much support for a new question. however would very much like to continue the discussion in [chat](http://chat.stackexchange.com/rooms/2710/computer-science) for anyone interested. think some may be intrigued by its connections to qm computing.  
> **username_2**: Wait... you thought angles had to be integers???  
> **username_3**: if the inputs are any arbitrary angle it doesn't make sense anymore to ask what boolean functions these circuits can compute  

---

