Computability

Hi,

in literature you often find the statement that (concrete) program
semantics are in general not computable. If you for example consider so-
called "sticky collecting semantics", you want to compute different
properties of the program at particular program points. Let's say, I
would like to know which values all program variables might have at
program point P0. The naive approach would be to run the program with all
possible combinations of program input parameters. Of course, this would
take quite long, but the semantics remains computable.

The only issue I could imagine is that you get trouble with non-
terminating programs. If you can't guarantee that the input program
terminates, the semantics cannot be computed. Is this possibly the
reason why "program semantics is not computable in general"?

On the other hand, if the set of programs under analysis is restricted
to terminating programs, will the concrete program semantics be always
computable?

Best,
Tim
.

Relevant Pages

  • Re: Computability
    ... semantics are in general not computable. ... to terminating programs, will the concrete program semantics be always ... It is even pretty "fast" as the time needed to compute P_qis roughly proportional to x (plus some simulation overload you may have). ... The existence of universal programs and the fact that a program cannot decide whether it is "run directly" or "simulated by an universal machine" means that even if you try to circumvent this construction by adding extra condition such as "uniformly terminating programs that only manipulate uniformly terminating programs" or similar things you can embed the construction within several layers of universal machines and simulation and will still get undecidability. ...
    (comp.theory)
  • Re: Computability
    ... semantics are in general not computable. ... You can't even in principle test ... It's one reason. ... to terminating programs, will the concrete program semantics be always ...
    (comp.theory)