1

First I'll tell you a bit about how (at least modern) software development works to clarify what I mean by a "test". I'll also narrow the scope to a very particular kind of test known as block box testing since its the simplest form of test and is often highly effective in practice. I try not to assume too much about the nature of programs or programming here but I don't think I entirely accomplish that. Please feel free to ask questions!

A program (for the purposes of this discussion) is something that can be given inputs such as numbers or text and produces outputs. This narrow definition of a program can be mathematically formalized as a function. Specific inputs produce specific outputs. Under this simplified definition if the same inputs are given on two separate occasions, the same output is produced. A program of this kind is just a mechanical realization of a mathematical function.

When creating programs, programmers make mistakes. Sometimes programmers get it right however. In order to build confidence that a program has been created to mimic the desired function, other programs are creates to "test" the program. These programs that "test" another program are called "tests" conveniently enough. A test will give various inputs, one at a time, to a program under test to see if the program outputs the desired values. If an input is found that causes a mistmatch between the output and the expected output, we have a bug. If no bugs are found by the tests, we say the tests are passed (but we don't say that the program is correct because we haven't checked all possible inputs).

It's hard to explain why this process should give confidence of correctness however. Certainly I should have more confidence in a program if I've run some tests on it than if I've run no tests since I at least know that the tested inputs are correct. I should also have a bit more confidence if I test a new input and it sill passes. The more inputs I test the more confidence I should have. But why?

In practice forms of black box testing that randomly check many thousands of inputs consistently find bugs in practice. Programs which pass these checks generate very high confidence in practice. Additionally when tests check all "small" inputs exhaustively this generates high confidence as well. There are cases where the programmer has some information which tells them that the such randomized testing is unlikely to catch the inputs of greatest concern and this can undermine these high levels of confidence but in general this sort of testing typically generates high levels of trust that the program is correct.

One incomplete explanation is parsimony. As more and more inputs are attempted, a program which is correct on all of those inputs and yet not on some other input becomes more and more complicated to write pending contrived cases like a correct program modified to output something incorrect on one highly specific input. Can we be more formal?

It's similar to "why does seeing another black raven increase my confidence that all ravens are black" but each observation can be distinguished in this case. Additionally, while I haven't elaborated on this, programs have specific structure. For instance we can talk about the "size" of a program or we can talk about the kinds of mistakes programmers are likely to make in practice. Does this difference in structure change the problem? Does it give us a way to talk more concretely about evidence in confidence based on tests?

  • 1
    I think the answers to these questions are extremely nuanced; and the subject matter of writing good tests for programming may be too niche for this community. softwareengineering.se may be a better fit, but I still have a feeling this is too high level even for that community. But roughly at a high level it's not about "parsimony" per se... it's about quality, cost savings, and (not mentioned) flexibility (good tests that stay around help in refactoring). – H Walters Jun 10 at 2:22
  • Correct; it is the well-know Problem of Induction: no certainty at all... but it worked for millenia (humans survived using the "natural born" attitude to generalize). – Mauro ALLEGRANZA Jun 10 at 8:16
  • @MauroALLEGRANZA: Yes, but only in the sense that certainty is a spook. – CriglCragl Jun 11 at 0:18
0

I agree with @HWalters -- what could have possibly motivated you to post this here???:) Nevertheless, I happen to have been a software developer all my professional life, and also have an ms in physics, so maybe I can see a tenuous connection, as follows. Firstly, let's define a program as corresponding to a computable function f:N-->N, since any text string can be represented by its Godel number, etc (e.g., the rationals and the computable reals can both be mapped to N). That'll permit more focused and more rigorous discussion.

Now, like scientific theories, programs are falsifiable by tests/experiments, rather than provably correct. But there is an exception, the same one for both. Within a limited range, both are provably correct. For programs, that range is simply a finite subset of N, whose cardinality is small enough so that you can exhaustively test every n in that subset. For physical theories, e.g., Newtonian mechanics is a provably correct approximation for small-enough speeds, so special relativity is irrelevant, and for not-too-large and not-too-small masses and distances/times, so that both general relativity and quantum mechanics are also irrelevant. Then you still can't test literally every conceivable situation, simply because that collection is nondenumerable and uncomputable (whereby you can't even conceive them all "individually"). Nevertheless, within its regime of applicability, I'd say it's generally accepted that Newtonian mechanics has been experimentally proven (aka tested) correct.

