1
$\begingroup$

If a function f has a while loop or for loop, can I compile this function into an acyclic boolean circuit that ensures that each gate is topologically ordered, i.e. there is no feedback? If so, how exactly is that done, by loop expansion? And if compiling the function as a cyclic boolean circuit is allowed, does it simplify the circuit structure?

I would appreciate your answer. Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ Whether that's your question or an assignment (please indicate), it's an interesting one. Is the context "advanced compilers" or computability? $\endgroup$
    – greybeard
    Mar 13 at 7:35
  • $\begingroup$ I have updated the question, thanks for the reminder. @greybeard $\endgroup$
    – Emison Lu
    Mar 13 at 8:17

1 Answer 1

Reset to default
0
$\begingroup$

If your circuit can contain registers (or some other form of memory or state) (e.g., sequential logic), then yes, you can. You store the value of all variables in the registers, and you build a circuit that computes the next value of those variables after one iteration of the loop, and then the circuit runs over and over again.

If your circuit cannot contain registers or state, but only logic gates (i.e., combinational logic), then no, you cannot.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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