P′′

P′′ — низькорівнева мова програмування, яку створив 1964 року Коррадо Бьом.

Визначення P′′ формально визначено як набір слів алфавіту з 4 інструкцій {R, λ, (, )} так:

Синтаксис

R і λ — слова. Якщо p і q — слова, то pq — слово. Якщо q — слово, то (q) — слово. Решта послідовностей символів не є словами.

Семантика

{a0, a1, ..., an} (n ≥ 1) — алфавіт нескінченної стрічки (аналогічної стрічці машини Тюрінга), a0 — порожній символ. R — перенесення головки стрічки на одну клітинку вправо. λ — замінити поточний символ ai на ai+1 (an замінюється на a0) і перемістити головку на одну клітинку вліво. (q) — повторювати операцію (операції) q, поки значення поточної комірки не дорівнює a0. Операції виконуються зліва направо в порядку їх запису, поки справа нічого не залишиться.

Додаткові факти

P′′ — перша повна за Тюрінгом мова програмування без оператора GOTO. Команди мови Brainfuck (за винятком введення і виведення) можна перекласти на P′′ і навпаки:

BrainfuckP′′>R<L=r'λ+r=λR-r'=rrrrr...rr (n разів)[(])