Re: Worst case execution time problem


Christian Christmann wrote:
Hi,

in real-time systems the worst case execution time (WCET) is an important
issue. In the literature I found the statement that its calculation is
undecidable in general. Why? I appreciate any detailed explanations.

Perhaps an example will help.

Suppose you have a program something like the following pseudo-code:

max = 3

loop:

for x = 1 to max
for y = 1 to max
for z = 1 to max
for n = 3 to max
if x^n + y^n = z^n then print "Solution found" : stop
next n
next z
next y
next x
max = max + 1
goto loop

How long does this program take to run? Well, (assuming I've not made a
silly mistake) if you can work out whether it runs forever or not, you
have solved Fermat's Last Theorem, a tricky mathematical problem which
was not solved until about 350 years after it was stated. Different
programs can be written that would correspond to other mathematical
problems, some still unsolved. So you're not going to be able to come
up with a general solution.

Hope that helps.
Paul.

.