-3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Kaveh Apr 26 '13 at 17:40
  • 3
    $\begingroup$ "Circle bit" doesn't make any sense — "bit" is short for "binary digit". Why not just "angle"? $\endgroup$ – Jeffε Apr 26 '13 at 19:43
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 26 '13 at 21:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 27 '13 at 5:31
  • 2
    $\begingroup$ @vzn: Qbits are Quantum superpositions of BInary digITS. $\endgroup$ – Jeffε Apr 27 '13 at 17:07
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? =( $\endgroup$ – vzn Apr 27 '13 at 15:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 27 '13 at 16:49
  • 5
    $\begingroup$ 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. $\endgroup$ – Jeffε Apr 27 '13 at 17:14
  • 1
    $\begingroup$ Wait... you thought angles had to be integers??? $\endgroup$ – Jeffε Apr 28 '13 at 3:01
  • 2
    $\begingroup$ if the inputs are any arbitrary angle it doesn't make sense anymore to ask what boolean functions these circuits can compute $\endgroup$ – Sasho Nikolov Apr 28 '13 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.