Re: Debugging Theory

sol!ikastan@uunet.uu.net (ilias kastanas 08-14-90)
19 Sep 1996 00:17:47 -0400

          From comp.compilers

Related articles
Debugging Theory rfraer@sophia.inria.fr (1996-09-15)
Re: Debugging Theory dick@silicon.csci.csusb.edu (1996-09-16)
Re: Debugging Theory jacob@jacob.remcomp.fr (1996-09-17)
Re: Debugging Theory sol!ikastan@uunet.uu.net (1996-09-19)
Re: Debugging Theory johnr@numega.com (John Robbins) (1996-09-19)
Re: Debugging Theory hans@iesd.auc.dk (Hans Huttel) (1996-09-22)
Re: Debugging Theory hans@iesd.auc.dk (Hans Huttel) (1996-09-22)
Re: Debugging Theory ikastan@alumnae.caltech.edu (1996-09-22)
Re: Debugging Theory rtf@world.std.com (1996-09-23)
Re: Debugging Theory jjc@hplb.hpl.hp.com (Jeremy Carroll) (1996-09-25)
[2 later articles]
| List of all articles for this month |

From: sol!ikastan@uunet.uu.net (ilias kastanas 08-14-90)
Newsgroups: comp.theory,comp.compilers
Date: 19 Sep 1996 00:17:47 -0400
Organization: Information Resources and Technology
Distribution: inet
Expires: September 28, 1996
References: 96-09-051 96-09-076
Keywords: debug, theory

@Ranan Fraer (rfraer@sophia.inria.fr) wrote:
@: can anyone please recommend me some good books/papers on debugging theory ?


Theory's edict is "you can't"; and practice advises: "don't"!


In full generality theory has results you may be better off not
      knowing. Let Ts be Turing Machines/programs/algorithms/... Then
      a) the question "Do T and T' compute the same (partial) function?"
            is undecidable
      b) the problem "Given T, find a T' that computes a different function"
            is unsolvable.


So, no algorithm can tell whether two arbitrary TMs are "the same",
      or, given one TM, produce a "different" one; i.e., you cannot tell whether
      a program does what is wanted... and moreover you cannot change it anyway!
      (At 3 a.m. one might need some wry amusement).


Fortunately in practice we don't face the full situation; still, such
      results support the familiar view: focus on avoiding debugging. We cut it
      down by careful design, good style, formal correctness methods if applica-
      ble, and so on. And an attitude of looking for more.


Ilias
[I don't think that was quite the question he asked. There has been some
interesting work over the years in identifying and classifying bugs. -John]




--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.