# Why is UHALT in P/Poly?

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!

• In (3), you probably wanted to write that HALT (or UHALT) is clearly not in P. – Emil Jeřábek supports Monica Mar 3 '11 at 11:25
• @Emil Jerabek: Good catch. Typo fixed. Thanks! – LowerBounds Mar 3 '11 at 15:15

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}$$