From: Rick Bradley <rick@...>
Date: 2002-05-15T04:36:03+09:00
Subject: Halting Problem (was "Re: code coverage tool?")

* Patrick May (patrick-may@monmouth.com) [020514 13:54]:
> Do you have any links to more information about the issues in doing
> coverage analysis?  What is The Halting Problem?

I wish I had more information to offer regarding coverage analysis, but
I don't really have much expertise in building tools for that.  I've
been around folks (during my short stay in research-land) who were
heavily into static analysis, provable languages, etc., but their
fire never really caught under me.


The Halting Problem is simply the problem of determining whether a
Universal Turing Machine will reach a "halt" state, given, as input, the
encoding for another Turing Machine and an input for that second Turing
Machine.  This problem has been shown to be undecidable. [0]

The Halting Problem has some interesting things in common with Godel's
Incompleteness Theorem, and from a certain point of view the proof
methods are fairly similar.  Given the appropriate theoretical framework
(rigorous constructions of computing devices, such as Universal Turing
Machines; coupled with Church's Thesis for applicability to generalized
computation) the proof of the Halting Problem's decidability is a fairly
straightforward diagonalization proof.

A couple of the practical implications of the Halting Problem are
knowing that we can't build a general infinite loop detector, nor can we
write a program to predict what output any program will produce on a
given input.

This isn't to say that we can't do various useful types of analysis
(because clearly there's a thriving industry doing just that, and which
isn't for the most part engaged in charlatanism) -- we can.  It's just
that there are real limits to what we can do.  When we attempt to use
static analysis to determine whether an application is going to do
such and such when running we're often on the road to trouble.

All of this is fairly hand-waving because there's a large body of
literature on this and closely related topics, often labelled as
"Computability Theory", which most people find highly uninteresting [1].


[0] Which is a way of saying that for an infinite number of instances of
    the problem set we cannot arrive at a conclusion as to the outcome.
    This is much worse than saying "it's hard" or even "we don't know
    how to solve this" -- it's essentially saying "We've proven that we
    cannot solve this general problem."

[1] When I was in graduate school for Computer Science a senior
    professor in the department announced his intent to teach a course
    on Computability the following semester if there was *any* interest.
    I was one of three people who signed up for the course.  One of the
    others dropped out a few weeks in.  This in a respected department
    with a sizable graduate community and a number of strong
    theoreticians.  The course was one of the most challenging I've had
    to date.  Were I a powerful computer science despot I would require
    that a solid course in computability be a prerequisite for any
    computer science degree.

Rick
-- 
 http://www.rickbradley.com    MUPRN: 367    (84 F)
                       |  that I go to since
   random email haiku  |  it is part of NASA and
                       |  there is a firewall.