Ok, I will do it.

On 11/23/15, Laxmi Gewali <laxmi.gewali@unlv.edu> wrote:
> Larry,
>
> I will be out of town on Monday Nov 30
> Could you teach for me CS 456 class?
> (Time and Class Room: Monday 2:30 pm - 3:45 pm - TBE B176)
>
> The topics to cover:
>
>    - Recursively enumerable languages
>    - Church Thesis
>    - Turing Thesis
>    - Languages that are not recursively enumerable (diagonalization method)
>
> Thanks
>
> - Laxmi
>

I did not discuss Turing Machines.  They told me they had already done that.
I told them that we can think of "machines" and "programs" as the same thing.
(This requires the Church-Turing Thesis.)

Here is what I taught them.

1.  A function is "recursive" = "computable" if some machine computes it,
equivalently, if there is a program that computes it.

2.  A language is "recursive" or "decidable" if there is some machine (program)
P that decides it, meaning that, given an input string w, P halts and outputs
either "1" (yes) if w is in M, and "0" (no) if w is not in M.

3.  A program P "accepts" a language if, given an input string w, P halts
and says "1" (yes) if w in L, and where P does not halt if w is not in L.

4.  Trivially, if L is decided by some program then L is accepted by some
other program.

5.  Every language is enumerable = countable.  But that doesn't mean that you
can compute the enumeration.

6.  A language L is "recursively enumerable" = R.E. if there is a machine that
enumerates L.

7.  Theorem (I gave no proof) L is R.E. if and only if there is some machine
that accepts L.

8.  Theorem (I gave no proof) L is decidable if and only if there is some
machine that enumerates L in canonical order.

9.  Pick a programming language, say Pascal.  Let L be the language consisting
of all Pascal programs P such that P does not accept itself.

  I proved that L is not accepted by any machine.

  Suppose P is a Pascal program that accepts L.  Is P a member of L?

  If P is a member of L, then P does not accept P, which implies that
  P is not a member of L.

  If P is not a member of L, then P accepts P, which implies that
  P is a member of L.

  This is clearly impossible, and thus P does not exist, that is, L is not
  accepted by any machine, and thus L is not R.E.
  Trivially, L is not decidable.