摘要
Hoare logic is a logic used as a way of specifying semantics of programming languages, which has been extended to be a separation logic to reason about mutable heap structure. In a model M of Hoare logic, each program α induces an M-computable function fα M on the universe of M; and the M-recursive functions are defined on M. It will be proved that the class of all the M-computable functions fα M induced by programs is equal to the class of all the M- recursive functions. Moreover, each M-recursive function is ∑ 1 NM -definable in M, where the universal quantifier is a num- ber quantifier ranging over the standard part of a nonstandard model M.
Hoare logic is a logic used as a way of specifying semantics of programming languages, which has been extended to be a separation logic to reason about mutable heap structure. In a model M of Hoare logic, each program α induces an M-computable function fα M on the universe of M; and the M-recursive functions are defined on M. It will be proved that the class of all the M-computable functions fα M induced by programs is equal to the class of all the M- recursive functions. Moreover, each M-recursive function is ∑ 1 NM -definable in M, where the universal quantifier is a num- ber quantifier ranging over the standard part of a nonstandard model M.
