# P/Poly class - undecidable lanauge

I didn't understand some things about $P/POLY$ class, and I will be thankful if you could help me. as I learned in class,

a turing machine M accepts language L with advice ${a_n}$ if: M(x,$a_|x|$ ) = 1 <=> x in L

1. Does it mean that M with the advice decides L (halts on every input)? or recognizes L? (accept every x in L but may not halt on x that is not in L)

Generally, if a language L is in P it means that there is polynomial time machine that decides it right? I feel like it really confused me.

then we defined: $P/POLY$ = union of (DTIME($n^{k1}), n^{k2})$ on every $k1,k2$ in $N$ .

we proved in class that there is a unary language which is undecidable, and that every unary language is in $P/1$. that means that there is language in $P/1$ which is undecidable.

1. I don't understand it because $P/1$ is in $P/POLY$ . as I understand by the definition, there is poly time machine that decides it.. so what do I get wrong?

if $L\in P/poly$ then there is a machine that decides any input $x$, given the advice $a_{|x|}$.
However, if the advice is not given, maybe no machine can decide $L$. This is what happens in the unary case. Note that the machine doesn't know the advice and cannot compute it, i.e., the set of advices (for a specific $L$) may be an undecidable language.
On the other hand, if someone gives you this (possibly undecidable) set, you have more power at hands. Similarly, if you can compute this set (for a certain $L$), say get $a_n$ in $f(n)$ time, then $L$ clearly belongs to $DTIME(poly(f(n)))$.
• exactly because the "advice" there is undecidable. The advice is still 1 if x is in $L$ and 0 otherwise, but there is no TM that can compute this advice (=undecidable). – Ran G. Jul 20 '15 at 12:17