Possible Proof of Non Recursively Enumerablity of Universality

proof.txt

Diag = {M | M does not accept M}
HP = {(M, x) | M accepts x}
Co-Univ = {M | there exists w such that M does not accept w}

Claim: HP <= Diag <= Co-Univ

Reduction from HP to Diag

Say HP has input (M, x)
Design Turing Machine N such that:
  N on input y:
    Simulate M on x
    If simulation halts,
      accept
Pass N to Diag Decider.
If Diag Decider says yes:
  reject
Otherwise
  accept

End Reduction

Reduction from Diag to Co-Univ

Say Diag has input M
Design Turing Machine N such that:
  N on input y:
    Checks if y == M
    if not:
      accept
    otherwise:
      simulate M on M
      if simulation accepts,
        accept
Pass N to Co-Univ Decider.
If Co-Univ Decider says yes:
  accept
Otherwise
  reject

End Reduction

proof2.txt

co-HP = {(M, x) | M does not halt on x}
Univ = {M | for all w . M accepts w}

Claim: co-HP <= Univ

Reduction from co-HP to Univ

Let (M, x) be the input to co-HP
Design Turing Machine N such that:
  On input y:
    Simulate M on x upto |y| steps
    If the simulation does not accept,
      accept
Pass N to Univ decider.
If Univ decider says yes,
  accept


End Reduction