If deemed necessary, reported comments will be removed within 7 - 10 days but usually sooner. Please submit this report ONLY if you STRONGLY believe this needs to be removed. Multiple illegitimate reports slow down the administrative process of removing the actual and more seriously unfavorable content.

Poster Name:
Turing

Poster Message:
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!