Re: What good is halting prob?

[RTOAL@lmumail.lmu.edu (Ray Toal)]

In article <3n3b82$ild@hermes.unt.edu> srt@zaphod.csci.unt.edu (Steve Tate) writes:

>I have seen concepts from the theory of computing (both computability
>and complexity) presented in many different ways, including a
>presentation using register machines made by a famous
>mathematician/logician/recursion theorist. 

Here's one that just uses Ada 95 (sorry if this is common knowledge):

Given:

  type Program is access procedure;

We want to write:

  function Halts (P: Program) return Boolean;

But we cannot because we can write

  procedure Nasty is
  begin
    if Halts (Nasty'Access) then
      loop
        null;
      end loop;
    end if;
  end Nasty;

which halts if and only if it doesn't.

I've found this an effective way to present the halting problem to
students who have not yet seen Turing Machines.  (Of course, before
Ada 95, I had to show them in C++ due to the lack of subprograms
as parameters in Ada 83.)

Ray Toal