

Senior Member
Gödelian Quality Assurance – A Thematic Interlude
I have been looking at the idea of getting people to think of subtle testing, coverage, analysis, and QA related concepts in various ways. One way, as I have often touted on these boards, is via the use of puzzles. What I want to do here is present a puzzle thread that will perhaps establish a basis for this, if you will, as well as establish a basis for my longheld contention that QA is undergirded by a strict formalistic logic. Each post in this thread will contain one puzzle of a given theme (of which there are three). Each puzzle will have exercises. There is no need for everyone to post their solutions here. I want this to be a challenge for people but not one where people feel superior (because they know the answers and post them) or inferior (because they do not know the answers and cannot post them).
The structure will be three themes. The first theme (A Gödelian System) will have two puzzles. The second theme (Doubly Gödelian Systems) will have also have two puzzles. The third, and final, theme (Gödel's Complete System) will have just one puzzle. To keep extraneous posts from being inserted, I have added all the themes and puzzles at one time so this is a large thread but probably the first "thematic" thread on QA Forums.
The point of this is to get people thinking about these things. At first it may seem as if this has little to no bearing on quality and/or testing topics. Look a little deeper and you will see that, in fact, it does. Part of the challenge of this interlude is for people to understand where the relevance comes in. I will give a hint at the bottom of each post for how you might think of the relevance.
In my opinion, this is sort of an I.Q. test for QA and test professionals. It does not test your ability to memorize. It tests your ability to think. It is tests your ability to refer back to information you were previously given and apply that information to different situations. It also tests your ability to think abstractly. Now, I will not kid myself: I know this thread will have a limited viewing audience and an even more limited reading audience. However, for those that try it out: kudos to you. Read this not so much with an idea of responding to it, but with the idea of reading it and, each time, thinking about it. This is not a sound bite. It is a thought experiment.
The first post is right below ...

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Theme 1: A Gödelian System
Puzzle 1: The System G</center>
A certain system under test, G, is composed exclusively by components that never fail, called KPassers, and components that always fail, called KFailers. Some of the KPassers are called established KPassers, and these are KPassers that have "proved themselves", so to speak, in that they have never failed. There are also certain KFailers called established KFailers, which have "proved themselves" in terms of always failing.
Now, the components of this system can be placed into various logically related groupings. It is possible that a component may belong to more than one group. Given any component X and any group C, either X claims to be a member of C or claims to not be a member of C. By "claims" I simply mean the component has a certain means of indicating whether it is or is not a member of group C. KPassers always make truthful claims of membership (i.e., correctly report their status) and KFailers always make untruthful claims of membership (i.e., incorrectly report their status).
We, as QA professionals, are given four conditions (constraints) that apply to the system under test.
<UL TYPE=SQUARE><LI><font color="#ff0000">E1</font>: The set of all KPassers forms a group.<LI><font color="#ff0000">E2</font>: The set of all KFailers forms a group.<LI><font color="#ff0000">C</font>: Given any group C, the set of all components in the system that are not members of C form a group of their own. (This group is called the complement of C and is denoted by C.)<LI><font color="#ff0000">G</font>: Given any group C, there is at least one component in the system that claims to be a member of C. (Of course, that claim might be false, as that component might be a KFailer.)[/list]
Exercise 1: Prove that there is at least one unestablished KPasser in the system.
Exercise 2: Prove that there is at least one unestablished KFailer in the system.
<font color="#0000ff">HINT:</font> If this seems needlessly complex, and perhaps even bordering on asinine, think about what this is asking you when you abstract away the puzzle elements. You are being asked to see if there is a component that never fails but has not been proven (i.e., tested) as such and you are being asked to see if there is a component in the system that always fails but has not yet been found. That is very relevant to the notion of testing components and doing coverage analysis. Think about how the notion of "group" might apply to related areas of functionality or areas of an application that you feel more or less confident in. Also think about how "always passes" and "always fails" could be substituted for things like "does not have hidden faults" and "does have hidden faults". You could also reformulate the wording a little and have things like "has been tested" and "has not been tested".
When you are done with those two exercises, think of these as a bonus to test your skills:
Exercise 3: Do the set of all KFailers in the system form a group?
Exercise 4: Do the set of all KPassers in the system form a group?
<font color="#0000ff">HINT:</font> Why these exercises? It shows you how you might logically group things in your mind and how you are able to consider things part of one group or, perhaps, to recognize that they are not part of one group. Can you think of how that might be relevant to what you group in some of your QA or testrelated tasks?


Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Puzzle 2: General Gödelian Systems</center>
This is still part of Theme 1 and in this puzzle consider an arbitrary KPasser/KFailer system under test with groups, similar to that from Puzzle 1. We will say that this system is a Gödelian system if condition <font color="#ff0000">G</font>, from Puzzle 1, holds. In other words, the system is Gödelian if for every group C, there is at least one component that claims to be part of that group.
Now consider an intrepid QA professional contracting to a new organization who wants to find out if the system they will be working with there is Gödelian. The QA professional manages to find out some information.
First, it is determined that each group is named after a component and each component has a group named after it. Also, a component is not necessarily a member of the group named after itself. However, if the component is a member of the group named after itself, it is called a sociable component. If the component is not a member of the group named after itself, then it is called an unsociable component. Finally, a component X is called a friend of a component Y if X claims that Y is sociable.
Now, our intrepid QA professional still did not know whether or not he was working with a Gödelian system but then he found out that the system satisfied a certain condition (constraint):
<UL TYPE=SQUARE><LI><font color="#ff0000">H</font>: For any group C, there is another group D such that every component of D has at least one friend in C, and every component that is not part of D has at least one friend who is not part of C.[/list]
From this condition, the QA professional could easily deduce whether the system was, in fact, Gödelian.
Exercise: What conclusion did the QA professional come to? Is the system Gödelian or not?
<font color="#0000ff">HINT:</font> Note in the above that when I talk about sociable, unsociable, and friends you can relate this to programming constructs, as just one example, that provide, say, public and private interfaces. You can also think of this in terms of group dynamics within an organization, such as teams that do communicate and collaborate and teams that do not. Are you starting to see how the notion of "system" and "component" can be quite broad in these themes?

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Theme 2: Doubly Gödelian Systems
Puzzle 3: The Doubly Gödelian System S</center>
Here we will consider a KPasser/KFailer system under test, S, with groups, similar to that from Puzzle 1 and 2. We will say that any such system is doubly Gödelian if a new condition, <font color="#ff0000">GG</font>, holds. That condition is:
<UL TYPE=SQUARE><LI><font color="#ff0000">GG</font>: Given any two groups C1, C2, there are components A, B such that A claims that B is a member of C1 and B claims that A is a member of C2.[/list]
Now, say a QA professional is working with a doubly Gödelian system S in which conditions <font color="#ff0000">E1</font>, <font color="#ff0000">E2</font>, <font color="#ff0000">C</font>, and <font color="#ff0000">G</font> (from Puzzle 1) all hold.
Exercise 1: Can it be determined whether there is an unestablished KPasser in S? What about an unestablished KFailer?
Exercise 2: Can it be determined whether the KPassers in system S form a group? What about the set of KFailers?
Extra Credit Exercise: Does condition <font color="#ff0000">GG</font> imply condition <font color="#ff0000">G</font>? Does condition <font color="#ff0000">G</font> imply condition <font color="#ff0000">GG</font>? Is a Doubly Gödelian System necessarily a Gödelian system?
<font color="#0000ff">HINT:</font> So what is all this showing? Well, think about what you are being asked to prove and think about what the solution gives you. Think about ending up with something that is true but you cannot prove it to be true. Or think of ending up with something that is false but you cannot disprove it (thus showing that it is false). Could this apply to hidden faults in components? Could this apply to test casing? Can you end up with things that are valid but cannot be proven to be so? Or can you end up with things that are invalid but are incapable of being shown to be invalid? If so, what does this say for estimating? What about for proving the value of something?

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Puzzle 4: The System S<sup>1</sup></center>
In this situation, imagine a QA professional who finds himself working with a doubly Gödelian system S<sup>1</sup>. In this case conditions <font color="#ff0000">E1</font> and <font color="#ff0000">E2</font> (from Puzzle 1) both hold for this system, but it is not known whether condition <font color="#ff0000">C</font> (also from Puzzle 1) holds. (Remember that condition <font color="#ff0000">C</font> is that for any group C, the set of components not in C form a group.)
On the face of it, it seems obvious to our QA professional that it is apparently impossible to prove that there is an unestablished KPasser in system S<sup>1</sup> and it is also apparently impossible to prove that the KPassers do not form a group. It also is apparently impossible to prove that the KFailers do not form a group. However, the QA professional is, in fact, able to prove two aspects of the system. That makes up your exercises.
Exercise 1: Prove that either there is an unestablished KPasser or an unestablished KFailer in the system.
Exercise 2: Prove that it is impossible that both the KPassers form a group and also the KFailers form a group.
<font color="#0000ff">HINT:</font> What this shows is that you will always have some measure of uncertainty in your systems. But what does that mean? How can you apply that? Does this suggest you can measure that uncertainty or at least bound the regions of uncertainty? (But if you can do all that, how uncertain is it really?) Does this suggest that uncertainty, to a large extent, is intrinsic and, if so, how does that affect our planning and estimating? Does this apply to things like inconsistency engineering?

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Theme 3: Gödel's Complete System
Puzzle 5: Is The System Complete?</center>
A QA professional comes across a massive bounded test case document called The Manual of Test Cases. Each page of this document is numbered consecutively and each page has exactly one test case on it. No test case appears on more than one page. Given any test case X, the number of the page on which is written is called the page number of X.
Now, every test case in the document is, of course, either true or false. (Here "true" means valid and "false" means invalid.) Some of the true test cases are selfevident to the QA professional reading the document and he has taken these selfevident truths as axioms of his test strategy. This strategy also contains certain rules of reasoning which enable the QA professional to prove various true test cases from the axioms (i.e., show they are valid) and to disprove various false test cases (i.e., show they are invalid).
The QA professional assures his management that his strategy is correct in the sense that every test case which is provable in the strategy is indeed a true test case, and every test case which is disprovable in the strategy is a false test case. However, the QA professional is uncertain whether his strategy is complete in the sense that all the true test cases are provable and all the false test cases are disprovable. The QA professional would really like to be able to answer two questions:
(1) Are all the true test cases provable in his test strategy?
(2) Are all the false test cases disprovable in his test strategy?
Now, the QA professional also has access to a second bounded document that is titled The Manual of Sets. Like the other book, this one also has its pages consecutively numbered, and each page contains a description of a set of positive whole numbers. Any set of numbers which is described anywhere in the manual we will call a listed set. Now, given any number n, it may be the case that the set listed on page n (of The Manual of Sets) contains n itself as a member; if this happens we will then call n an extraordinary number. Also, given any numbers n,h, we will call h an associate of n if the test case on page h (of The Manual of Test Cases) asserts that n is extraordinary.
The QA professional learns that the following four conditions (constraints) hold:
<UL TYPE=SQUARE><LI><font color="#ff0000">E1</font>: The set of page numbers of all provable test cases is a listed set.<LI><font color="#ff0000">E2</font>: The set of page numbers of all disprovable test cases is a listed set.<LI><font color="#ff0000">C</font>: For any listed set A, the set A of all numbers not in A is a listed set.<LI><font color="#ff0000">H</font>: Given any listed set A, there is another listed set B such that every number in B has an associate in A and every number outside B has an associate outside A.[/list]
These four conditions allowed the QA professional to answer his own questions.
Exercise 1: Is every true test case provable in the test strategy?
Exercise 2: Is every false test case disprovable in the test strategy?
Extra Credit Exercise: How can you determine whether or not the set of page numbers of all the true test cases is a listed set and whether the set of page numbers of all the false test cases is a listed set?
<font color="#0000ff">HINT:</font> For this puzzle, you might consider "sets" here as "numbered requirements" and think of The Manual of Sets as The Manual of Requirements. Now do you see how this puzzle could be formulated? Do you see, perhaps, a hint of a traceability puzzle here (in terms of, perhaps, test cases to requirements)? (Incidentally, I will say that the solution to this puzzle, in terms of understanding it, also helps you understand something known as Gödel's Incompleteness Theorem. So not only can you gain a deeper understanding of how test systems can work but you can also educate yourself on a fundamental facet of logic at no extra charge.)

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<center>Okay, So Now What?
(Or: Was There A Point To All This?)</center>
The biggest danger I faced in writing all this (and you face in reading it) is that it will be dismissed as ranting, showingoff, or simply wasting people’s time. (I have been accused of each.) Another danger is not looking beneath the puzzle format and not trying to see how this material applies in a variety of situations that come up quite regularly in the field of quality assurance and in the subset of strict testing.
What I have been talking about in these puzzles is systems that can be more or less broad. You can consider an application as a system under test or you can consider a requirements document as a system or even consider an organization as a whole as a system. Then I looked at what the notion of truth (read: validity) might mean within the context of that system and what the notion of provability might mean. (Consider this thread that asked about "proving" the "value" of QA.) "Value" suggests a certain degree of validity and "proving" anything requires a notion of what "proof" means in a given context.
Consider, if you will, the following:
<center><font color="#0000ff">This sentence can never be proved</font></center>
Replace "sentence" with whatever you want (requirement, test case, best practice, process) and consider "proved" to also equate with "valid" or "viable".
What are we really saying with this sentence? If the sentence is false, then it is false that the sentence can never be proved, which means it can be proved, which means it must be true! So if the sentence is false I have just shown a contradiction, and thus the sentence must be true. So I have just proved that the sentence is true, right? Then, since the sentence is true, what it says must be true, which means that the sentence can never be proved. But wait a minute! Did I not just do that?
Can you spot the fallacy? The fallacy is that the notion of what it means to be "provable" is not really welldefined. The notion of "proof" is not always a precise one. It can be more or less precise in certain situations but to assume it is precise is to make a mistake. We can say that those "certain situations" correspond to systems. In other words, we tend not to speak of provability in general but, rather, of provability within a given system. So suppose we have a system, S, in which the notion of provability within the system S is quite welldefined.
Suppose also, at this point, that the system S is correct in the sense that everything that is provable within the system really is, in fact, true. Now consider the following:
<center><font color="#0000ff">This sentence is not provable in system S</font></center>
Do we have a fallacy here? No, but we do have an interesting truth that can serve as an axiom for many kinds of work we do. The truth we have is that the above sentence must be a true sentence which is not provable within the system S. It is similar to a Gödel sentence which can be seen as asserting its own unprovability – but not in an absolute sense. Only in relation to system S.
This brings up interesting points. First of all, this sentence is easy. Imagine more complex sentences that would similarly state their unprovability but not be as obvious about it. Now think of test scenarios or situations in a QA environment where things like this can happen. Also note that the crucial point is that the unprovability only stems from system S. Another system, say system R, might be able to prove the statement  or, more accurately, the statement may be provable in system R, although not in system S. What this means is that certain sentences are more or less valid depending on the notion of what you are dealing with and the system in which those sentences must apply. Hmmm. Are we not approaching a mathematical description of the idea that there are no best practices, just good practices in context? Does this not start to show that "proving" the "value" of QA is, by its very nature, a contextual and situational affair?
I could go on and on about different applications of this and show how my logic here has been multifaceted, however, I trust that my point has been communicated and, if that is the case, I trust that the validity of this thematic interlude has at least been established, even if you perhaps disagree with me on some or all of the particulars.
(Oh, yes, and in the "Not Leaving You Hanging" category, I will eventually post the solutions to the exercises in another thread.)

Moderator
Re: Gödelian Quality Assurance – A Thematic Interlude
<BLOCKQUOTE><font size="1" face="Verdana, Arial, Helvetica">quote:</font><HR>Originally posted by JeffNyman:
In my opinion, this is sort of an I.Q. test for QA and test professionals.<HR></BLOCKQUOTE>
Are you serious?
Fun, sure. But I.Q. Test?
Have you actually tried to compare the results of these tests against your concept of an "Intelligent" QAer or Tester?

 Joe (strazzerj@aol.com)

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
<BLOCKQUOTE><font size="1" face="Verdana, Arial, Helvetica">quote:</font><HR>Originally posted by jstrazzere:
Are you serious?
Fun, sure. But I.Q. Test?
Have you actually tried to compare the results of these tests against your concept of an "Intelligent" QAer or Tester?
<HR></BLOCKQUOTE>
It pays to consider all the words that were said. I said "sort of an I.Q. test" (emphasis added). Intelligence is defined as the capacity to acquire and apply knowledge and the faculty of thought and reason. These themes highlight all of those abilities. Can you say that for every certification test you have seen? Or for every book you have read on the subject. I, for one, cannot.
The idea is to see how people think  not just if they can memorize certain facts. The idea is to think if someone can think abstractly within their field of discipline. The idea is to see if one can take disparate knowledge and apply it. Above all, however, it again pays to consider what I said: "The point of this is to get people thinking about these things."
A major part of this theme, however, is to show that a formalistic type logic does, in my opinion, underlie QA. Most people would say "who cares" but that would, again just in my opinion, show shortsightedness. These puzzles highlight a lot of subthemes: the presence of uncertainty in all systems, the inability of all test cases to ever be provable, the inability of traceability to ever be complete. But it also points the path to how we can do certain things to alleviate the boundary conditions, if you will, of QA.
[This message has been edited by JeffNyman (edited 03252002).]

Senior Member
Re: Gödelian Quality Assurance – A Thematic Interlude
While I doubt I'll ever spend the time acutally reading and trying to solve these puzzles, I have to mention something I just read which seems to echo some of Jeff's thoughts here.
In Surely You're Joking, Mr. Feynman!, one of Feynmann's essays describes a time he spent teaching physics in Brazil. He became greatly disheartened by the fact that the Brazilian students were very good at memorizing facts, but were never taught how to understand the greater meaning of those facts. If he would ask a question concerning some real world phenomenon, they could not answer it even though they could quote all applicable theories and formulas if he simply asked for them.
Just thought I'd throw that in, Jeff. You can keep my two cents.

Charles Reace
charles{DOT}reace{AT}verizon{DOT}net
[This message has been edited by Charles Reace (edited 03252002).]
web site  [url=http://www.ebookworm.us/[/url]
[i]...Sound trumpets! Every trumpet in the host! / Sixty thousand, on these words, sound, so high the mountains sound, and the valleys resound.</i] (The Song of Roland)
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules
