Java Reference
In-Depth Information
n/=2;
// divide by 2
else
n=3
∗
n+1;
}
while
(n
>
1) ;
However one has not yet managed to successfully prove that this program will
eventually stop for
any
given
n
. It is a hard mathematical problem that is known
in the literature by the name of Syracuse's conjecture or 3
x
+ 1 problem.
4
This simple toy problem raises the fundamental
halting problem
famous in
theoretical computer science. Loosely speaking, Godel proved that there is
no
program that can decide whether any given program will stop after a finite
number of instructions or not. This important theoretical result, which is one
of the pillars of computer science, will be further explained using a simple
contradiction argument in Chapter 3.8.
2.6 Certifying programs: Syntax, compilation
and numerical bugs
A program that compiles without reporting
any
error message is a
syntactically
correct program. Beware that because of the language flexibility provided by
its high-level semantic, some obscure codes
5
compile. These obscure codes are
often very di
cult for humans to understand. To get a flavor, consider for
example the snippet:
Program 2.10
Syntactically correct program
int
i=3;
// syntax below is valid! guess its result?
int
v a r = i +++ i ;
This program compiles and is valid since the expression
i+++i
is well-formed.
How did the compiler interpret it? Well, first the compiler put parenthesis from
the operator priority rule:
(i++)+i
. Then it first evaluated this expression by
performing the post-incrementation
i++
(so that it returns 3 for this expression
but now
i
stores value 4). Finally, it adds to the value of
i
3 so that we get
3+4=7.
Even when a simple human-readable program compiles, it becomes complex
for humans to check whether the input fits all branching conditions. In other
words, are all input cases considered so that the program does not have to
notes.
5
Hackers love them.
Search WWH ::
Custom Search