Todd R. Keuny
Registered: Nov 2006
Modeling the Debugging Process
I am interested in the problem of "debugging" large software systems (multiple parts, multiple processes).
One element of my interest is to try and identify how much "knowledge" about a system is required in order to make "useful" inferences and/or alterations. I observe that its is easy to make "locally right" observations which are "globally wrong" and that as a system tends to be more complex this problem becomes more prevalent.
My idea is to create an environment where a small "window" looks into a larger "universe" where the content of the universe is driven by some CA and then use this environment to try and understand what can be inferred though the window.
Here is my first attempt to define such an environment:
First, I create a "Universe". It is easiest for me to think of the Universe is a large, toroidal game of Conway's Life, lets say 1,000 by 1,000 cells, though I believe any CA that can be associated with a toroidal space could be used (with perhaps different impact on the conjectures below).
The Universe is toroidal such that each edge seamlessly wraps around to the opposing side.
A cell has a "Value" of one (1) if the cell is populated and zero (0) if it is not populated.
The Universe is initialized with random values for each cell.
The Universe is opaque to the outside world save for a "Window" created by an "Observer".
Associated with the Universe is publicly visible "Time". Time is a many digit number that, at the time the Universe is created, is initialized to a random value. Each time the underlying CA advances a generation this number is incremented. Each increment is a "Tick".
Knowledge of Absolute Time is knowledge of the actual CA generation.
I allow an "Observer", which is a person or persons, the ability to create rectangular "Window" positioned relative to the Universe. The Window allows the Observer to see and record, but not change, the contents of the cells which underly the Window. The Observer is also allowed to know the rules of the CA that govern the Universe.
The height and width of the Window are randomly chosen values limited to a few percent of the size of the universe.
The absolute position of the Window relative to the underlying Universe is not knowable by the Observer.
The Observer may record Ticks and corresponding "Window" contents.
The Observer is not allowed to know the Absolute Time.
The Window may be moved by the Observer and the Observer may record the relative distance in cells. Movement occurs "between" Ticks.
Next, I define some terms:
A "Prediction" is a numerical value, either zero or one, assigned a cell by the Observer. If, in the next generation, the cell's Value is equal to the predicted value, the result is True. Otherwise its False.
"Full Comprehension" occurs when the Observer can correctly "Predict" the value of all cells in the Universe for all subsequent generations.
"Local Comprehension" occurs when the Observer can correctly "Predict" either the value of a subset of cells in the Universe, e.g., those in the Window, for all subsequent generations.
"Theoretical Comprehension" occurs when the Observer can correctly "Predict" the value of a subset of cells for a subset of remaining generations.
How this relates to debugging:
The Universe is a program or system to be understood. The Window represents the tool used by someone to study that system. The various levels of prediction are defined to mimic the steps someone goes through in learning a complex system.
I believe the "conjectures" below reasonably mimic the general debugging experience.
Some initial conjectures:
#1 - I cannot reconstruct the initial state of the Universe without use of Absolute Time.
Requirements for conjecture #2
A single movable Window created at some unknown to the Observer interval after the creation of the Universe.
Unlimited number of observations.
Observations occur at relative Tick intervals I choose.
#2 - "Full Comprehension" of the Universe may not be possible (infinite number of observations).
#3 - Allowing multiple Windows or large Windows (violating the previous requirement on percentage size) guarantees "Full Comprehension" is always possible once a "sufficient" portion of the Universe is revealed.
I think understanding conjecture #3's "sufficiency" requirement is key for understanding debugging.
Report this post to a moderator | IP: Logged