Wiele probabilistycznych języków programowania zostało zbudowanych na spostrzeżeniu, że modele prawdopodobieństwa można zdefiniować za pomocą kodu wykonywalnego w dowolnym języku programowania, który zawiera źródło losowości. W przypadku takich modeli możliwe światy są śladami wykonania, a prawdopodobieństwo takiego śladu jest prawdopodobieństwem losowych wyborów wymaganych do zaistnienia tego śladu. Stworzone w ten sposób PPL dziedziczą całą moc ekspresji języka bazowego, w tym złożone struktury danych, rekurencję i, w niektórych przypadkach, funkcje wyższego rzędu. Wiele PPL jest w rzeczywistości uniwersalnych obliczeniowo: mogą reprezentować dowolny rozkład prawdopodobieństwa, z którego może pobrać próbkę probabilistyczna maszyna Turinga, która się zatrzymuje.