П'' - P′′

П'' (P двойное простое^[1]) примитивный компьютер язык программирования сделано Коррадо Бём^[2][3] в 1964 году для описания семьи Машины Тьюринга.

Определение

${ textstyle { mathcal {P}} ^ { prime prime}}$ (здесь и далее написано П'') формально определяется как набор слов в алфавите с четырьмя инструкциями ${ textstyle {R, lambda, (,) }}$, следующее:

Синтаксис

1. ${ textstyle R}$ и ${ textstyle lambda}$ слова в P ′ ′.
2. Если ${ textstyle q_ {1}}$ и ${ textstyle q_ {2}}$ слова в P ′ ′, то ${ textstyle q_ {1} q_ {2}}$ - слово в P ′ ′.
3. Если ${ textstyle q}$ слово в P ′ ′, то ${ textstyle (q)}$ слово в P ′ ′.
4. Только слова, полученные из трех предыдущих правил, являются словами в P ′ ′.

Семантика

• ${ textstyle { Box, c_ {1}, c_ {2}, ldots, c_ {n} }}$ ленточный алфавит Машина Тьюринга с левой бесконечной лентой, ${ textstyle Box}$ будучи пустой символ, эквивалентный ${ textstyle c_ {0}}$.
• Все инструкции в P ′ ′ перестановки из набора ${ textstyle X}$ всех возможных конфигураций ленты; то есть все возможные конфигурации как содержимого ленты, так и положения головки.
• ${ textstyle alpha}$ это предикат говоря, что текущий символ не ${ textstyle Box}$. Это не инструкция и не используется в программах, а вместо этого используется для определения языка.
• ${ textstyle R}$ означает переместить головку ленты вправо на одну ячейку (если возможно).
• ${ textstyle lambda}$ означает заменить текущий символ ${ textstyle c_ {i}}$ с ${ textstyle с _ {(я + 1) { bmod {(}} п + 1)}}$, а затем переместите головку ленты на одну ячейку влево.
• ${ textstyle q_ {1} q_ {2}}$ означает функциональная композиция ${ textstyle q_ {2} circ q_ {1}}$. Другими словами, инструкция ${ textstyle q_ {1}}$ выполняется до ${ textstyle q_ {2}}$.
• ${ textstyle (q)}$ означает повторять ${ textstyle q}$ в пока цикл, с условием ${ textstyle alpha}$.

Отношение к другим языкам программирования

• P ′ ′ был первым »ИДТИ К без "императива" структурное программирование язык, который нужно доказать Полный по Тьюрингу^[2][3]
• В Brainfuck язык (помимо его команд ввода / вывода) является незначительной неформальной вариацией P ′ ′. Бём дает явные P ′ ′ программы для каждой из набора базовых функций, достаточных для вычисления любых вычислимая функция, используя только ${ textstyle (}$, ${ textstyle)}$ и четыре слова ${ textstyle r, r ^ { prime}, L, R}$ куда ${ textstyle г эквив лямбда р, г ^ { простое} экв г ^ {п}}$ с ${ textstyle r ^ {n}}$ обозначая ${ textstyle n}$th повторять из ${ textstyle r}$, и ${ textstyle L Equiv r ^ { prime} lambda}$. Это эквиваленты шести соответствующих команд Brainfuck. [, ], +, -, <, >. Обратите внимание, что поскольку ${ textstyle c_ {n + 1} Equiv c_ {0} Equiv Box}$, увеличивая текущий символ ${ textstyle n}$ раз будет повторяться так, чтобы в результате символ в текущей ячейке «уменьшился» на единицу (${ textstyle r ^ { prime}}$).

Пример программы

Бём^[2] дает следующую программу для вычисления предшественника (Икс-1) целого числа Икс > 0:

${ Displaystyle R (R) L (r ^ { prime} (L (L)) r ^ { prime} L) Rr}$

что переводится прямо в эквивалент Brainfuck программа:

>[>]<[−[<[<]]−<]>+

Программа ожидает, что целое число будет представлено в биективное основание-k обозначение, с ${ textstyle c_ {1}, c_ {2} ldots, c_ {k}}$ кодирование цифр ${ textstyle 1,2, ldots, k}$ соответственно, и иметь ${ textstyle Box}$ до и после строки цифр. (Например, в биективном основании-2 число восемь будет закодировано как ${ textstyle Box c_ {1} c_ {1} c_ {2} Box}$, потому что 8 в биективном основании-2 равно 112.) В начале и в конце вычислений магнитофон находится на ${ textstyle Box}$ перед цифровой строкой.

Рекомендации

Веб ссылки

• П''Онлайн-переводчик: Демонстрация итеративного 99 бутылок пива песня построена в 337568 П'' инструкции.