Abstract

P′′ is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines.

Definition

formula_1 (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet formula_2, as follows:

Example program

Böhm gives the following program to compute the predecessor ("x"-1) of an integer "x" > 0:

which translates directly to the equivalent brainfuck program:

The program expects an integer to be represented in "bijective base-k" notation, with formula_38 encoding the digits formula_39 respectively, and to have formula_11 before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as formula_41, because 8 in bijective base-2 is 112.) At the beginning and end of the computation, the tape-head is on the formula_11 preceding the digit-string.