On the Hardness of Almost-Sure Termination

This paper considers the computational hardness of computing expected outcomes and deciding (universal) (positive) almost-sure termination of probabilistic programs. It is shown that computing lower and upper bounds of expected outcomes is $Σ_1^0$- and $Σ_2^0$-complete, respectively. Deciding (universal) almost-sure termination as well as deciding whether the expected outcome of a program equals a given rational value is shown to be $Π^0_2$-complete. Finally, it is shown that deciding (universal) positive almost-sure termination is $Σ_2^0$-complete ($Π_3^0$-complete).

No reviews yet.

No comments yet.