Turing machine and boolean circuits

Question

As an example of languages that are in P/poly is the UHALT Problem :

UHALT = { 1^n: n's binary expansion encodes a pair such that M halts on input x}

We can create a boolean circuit of just AND gates. However, we can create it only for a fixed 'n', not for all n's ...

My question is : when we consider a language like the UHALD problem, do we consider all of the 'n' possible values ,ie for every 'n' we have a different language? or for every n we have a different language ?

In Turing-machines, i think we can loop, but in boolean circuits.. i dont think we can, thus the impossibility (in my point of view) of making, for example, a circuit for the UHALT problem for every n there is.

Answer 1

The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a family of circuits does, which is an infinite sequence $(C_n)_{n \in \mathbb{N}_0}$, $C_n$ being the circuit for inputs of length $n$.

Moreover, Boolean circuits in general are intrinsically non-uniform models of computation anyway since the input gates count as part of the circuit. If you insist on an arbitrary number of input gates, then you necessarily end up with a circuit of infinite size (which is a no-no). (In fact, this is why we use the notion of constructability to obtain uniform circuits; any sort of uniformity must be extrinsic to the circuit.)