Show that membership in language is undecidable By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable.
REACHABLE-CODE is defined like this:
INSTANCE: A source code S, a number n of a line in S. QUESTION: Is there an input I for S such that the run of S on I will reach the code on line n?
 A: Equivalently, consider the set of all unary partial recursive functions $f_x$ with Gödel number $x$, where $f_x(y)=0$ for each $y$ in the domain of $f_x$. The corresponding set of Gödel numbers is a proper subset of the set of natural numbers and so the set is undecidable by the Thm of Rice. 
A: Okay, consider the set $C=\{x\in\mathbb N_0\mid \phi_x=c_0\}$, where $\phi_x$ is the unary partial recursive function with Gödel number $x$ and $c_0$ is the unary zero-function. 
Claim that $C$ is undecidable. 
Indeed, define $f:\mathbb N_0^2\rightarrow\mathbb N_0$ by $f(x,y)=0$ if $x\in\rm{dom}\;\phi_x$, and $f(x,y)$ undefined otherwise. This function is partial recursive, since it can be written as $f(x,y)= 0\cdot\phi_x(x)$ (or  use the universal function for unary partial recursive functions; i.e. let $\psi$ be a universal function for monadic partial recursive functions, i.e., $\psi$ is partial recursive with $\psi(x,y)=\phi_x(y)$ for all $x,y$. Then $f(x,y)=0\cdot\psi(x,x)$). By the smn theorem, there is a unary computable (prim. rec.) function $s$ such that $f(x,y)=\phi_{s(x)}(y)$. 
Now consider two cases:
First, let $x\in{\rm dom}\;\phi_x$. Then $f(x,y)=0$ for all $y$. Thus $\phi_{s(x)}(y) = c_0(y)$ for all $y$ and so $s(x)\in C$.
Second, let $x\not\in{\rm dom}\;\phi_x$. Then $f(x,y)$ is undefined for all $y$. Thus $\phi_{s(x)}(y)$ is undefined for all $y$ and so $s(x)\not\in C$.
Consequently, the computable function $s$ yields a reduction of the undecidable set $H'=\{x\in\mathbb N_0\mid x\in{\rm dom}\;\phi_x\}$ to the set $C$. 
Note that the set $H'$ is a subset of the ''halting problem'' $H=\{(x,y)\mid y\in{\rm dom}\;\phi_x\}$.
A: Suppose membership of $A$ were decidable. Consider the program $B_2$ that loops on every input. We can now check if a given program $B_1$ halts on some given input $y$ by modifying it to $B'_1$ which behaves as follows:

On input $x$: If $x \neq y$ then loop else simulate $B_1$ on input y$

We have that $(B'_1,B_2) \notin A$ if and only if $B_1$ halts on input $y$. So if we could check membership of $A$, the Halting Problem would be decidable.
