Uncomputability

Example 1: Deciding self-rejecting TMs

A TM $uc$ that decides if another TM is self-rejecting cannot exist!

Proof

1. Suppose $uc$ exists. So $uc$ is a TM that accepts a TM if it's self-rejecting.
2. Give $uc$ as input to itself. What happens?
   1. If $uc$ rejects itself: Then $uc$ is not self-rejecting (but it did?!)
   2. if $uc$ accepts itself: then $uc$ is self-rejecting (but it already accepted itself!!!)
3. Contradiction. So $uc$ cannot exist

Example 2: Halting problem

A TM $halt$ that decides if another TM halts on a certain input cannot exist!

Proof

1. Suppose $halt$ exists. So $halt$ is a TM that accepts a (TM, $x$) pair if the TM halts on input $x$.
2. Build a TM $m$ that:
   1. takes as input another TM called $Y$
   2. Passes Y and code of Y to $halt$
      1. If Y halts on it's own code, go into an infinite loop
      2. If Y does not halt on it's own code, return
3. Give m as input to itself
   1. m passes m and code of m to halt
      1. if m halts on it's own code, m loops (?!)
      2. if m does not halt on its own code, m returns (?!)
4. Contradiction. so $halt$ cannot exist.

Example 3: Diophantine equation

• Proof is out of scope