Definition of Turing Complete PPL

Hello everyone,

My task is to understand which probabilistic models can be defined using Edward. In the ICLR 2017 paper, it has been stated that Edward is a Turing Complete PPL. And the term is explained as “it supports any computable probability distribution”.[1]

Let’s make a categorization as follows,

1. Parametric

  • Directed Graphical Models

I think for Directed Graphical Models, one can specify a P(Child|Parents) from the set of parametric distributions (or you can write your own distribution) and selects the parametric distributions parameters as a function of its Parent Variables.

  • Undirected Graphical Models

In forum post [3], Dustin states that they have very limited support.
In forum post [4], Dustin mentions a method of sampling from an unnormalized distribution which I think may be related the undirected graphical models because the energy function is not normalized.

  • Models that Cannot be Represeated by Above Graphical Models

In [1], the authors state the existence of probabilistic programming languages which can even models that cannot be represented by Graphical Models.

2. Non-Parametric

It can model Bayesian Nonparametrics as stated in [2]. I think the example is the Gaussian Process.


I have previously posted a similar question on Gitter chat but couldn’t get a response. What are your opinions?

  • I think for directed graphs if the distribution is not defined using an if statement, it can model any parametric conditional distribution.
  • For the undirected graphs, I haven’t seen an example and would appreciate it.
  • For the models that are not representable by graphs, I’m wondering what can be an example of such a model. If you can give an example I would appreciate it.

Thanks in advance, I think since in Tensorflow Probability one can define a model using Edward language this post can help the users of Tensorflow Probability to understand its limits too.

[3] Hierarchical CRF
[4] Generate samples from an unnormalized distribution