

Senior Member
Gödelian Quality Assurance – Solutions
This thread will provide solutions to the Gödelian Quality Assurance – A Thematic Interlude thread for those of you who did read the thread and are curious as to how accurate you might have been in working out the solutions to the exercises.
Each post in this thread will cover the solution for each puzzle that was mentioned in the Thematic Interlude thread. Remember that some puzzles were made up of more than one exercise so I will post a solution to each exercise here. Do not be surprised, however, if, once in awhile, a few new "puzzles" or questions come to your mind when you consider the solutions.

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>Theme 1: A Gödelian System
Puzzle 1: The System G</center>
** Exercise 1  Solution **
Exercise 1 asked us to prove that there was at least one unestablished KPasser in the system. (Remember that, here, "unestablished" means that the KPasser is a component that always passes, or does not have hidden faults, but has not been proven to be such a component yet.)
Remember that this puzzle gave us conditions or constraints. As such, by constraint <font color="#ff0000">E1</font>, the set E of all established KPassers forms a group. Hence by condition <font color="#ff0000">C</font>, the set E of all components in the system that are not estalished KPassers also form a group. Then by condition <font color="#ff0000">G</font>, there is at least one component in the system that claims (via its interface) to be a member of the group E. In other words, this component claims that it is not an established KPasser. In other words, it is an unestablished KPasser.
Now, consider that a KFailer component could never possibly claim that it was not an established KPasser (because it is true that a KFailer is not an established KPasser and KFailers do not make true claims). So the component making the claim we just talked about above must be a KPasser. Since it is a KPasser its claim via its interface is true, so it is not an established KPasser. Thus, we have shown, the component is a KPasser and that is not an established KPasser.
Thus, for example, you have a potential component of the system that does not possess hidden faults and thus less testing time could be spent on this, as opposed to one of the KFailers. But are you aware of this? Or will you distribute your testing effort unevenly?
** Exercise 2  Solution **
Exercise 2 asked us to prove that there is at least one unestablished KFailer in the system.
By condition <font color="#ff0000">E2</font>, the set of established KFailers form a group. So, because of condition <font color="#ff0000">G</font> there is at least one component in the system that claims to be an established KFailer (meaning that its interface claims that it is a member of the group of established KFailers). Obviously this component cannot be a KPasser (since a KPasser interface could not claim to be any kind of KFailer), so the component is a KFailer. Therefore its claim is false (invalid), thus the component is not an established KFailer. This means that the component is a KFailer but not an established KFailer. Or, in other words, it is an unestablished KFailer.
The practical upshot of that, apart from the strict solution itself, is that you have a component that has a hidden fault (potentially) or an active fault but has not been established, yet, as having that fault. Thus you have a risk in your system. (This puzzle does not speak to the severity of the risk at all since all risks  KFailers  in these two puzzles have been normalized.)
** Exercise 3 and 4  Solution **
Exercise 3 asked us whether or not the set of all KFailers in the system formed a group. Exercise 4 asked us whether or not the set of all KPassers in the system formed a group.
This was fairly easy to figure out. If the set of KFailers formed a group, then at least one component would claim to be a KFailer, which neither a KPasser nor a KFailer could do. Thus the set of KFailers does not form a group. (Interesting ramifications for test groupings and performing test clustering, particularly if you are doing some sort of proactive fault analysis.)
As far as the other situation, if the set of KPassers formed a group, then the set of KFailers also would (by condition <font color="#ff0000">C</font>), so the KPassers do not form a group either.
Interesting. But we know techniques like equivalence partitioning at the lowend, test clustering at the middle level, and fault analysis at the highend, do work. So what is the discrepancy here? The solution to that is something I leave to the interested (and resourceful) reader. Just recognize that Exercises 3 and 4 provide an alternative solution to Exercises 1 and 2.

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>Theme 1: A Gödelian System
Puzzle 2: General Gödelian Systems</center>
** Exercise  Solution **
This puzzle only had one exercise. The exercise was to determine if the system described in the puzzle was Gödelian. (You were told, in the course of the puzzle that the fictitious QA professional was, in fact, able to determine if the system was or was not Gödelian in nature.)
The answer: Yes, the system is Gödelian.
Consider any group C. Now let D be a group given by condition <font color="#ff0000">H</font> from the puzzle. (Remember that condition <font color="#ff0000">H</font> said: 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.)
This new group D is named after a component  say API_Interface. Either API_Interface belongs to group D or it does not.
Suppose that API_Interface does belong to group D. Then API_Interface has a friend  call it API_Sound  in group C who would claim that API_Interface is sociable. Since API_Interface does belong to group D, then API_Interface really is sociable, hence API_Sound is a K_Passer. So API_Sound is a K_Passer that belongs to group C, so API_Sound will claim that it belongs to group C.
Now, instead of the above scenario, suppose that API_Interface does not belong to group D. Then API_Interface has a friend  call it API_Graphics  that is not a member of group C, and API_Graphics claims that API_Interface is sociable. Since API_Interface is not a member of group D, then API_Interface is actually unsociable, hence we see that API_Graphics is a K_Failer. So API_Graphics is a K_Failer that is not part of group C, hence API_Graphics would falsely claim that it is part of group C. So whether API_Interface belongs to group D or does not belong to group D, there is a component who claims to be a member of group C.
Incidentally, if you combine the results of Puzzles 1 and 2, you can see that given any system that satisfies conditions <font color="#ff0000">E1</font>, <font color="#ff0000">E2</font>, <font color="#ff0000">C</font>, and <font color="#ff0000">H</font>, that there must be both an unestablished KPasser and an unestablished KFailer in the system. Thus you will have faults pretty much no matter what is what this partly tells you thus you have a matehmatical and logical proof of the incompleteness of testing. This is really just a disguised form of Gödel's Incompleteness Theorem (dealt with in Theme 3).
Also, if you would like to try a tough problem on someone else, give them a scenario where they have a system with conditions <font color="#ff0000">E1</font>, <font color="#ff0000">E2</font>, <font color="#ff0000">C</font>, and <font color="#ff0000">H</font> and do not mention condition <font color="#ff0000">G</font> at all. Then pose Puzzle 1 of Theme 1 to them. The idea here would be to see if the person comes up with condition <font color="#ff0000">G</font> on their own. (If you are wondering about the relevance of this, it does, to a certain extent, speak to the notion of testability that one might derive relative to a given system. In other words, how testable would someone claim a given system is and on what basis would they make that decision?)

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>Theme 2: Doubly Gödelian Systems
Puzzle 3: The Doubly Gödelian System S</center>
** Exercise 1  Solution **
Exercise 1 really asked us two things: can we determine if there is an unestablished KPasser in system S and can we determine if there is an unestablished KFailer in system S?
Remember that, according to this puzzle, the 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 true. From those we know that the set of established KPassers forms a group and since that is the case, it is also the case that the set of all components that are not established KPassers also forms a group.
So, taking these two groups for hypothetical groups C1, C2, we have (by condition <font color="#ff0000">GG</font> given in the puzzle) components A,B who make the following claims:
<font color="#0000ff">A: B is an established KPasser.</font>
<font color="#0000ff">B: A is not an established KPasser.</font>
It should be obvious to all readers who have come this far that at least one of the two components A,B must be an unestablished KPasser. (More specifically: if A is a KPasser then it is not an established KPasser, and if A is a KFailer then B must be an unestablished KPasser.) What is interesting here is that even though we know that one of A,B is an unestablished KPasser, we have no idea which one. (Thus we see, in a roundabout fashion, that faultfree aspects our systems might be hard to root out.)
In a similar fashion, since the established KFailers form a group, so, too, does the set of all components that are not established KFailers. Therefore (again by <font color="#ff0000">GG</font>) there must be two components who claim (via their interfaces):
<font color="#0000ff">A: B is an established KFailer.</font>
<font color="#0000ff">B: A is not an established KFailer.</font>
It is obvious that from this it follows that if B is a KFailer then it is an unestablished KFailer and if B is a KPasser then A is an unestablished KFailer. In either case, A or B is an unestablished KFailer (a fault that has not been found), but we do not know which one is the KFailer.
** Exercise 2  Solution **
Exercise 2 asked us if we can determine whether the KPassers in system S formed a group and if we could determine if the set of KFailers in system S formed a group.
For this, consider that if the set of KPassers form a group, then so does the set of KFailers (by condition <font color="#ff0000">C</font>), and if the set of KFailers forms a group, then so does the set of KPassers (again, by condition <font color="#ff0000">C</font>). So what we have is that if either of these two sets formed a group, they both would. Quite obvious. So, now, suppose that they both do, in fact, form groups.
Then, by condition <font color="#ff0000">GG</font> there must be components A,B who would make the following claims via their interfaces:
<font color="#0000ff">A: B is a KFailer.</font>
<font color="#0000ff">B: A is a KPasser.</font>
This is an impossible situation. (Can you see why it is impossible? Can you formulate where the contradiction comes in?) The conclusion we end up with is that neither the set of KPassers nor the set of KFailers can form a group.
Incidentally, solving Exercise 2 actually gives a much easier solution to Exercise 1. Consider that, as we now know, since the set of KPassers does not form a gorup and the set of established KPassers does, then the two sets are different, hence not all KPassers are established. This is the similar situation with KFailers. So, again, we see that the potential for, say, uneven test distribution and skewed test efforts are not only possible, they are practically a certainty.

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>Theme 2: Doubly Gödelian Systems
Puzzle 4: The System S<sup>1</sup></center>
** Exercise 1  Solution **
In this exercise, you were asked to prove that either there is an unestablished KPasser or an unestablished KFailer in the doubly Gödelian system S<sup>1</sup>.
Remember that, as stated in the puzzle, the conditions/constraints <font color="#ff0000">E1</font> and <font color="#ff0000">E2</font> from Puzzle 1 hold. Because of that we know that the estalished KPassers form a group and that the established KFailers form a group. That means there are then components A,B who claim via their interfaces:
<font color="#0000ff">A: B is an established KFailer.</font>
<font color="#0000ff">B: A is an established KPasser.</font>
Now, suppose A is a KPasser. Then its claim is true/valid, hence B is an established KFailer, which means B's claim is false/invalid, and thus A is not an established KPasser. In this case, then, A is an unestablished KPasser. If we suppose that A is a KFailer, then B's claim is false, so B is a KFailer. Also this means that A's claim is false, so B is not an established KFailer. So, in this case, B is an unestablished KFailer.
What do we end up with? We end up with a situation where either A is an unestablished KPasser or B is an unestablished KFailer  but we have no idea which is which.
** Exercise 2  Solution **
In this exercise, you were asked to prove that it is impossible that both the KPassers formed a group and also that the KFailers formed a group.
One easy way to solve this is to assume the counterfactual. Assume that the KPassers formed a group and the KFailers also formed a group. This means there would be components A,B such that A claims B is a KFailer and B claims A is a KPasser  which we know to be impossible. (See the solution to Exercise 2 in Puzzle 3.)
Thus it cannot be the case that the KPassers form a group and also that the KFailers form a group. Either the KPassers do not form a group or the KFailers do not form a group. If the KPassers do not form a group, then there must be an unestablished KPasser (since the established KPassers do form a group). If the KFailers do not form a group, then, again, there must be an unestablished KFailer. The rub is that we cannot tell which.
Incidentally, this also proves Exercise 1 for this puzzle.

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>Theme 3: Gödel's Complete System
Puzzle 5: Is The System Complete?</center>
On the face of it, this puzzle was a little different than the others had been. It had a new set of conditions/constraints. However, in reality, this is the same thing as the puzzles in Theme 1, just laid out in a different manner. Part of the test with this puzzle was to see if you were able to recognize similar situations but in a different guise. (Sometimes in QA or testing we have to provide solutions for problems that, on the face of it, appear quite different but, in actual fact, are what we have dealt with before.)
In this puzzle (and with this theme), the page numbers of the true test cases are the role of the KPassers. The page numbers of the false test cases are the role of the KFailers. The provable test cases were the role of the established KPassers and the disprovable test cases were the role of the established KFailers. The listed sets in this puzzle play the same role as the groups did in the other puzzles. The idea of a set being listed on a given page that has a certain number in this puzzle is similar to the notion of a group being named after a given component in the other puzzles. Also, the "extraordinary" numbers in this puzzle correspond to "sociable" components in the other puzzles, just as the notion of "associate" in this puzzle plays the role of the "friend" from the other puzzles.
There were two exercises presented in this puzzle and, to a certain extent, they might have been a little harder than the others to solve because to make things easier on yourself, it made sense to first formulate and prove the analogue of condition <font color="#ff0000">G</font> from the previous puzzles. In this case, that analogue would be: For any listed set A, there is a test case which is true if and only if its own page number lies in A.
How do we prove condition <font color="#ff0000">G</font>? Well, take any listed set A. Let B be a set given by condition <font color="#ff0000">H</font> (which is given in this puzzle). Now, let n be the number of a page on which B is listed. By condition <font color="#ff0000">H</font>, if n lies in B, then n has an associate h in A. If n lies outside B, then n has an associate h outside A. We assert that the test case X on page h is the test case we are looking for.
The test case X says that n is extraordinary  in other words, that n does lie in B (since B is the set listed on page n). If X is true then n really does lie in B, hence h lies in A. So if X is true, then its page number h does lie in A. Suppose X is false. Then n does not lie in B, hence h lies outside A. Thus X is true if and only if its page number lies in A.
Whew. Okay, with condition <font color="#ff0000">G</font> proven I can show how the exercises are solved. (Note you did not have to explicitly state <font color="#ff0000">G</font> to solve the puzzle, but you would have implicitly thought that way.)
** Exercise 1  Solution **
This exercise asked you if every true test case was provable in the test strategy. We are given that the set A of page numbers of all the provable test cases is a listed set, hence by condition <font color="#ff0000">C</font>, so is the set A of all numbers which are not page numbers of provable test cases, therefore (by condition <font color="#ff0000">G</font>) there is a sentence X which is true if and only if the page number of X belongs to A. Now, to say that the page number of X belongs to A is to say that the page number of X does not belong to A, which is to say that X is not provable (since A consists of the page numbers of those test cases which are provable). Thus X is true if and only if X is not provable. This means that either X is true and not provable or X is false but provable. You are given in the puzzle that no false test case is provable in the system, hence X must be true but not provable in the system.
** Exercise 2  Solution **
This exercise asked you if every false test case was disprovable in the test strategy. In this case, we now take A to be the set of page numbers of all the test cases which are disprovable. Applying condition <font color="#ff0000">G</font> we get a test case Y which is true if and only if its page number is the page number of a disprovable test case  in other words, Y is true if and only if Y is disprovable. This means that Y is either true and disprovable or false and not disprovable. The first possibility is not tenable since no disprovable test case is true. This means that Y must be false but not disprovable in the system.
** Extra Credit Exercise  Solution **
I usually do not provide solutions for extra credit but here the point is kind of important. This exercise wanted you to figure out how to 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.
Well, if the set of page numbers of all the false test cases were a listed set, then there would be a test case Z which is true if and only if its page number is the page number of a false test case  in other words, Z would be true if and only if Z is false, and this is impossible. (It would be equivalent to saying something like: "This sentence is false.") Therefore what we have is that the set of page numbers of all the false test cases is not a listed set. (Think about the ramifications of that!) Then, by condition <font color="#ff0000">C</font>, the set of page numbers of the true test cases is also not a listed set. (Once again: interesting ramifications.)

