decidability of Lacc

In short, if a program that decided L_acc exists, we can construct a program that rejects its own source code if and only if it accepts its own source code, forcing a contradiction.

Recall that if C is the language that decides L_acc, C is this magic thing that tells you if any program accepts any input, accepting (program M, input x) if the program M accepts input x.

We force the contradiction by defining a program D that:
1. Takes the source code of any program M as input
2. Runs C, the program C that decides L_acc, on <M>.
3. Asks C if M takes its own source code <M> as input, and
4. Accepts if C rejects and rejects if C accepts.

So if D takes its own source code <D> as input, D = M:
Case 1: Assume D accepts its own source code <D>. Then, C says D does take its own source code <D> as input, and so accepts (<D>, <D>). But then, D does the opposite of C and rejects <D>
Case 2: Assume D rejects <D>. Then, C rejects (<D>, <D>), and D accepts <D>.

So D accepts <D> if and only if D rejects <D>. Contradiction. \n\n\n\n\nIf you need a detailed explanation, here is one below.

Recall that:
L_acc := { (<M>, x) ; M is a program that accepts x}.
That is, L_acc is the set of all pairs of programs and inputs such that in each pair, the program accepts its input.

Now, L_acc is decidable
<=> Some program, call it C, decides L
<=> Given some program M and some input x, C takes these as input, and accepts if program M accepts and rejects if program M rejects

Here's the clever part.
1. Let D be a new program that takes in the source code of the original program, M.
2. D runs C on the original program M, asking if M accepts its own source code
3. D rejects if C accepts, and accepts if C rejects

D halts as C always halts.
M accepts <M> => C accepts (<M>, <M>) => D rejects <M>
M rejects <M> => C rejects (<M>, <M>) => D accepts <M>

Take D = M. That is, run D on itself. Then,
D accepts <D> <=> C accepts (<D>, <D>) <=> D rejects D>
Contradiction!