Re: Worst case execution time problem

"Hans-Bernhard Bröker" <HBBroeker@xxxxxxxxxxx> wrote in message
news:en3osl$qv8$01$1@xxxxxxxxxxxxxxxxxxxx
Christian Christmann wrote:

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?

Because _in_general_, it's even impossible to decide whether a given
program will *ever* finish. This is known as the Halting Problem, and its
impossibility was proven by Turing long before most of us were born.

I suspect that the OP posed a more general question than he intended ...

Hans, ... in general the problem is undecideable, but for most specific
practical examples in embedded work you can just examine all the branch
paths and loops and find a maximum.

The undecideability result doesn't apply to most practical applications that
occur in embedded systems.

http://en.wikipedia.org/wiki/Worst_case_execution_time

http://en.wikipedia.org/wiki/Halting_problem

http://en.wikipedia.org/wiki/Alan_Turing

---------

P.S.--Turing and von Neumann are legends.

http://en.wikipedia.org/wiki/Von_Neumann

There is the anecdotal story (a variation of it is here:

http://thesciencepundit.blogspot.com/2006/07/john-von-neumann-and-mathematicians.html

) that a reporter posed to von Neumann the classic bee-train problem at a
party. von Neumann was said to have thought for less than ten seconds
before replying with the answer. The reporter queried, "I guessed you used
the shortcut solution?". von Neumann answered, "What shortcut solution?"
(i.e. von Neumann had evaluated the infinite series in his head and it never
occurred to him to just take time before collision and multiply it times the
bee's speed).


.