Re: Debugging Theory

sol! (ilias kastanas 08-14-90)
19 Sep 1996 00:17:47 -0400

          From comp.compilers

Related articles
Debugging Theory (1996-09-15)
Re: Debugging Theory (1996-09-16)
Re: Debugging Theory (1996-09-17)
Re: Debugging Theory sol! (1996-09-19)
Re: Debugging Theory (John Robbins) (1996-09-19)
Re: Debugging Theory (Hans Huttel) (1996-09-22)
Re: Debugging Theory (Hans Huttel) (1996-09-22)
Re: Debugging Theory (1996-09-22)
Re: Debugging Theory (1996-09-23)
Re: Debugging Theory (Jeremy Carroll) (1996-09-25)
[2 later articles]
| List of all articles for this month |

From: sol! (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 ( 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.

[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.