# Difference between a circuit and a normal function

I've seen the word circuit used in many crypto contexts (for example, regarding FHE in this pdf). I've always thought of a circuit as another word for a program or function. But is there a difference - i.e., is there something that a standard function can do that a circuit can't?

• By "normal function" do you mean the normal mathematical definition of a function or something else?
– otus
Jul 15, 2016 at 8:30
• Not a mathematical function in the strict sense. I mean a computer program with inputs and outputs Jul 15, 2016 at 9:00
• I have a sub-question as well: If circuits and computer programs are equivalent, then how can we convert a given program into a circuit? Does there exist an algorithm to do so?
– sun
Jul 16, 2016 at 3:36

A circuit is a representation of a (computable) function. There are many other ways to represent a function (mathematical notation, Turing machines, pseudo-code, etc.), but for some purposes it happens that circuits are the most convenient one.

• Another (informal) distinction is that circuits as a representation (as opposed to physical circuits) generally have no loops, and are thus analyzable in simpler ways, e.g. circuit depth.
– orlp
Jul 15, 2016 at 11:23
• I have a sub-question as well: If circuits and computer programs are equivalent, then how can we convert a given program into a circuit? Does there exist an algorithm to do so?
– sun
Jul 16, 2016 at 10:30
• @Itachi How do you define "computer program"? For example a C program is compiled to machine instructions, which are fairly easy to "translate" to a circuit. Jul 16, 2016 at 10:31
• @Itachi By the way, the source code distribution for the Pinocchio verifiable computing protocol includes a compiler to compile a program written in a subset of C to an arithmetic circuit. vc.codeplex.com Jul 16, 2016 at 10:59
• I'll ask my doubt as an example: How to convert a C program with a while loop (which loops x number of times, where x an input to the program) into a circuit (whose structure is independent of the input)?
– sun
Jul 16, 2016 at 12:16