I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me.I would like to know if Boolean circuits are what I would call universal. By this I mean that, given an infinite number of NAND gates and wires, could I solve any problem on any input?Equivalently (I think) could I simulate any given instance of a universal Turing machine using some particular Boolean circuit? By 'a given instance' I mean that the action table and input tape are set in stone, so we know exactly what process that our Boolean circuit is to simulate before we start wiring all the NAND's together.
Are Boolean circuits 'universal'
cc.complexity theory;circuit complexity;boolean functions