P′′

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

Определение[править | править код]

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

Синтаксис[править | править код]

1. R и λ — слова.
2. Если p и q — слова, то pq — слово.
3. Если q — слово, то (q) — слово.
4. Остальные последовательности символов не являются словами.

Семантика[править | править код]

1. {a0, a1, ..., an} (n ≥ 1) — алфавит бесконечной ленты (аналогичной ленте машины Тьюринга), a0 - пустой символ.
2. R — перенос головки ленты на одну ячейку вправо.
3. λ — заменить текущий символ ai на ai+1 (an заменяется на a0) и переместить головку на одну ячейку влево.
4. (q) — повторять операцию (операции) q, пока значение текущей ячейки не равно a0.
5. Операции выполняются слева направо в том порядке, в котором они записаны, до тех пор, пока справа ничего не останется.

Дополнительные факты[править | править код]

1. P′′ — первый полный по Тьюрингу язык программирования без оператора GOTO.
2. Команды языка Brainfuck (за исключением ввода и вывода) могут быть переведены на P′′ и обратно:

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (8 июня 2019)