Для $U=\mathbf{N}$ это следует из существования универсальных машин Тьюринга, а в общем случае — из тезиса Чёрча. Хорошо известно, что универсальная машина для вычисления функций $k$ аргументов получается выбором подходящей функции $k+1$ аргументов и объявлением первого аргумента переменной частью программы. Тогда $P$ в этом случае состоит из пар $(q, m)$, где $q$ — фиксированная программа $(k+1)$-местной универсальной функции (оборудования), а $m$ — мир, записанный на ленте (программное обеспечение).