|
|
Re: Hidden Variables
|
Posted: Jul 13, 2006 1:20 PM
|
|
> The answer is simple:
>
> Software development is deterministic because there is a
> clear set of rules that everything is derived from and
> that it can be used to prove a program's agreement with
> specifications.
>
> Algorithms can not be proven correct or incorrect
> according to the halting problem.
>
This is determinism with small print :)
- Cause and effect are related.
- The above is undecidable.
The answer is not simple at all. We have a clear set of rules for writing programs. However, each time we find an exception to our rules, we extend the set of rules with a new one - the exception itself. However, this Goedelization process of programing is not constructive, because it ends up in a paradox: "Name the largest number that can be described in 100 words or less".
Here's why: a program is a substitution for its output. One can either say: "This is the output for this input" or write a program which calculates the output. The approaches are Turing equivalent. Out of all Turing equivalent ways to express an output, the shortest way to do has some interesting properties:
1) its bits are not compressible
2) any other way to generates the same output is Turing equivalent.
3) its size in bits is a measure for complexity
Fine with that. So?
For "Name the largest number that can be described in 100 words or less" you can write the number, write a program or simply write the phrase. However, "Name the largest number plus one that can be described in 100 words or less" is also a valid statement. The two statements are because they describe the same result, however their results differ by 1.
In programming:
Number getNumber1() {
return some_way_to_calculate_that_number();
}
Number getNumber2() {
return getNumber() + 1;
}
The paradox is:
(shortestWayToState(a) == shortestWayToState(b) &&
a == b) is always false. You state the same number twice, but the you end up with two different numbers.
This is in fact the halting problem, which can be quickly expressed as:
boolean willHalt(Program p) {
return someHaltingAnalysis(p); // of complexity H
}
From any program a we can build program b does:
if(willHalt(a)) while(true);
For all programs a of complexity H the statement is:
willHalt(a) == willHalt(b)
however b will loop forever. That's a paradox and it can be resolved only by adding "willHalt(b) is false" as a new rule. Just in time to find the next paradox c:
if(!willHalt(b)) return;
The complexity of willHalt, a, b, c is in the relationship
willHalt = a < b < c
Back to the original topic: determinism holds only as long as the complexity of the subject of study is less or equal than the complexity of the deterministic method employed in the study. Beyond that point, all of the unaccounted complexity of the subject will be observed as random behavior.
Just having rules doesn't make things deterministic. The rules have to be complex enough for determinism to work.
|
|
Previous Topic