Senior Member
Re: Gödelian Quality Assurance – Solutions
<center>PostScript</center>
And that concludes the experiment of a thematic thread within QA Forums and it concludes the notion of the Gödelian Quality Assurance theme overall. Hopefully, if you read the puzzles and the solutions, you realize what is being shown here. What I have been trying to show is that a formal system does seem to underlie QA and testing practices.
Proving something like this is very important because it can show a logical structure to the discipline as a whole. That logical structure will present certain axioms, if you will, that are eminently provable by all but the most rigorous of conditions (since the notion of "proof" in any system such as that would be somewhat provisional). In that sense, when people ask you to "prove" the "value" of QA or "prove" the "effectiveness" of a given practice or ask you to explain why testing and QA cannot ensure perfection, you actually have a rigid set of arguments to fall back on that are not anecdotal or circumstantial.
Formal systems have been shown to underlie things like physics, logic, language, software engineering, and many other fields of endeavor. In all cases, recognition of this underlying system has allowed those disicplines to grow and, more importantly, to validate their conclusions in a wide venue. In other words, it allowed the discipline(s) to mature to a certain extent by allowing them to focus on the details of their procedures and not concentrating on always proving themselves with recourse to empty arguments or appeals to "common sense" (which is all too often not common). My hope is that the recognizition of such a system underlying the discipline of QA and testing (for discipline they are, I maintain) will give an added impetus to an already exciting (but often maligned) field of endeavor within the IT industry.
However, even with all that, I will be the first to admit that I might have some logic wrong. I might have looked at things too little in some cases or read too much into things in others. Thus having people check me on this stuff is definitely good and is part of why this was posted.
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
