My textbook claims: P \subset P/Poly, and that this is proper.


It claims that all unary languages are in P/Poly, and then goes on to claim that UHALT = {1^n | n encodes (M,x) s.t. M halts on x } is in P/Poly, but not in P.


I understand the following thing:



```
(1) HALT can not be calculated by any TM
(2) UHALT can not be calculated by any TM
(3) Clearly, HALT \not\in P
(4) P/Poly is non-uniform; i.e. we can have a different
    circuit for every input length.

```

What I don't understand is why (4) implies that UHALT \in P/Poly.


Thanks!



Why is UHALT in P/Poly?
Fix $n$, we want to construct a circuit $C\_n$ deciding UHALT on inputs $w$ of length $n$. Now, either $n\notin\mathrm{HALT}$, in which case $C\_n$ is the constant $0$ circuit, or $n\in\mathrm{HALT}$, in which case $C\_n$ is


$$C\_n(w)=\begin{cases}1&\text{if }w\text{ is a string of 1s,}\\0&\text{otherwise,}\end{cases}$$


which can be clearly implemented by a linear-size circuit.


