# Thread: Gödelian Quality Assurance – Solutions

1. ## 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.

2. ## 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 K-Passer in the system. (Remember that, here, "unestablished" means that the K-Passer 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 K-Passers forms a group. Hence by condition <font color="#ff0000">C</font>, the set -E of all components in the system that are not estalished K-Passers 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 K-Passer. In other words, it is an unestablished K-Passer.

Now, consider that a K-Failer component could never possibly claim that it was not an established K-Passer (because it is true that a K-Failer is not an established K-Passer and K-Failers do not make true claims). So the component making the claim we just talked about above must be a K-Passer. Since it is a K-Passer its claim via its interface is true, so it is not an established K-Passer. Thus, we have shown, the component is a K-Passer and that is not an established K-Passer.

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 K-Failers. 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 K-Failer in the system.

By condition <font color="#ff0000">E2</font>, the set of established K-Failers 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 K-Failer (meaning that its interface claims that it is a member of the group of established K-Failers). Obviously this component cannot be a K-Passer (since a K-Passer interface could not claim to be any kind of K-Failer), so the component is a K-Failer. Therefore its claim is false (invalid), thus the component is not an established K-Failer. This means that the component is a K-Failer but not an established K-Failer. Or, in other words, it is an unestablished K-Failer.

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 - K-Failers - in these two puzzles have been normalized.)

** Exercise 3 and 4 - Solution **

Exercise 3 asked us whether or not the set of all K-Failers in the system formed a group. Exercise 4 asked us whether or not the set of all K-Passers in the system formed a group.

This was fairly easy to figure out. If the set of K-Failers formed a group, then at least one component would claim to be a K-Failer, which neither a K-Passer nor a K-Failer could do. Thus the set of K-Failers 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 K-Passers formed a group, then the set of K-Failers also would (by condition <font color="#ff0000">C</font>), so the K-Passers do not form a group either.

Interesting. But we know techniques like equivalence partitioning at the low-end, test clustering at the middle level, and fault analysis at the high-end, 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.

3. ## 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 K-Passer and an unestablished K-Failer 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?)

4. ## 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 K-Passer in system S and can we determine if there is an unestablished K-Failer 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 K-Passers forms a group and since that is the case, it is also the case that the set of all components that are not established K-Passers 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 K-Passer.</font>
<font color="#0000ff">B: A is not an established K-Passer.</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 K-Passer. (More specifically: if A is a K-Passer then it is not an established K-Passer, and if A is a K-Failer then B must be an unestablished K-Passer.) What is interesting here is that even though we know that one of A,B is an unestablished K-Passer, we have no idea which one. (Thus we see, in a roundabout fashion, that fault-free aspects our systems might be hard to root out.)

In a similar fashion, since the established K-Failers form a group, so, too, does the set of all components that are not established K-Failers. 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 K-Failer.</font>
<font color="#0000ff">B: A is not an established K-Failer.</font>

It is obvious that from this it follows that if B is a K-Failer then it is an unestablished K-Failer and if B is a K-Passer then A is an unestablished K-Failer. In either case, A or B is an unestablished K-Failer (a fault that has not been found), but we do not know which one is the K-Failer.

** Exercise 2 - Solution **

Exercise 2 asked us if we can determine whether the K-Passers in system S formed a group and if we could determine if the set of K-Failers in system S formed a group.

For this, consider that if the set of K-Passers form a group, then so does the set of K-Failers (by condition <font color="#ff0000">C</font>), and if the set of K-Failers forms a group, then so does the set of K-Passers (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 K-Failer.</font>
<font color="#0000ff">B: A is a K-Passer.</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 K-Passers nor the set of K-Failers 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 K-Passers does not form a gorup and the set of established K-Passers does, then the two sets are different, hence not all K-Passers are established. This is the similar situation with K-Failers. 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.

5. ## 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 K-Passer or an unestablished K-Failer 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 K-Passers form a group and that the established K-Failers form a group. That means there are then components A,B who claim via their interfaces:

<font color="#0000ff">A: B is an established K-Failer.</font>
<font color="#0000ff">B: A is an established K-Passer.</font>

Now, suppose A is a K-Passer. Then its claim is true/valid, hence B is an established K-Failer, which means B's claim is false/invalid, and thus A is not an established K-Passer. In this case, then, A is an unestablished K-Passer. If we suppose that A is a K-Failer, then B's claim is false, so B is a K-Failer. Also this means that A's claim is false, so B is not an established K-Failer. So, in this case, B is an unestablished K-Failer.

What do we end up with? We end up with a situation where either A is an unestablished K-Passer or B is an unestablished K-Failer - 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 K-Passers formed a group and also that the K-Failers formed a group.

One easy way to solve this is to assume the counterfactual. Assume that the K-Passers formed a group and the K-Failers also formed a group. This means there would be components A,B such that A claims B is a K-Failer and B claims A is a K-Passer - which we know to be impossible. (See the solution to Exercise 2 in Puzzle 3.)

Thus it cannot be the case that the K-Passers form a group and also that the K-Failers form a group. Either the K-Passers do not form a group or the K-Failers do not form a group. If the K-Passers do not form a group, then there must be an unestablished K-Passer (since the established K-Passers do form a group). If the K-Failers do not form a group, then, again, there must be an unestablished K-Failer. The rub is that we cannot tell which.

Incidentally, this also proves Exercise 1 for this puzzle.

6. ## 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 K-Passers. The page numbers of the false test cases are the role of the K-Failers. The provable test cases were the role of the established K-Passers and the disprovable test cases were the role of the established K-Failers. 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.)

7. ## 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
•
BetaSoft Inc.
All times are GMT -8. The time now is 05:45 PM.