So you can maybe draw a vague analogy between testing programs and testing theories -- they're typically both falsifiable rather than provable, but that's maybe tangentially-at-best relevant here.

| improve this answer | |
  • 1
    It seems like there's an additional trick being applied in the Newtonian Mechanics case though right? There's a notion of continuity involved or being assumed right? The idea is that small changes to the experiment should result in small changes to the outcome (in most cases, chaotic mechanical systems exist I suppose). For a black box we don't have that really. – Jake Jun 10 at 23:25
  • 1
    @Jake Well, yes, sort of. Physically speaking, you probably wouldn't want to test that continuity assumption by stepping off a cliff. Computationally speaking (and I'm inferring from your profile that you have enough tcs background to follow this...), from the formal point of view of denotational semantics and domain theory, if you give "a little more info about the input" (i.e., a slightly stronger domain element), you'll get "a little more info about the output". Or, more formally, the computable function's continuous wrt to Scott (or Lawson if it's recursive as well as r.e.) topology. – John Forkosh Jun 11 at 7:07
  • Ah yeah true, perhaps continuity isn't the key. It seems like maybe compactness is however important? Sometimes the topology is discrete and the only open set is the universe, when this happens things are hard to test, the only "small step" you can make is to a specific number. In fact this the case most of the time. Additionally when that topology is compact we can actually write much more powerful tests to verify code. If I say "velocities of magnitude significantly less than the speed of light" also makes such a compact space. That's an interesting direction of thought for me, thanks! – Jake Jun 12 at 8:11
0

The more inputs I test the more confidence I should have. But why?

In the general all question, given a black box with infinite possible inputs and some output, and with unknown complexity, it is unclear what amount of testing will give what amount of confidence when predicting the next behavior of the black box.

However when the complexity of the interior of the box is known (white or grey box), then the actual behavior of the box is likely completely describable using a simple function, and thus only a few samples are required to check it matches the intended function.

As a concrete example, consider the problem of tracing electrical wiring inside a wall using a voltage detector. Without any other information, you'd need to test every point of the wall with the detector to determine whether there is wiring at this point. But when you can be sure that all wiring is done horizontally and vertically (from outlets and switches), you can test only a few points or lines of a wall and still be confident afterwards that you know all the invisible wiring.

Software testing follows the same principle, a software is generally assumed to follow certain principles such that only using a few data points, the structure can be confirmed with high confidence. This assumption is made viable by applying certain methods and conventions when creating and documenting software (similar to electrical wiring being laid out horizontally and vertically in drywalls).

| improve this answer | |
0

It comes down to intelligible intelligence. Which I suggest is a specific case of mutual intelligibility. As an experiment, people tried reverse diagnosing the function of a microchip; it was basically impossibly difficult. You need insight into how something occured, and how it fits within systems, to make sense of it. Language is like this too. An machine learning program can undertake an opaque learning process, which can have completely unpredictable features - unless it is drawn into a web of intelligibility, into the web of understandings & abstractions we call language. This is like finding a bridge between languages. Really advanced AGI, or aliens, might have a web of abstractions which can encompass our set of abstractions (eg senses +all-mutually-intelligible-words +maths) but not be expressed in them. Then we would be like a dog being shown relativity.

You could take a defined volume, if it has maximum entropy it is completely chaotic, like say a section of the superfluid at the centre of a black hole, thought to occupy the maximum density of states. Every notch toward less entropy than that, involves some symmetry, some reduction of total possible complexity. And that is abstraction. For a given closed system of a certain complexity there are finite abstractions that can work, and through testing you can narrow down on the tree of possibilities at least to certain categories or limbs.

But, entropy can only be measured in relative terms, as change of state. If there is hidden information that you can't gauge from heuristics and knowledge of available states, that can always be a source of unpredictability. If you build the system, you should be able to put at least boundary conditions on the type & scope of errors. Systems capable of self-directed learning are an interesting case, if that was in the black box. Energy/entropy consumption would still impose boundary conditions. But given a tree of possible abstractions, an intelligence might find an extremely unlikely tip of a branch, which heuristics wouldn't be much use for constraining.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.