We study the expressive power of subrecursive probabilistic higher-order calculi. More specifically, we show that endowing a very expressive deterministic calculus like Godel's T with various forms of probabilistic choice operators may result in calculi which are not equivalent as for the class of distributions they give rise to, although they all guarantee almost-sure termination. Along the way, we introduce a probabilistic variation of the classic reducibility technique, and we prove that the simplest form of probabilistic choice leaves the expressive power of T essentially unaltered. The paper ends with some observations about the functional expressive power: expectedly, all the considered calculi capture the functions which T itself represents, at least when standard notions of observations are considered.
On Higher-Order Probabilistic Subrecursion / Flavien Breuvart; Ugo Dal Lago; Agathe Herrou. - In: LOGICAL METHODS IN COMPUTER SCIENCE. - ISSN 1860-5974. - ELETTRONICO. - 17:4(2021), pp. 25.1-25.35. [10.46298/lmcs-17(4:25)2021]
On Higher-Order Probabilistic Subrecursion
Ugo Dal Lago;
2021
Abstract
We study the expressive power of subrecursive probabilistic higher-order calculi. More specifically, we show that endowing a very expressive deterministic calculus like Godel's T with various forms of probabilistic choice operators may result in calculi which are not equivalent as for the class of distributions they give rise to, although they all guarantee almost-sure termination. Along the way, we introduce a probabilistic variation of the classic reducibility technique, and we prove that the simplest form of probabilistic choice leaves the expressive power of T essentially unaltered. The paper ends with some observations about the functional expressive power: expectedly, all the considered calculi capture the functions which T itself represents, at least when standard notions of observations are considered.File | Dimensione | Formato | |
---|---|---|---|
lmcs2021.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
816.86 kB
Formato
Adobe PDF
|
816.86 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.