Recall that HALT $=\{$M$,$ w$$ : M halts on w$\}.$ Without loss of generality, we

assume that the alphabet of HALT is $\backslash$Sigma :$=\{1,2,...,$ q $1\}$ for some positive integer q$.$ For each nonnegative

integer n in N$,$ we define $$n$$q to be the base$-$q expansion of n$,$ so $$n$$q in $\{0,1,...,$ q $1\}$

$$

$.$ Define

HALT$-$LENGTH $=\{$x in $\{0,1\}$

$$

: $|$x$|$q in HALT$\}.$

$($a$)$ Prove that HALT$-$LENGTH in $/$ P$.$Problem $2(10$ points$).$ Recall that HALT halts on $w.$ Without loss of generality, we

assume that the alphabet of HALT is $$:$=\{1,2,$dots,$q-1\}$ for some positive integer $q.$ For each nonnegative

integer ninN, we define $($:$n$:${)}_q$ to be the base$-q$ expansion of $n,$ so $($:$n$:${)}_{q}in\{0,1,$dots,$q-1{\}}^{**}.$ Define

HALT$-$LENGTH $=\{xin\{0,1{\}}^{**}$:$($:$|x|$:${)}_{q}in$ HALT $\}.$

$($a$)$ Prove that HALT$-$LENGTH $!$inP.

$($b$)$ Prove that HALT$-$LENGTH $in$ PSIZE.