Java Reference
In-Depth Information
}
}
Godel
2
formally proved that there is
no
program that can decide whether or
not any given program entered as an argument will stop after a finite number
of instructions. Indeed, loosely speaking, suppose that we have at our disposal
a “special” Java program
Terminate(Prog)
that returns
true
if and only if
a program
Prog
terminates, and
false
otherwise. Then we could design the
following function:
public static void UndecidableProg()
{
while(Terminate(UndecidableProg))
{}
}
Does the function
UndecidableProg
terminate or not? If it terminates, then
Terminate(UndecidableProg)
is
true
, and the function loops forever, thus
not terminating. Or it does not terminate but
Terminate(UndecidableProg)
is
true
so that it terminates. This yields a contradiction. Note that Godel's
Proof of Incompleteness Theorem
3
is way beyond this informal sketch.
3.9 Exercises
Exercise 3.1 (Computing function values)
Write a function that computes
f
(
x
)=
√
x
+1 for
x
of type
double
.
Test this function in the
main
program function by displaying the result
of calling
f
(2) and
f
(3). Then use a
for
loop statement to display
f
(
i
)
for
i
∈{
0
, ...,
9
}
. Finally, modify this program to display
f
(
x
) for all
x
∈
[0
,
1) by increment of step size 0
.
1.
Exercise 3.2 (Power function and one of its properties)
Write a function
power
that takes two integer arguments
a
and
b
(with
b
0), and that returns the result
a
b
. The exponentiation
shall be computed by accumulating
b
multiplications. Then use this
exponentiation function in the
main
program to compute
a
b
for
a
and
b
given interactively by the user.
For
c
, a non-negative integer, we have the following property:
a
b
c
=
a
bc
.
Indeed, we have
a
b
c
=
e
c
log
a
b
≥
=
e
bc
log
a
=
a
bc
. Write a function
check
2
Kurt Godel (1906-1978).
Search WWH ::
Custom Search