Обратите внимание: я готов дать вознаграждение за любой ответ, который мне кажется интересным.

Ваша задача состоит в том, чтобы спроектировать компьютер с полным набором инструкций по Тьюрингу (OISC):

OISC - это абстрактная машина, которая использует только одну инструкцию - избавляя от необходимости кода операции машинного языка. Благодаря разумному выбору одной инструкции и неограниченным ресурсам, OISC может быть универсальным компьютером так же, как традиционные компьютеры с несколькими инструкциями.

Вот несколько примеров отдельных команд, которые делают OISC-полный по Тьюрингу.

Правила:

Вы должны предоставить интерпретацию или доказательство этого

Вы должны предоставить переводчика для вашего языка. Этот интерпретатор должен быть ограничен только памятью / временем (например, он не должен иметь никаких ограничений, наложенных пользователем). Если вы не предоставляете переводчика для вашего языка (по любой причине, кроме лени), вы должны доказать, что он может быть написан. Переводчик должен быть возможным .

Вы должны доказать его Тьюринговую полноту

Вы должны приложить формальное доказательство того, что ваш язык завершен по Тьюрингу. Простой способ сделать это - доказать, что он может интерпретировать или иметь то же поведение, что и другой язык, полный по Тьюрингу. Основным языком для интерпретации будет Brainf ** k .

Например, обычный язык, который имеет все те же команды, что и Brainf ** k (и такое же отсутствие ограничений памяти, наложенных пользователем), является полным по Тьюрингу, потому что все, что может быть реализовано в Brainf ** k, может быть реализовано на языке ,

Вот список очень простых в реализации языков, полных тьюринга.

Дополнительные требования OISC

• Этот OISC должен иметь только одну инструкцию - он не может иметь несколько инструкций, одна из которых делает его выполненным по Тьюрингу.

• Ваш OISC может использовать любой синтаксис, который вам нравится. Вы должны определить в своем ответе, что такое инструкция, что такое данные, а что нет (например, пробел). Будь креативным!

• Аргументы не просто должны быть целыми числами. Например, /// является прекрасным примером OISC, полного по Тьюрингу.

• Как и если ввод и вывод взяты и даны, остается на ваше усмотрение. Большинство OISC реализуют ввод / вывод через определенные области памяти, но могут быть другие способы сделать это, и вам рекомендуется найти один из них.

• Правильный ответ должен содержать пример кода в вашем OISC, либо путем включения его в сообщение, либо с помощью ссылки на простую задачу, решаемую на языке.

голосование

Избиратели, пожалуйста, помните, чтобы не голосовать против скучных представлений. Примеры:

• Lenguage -эквиваленты
• Реализация существующего OISC (ответчики, пожалуйста, создайте свой собственный!)
• «OISC», в котором первый аргумент указывает команду для вызова ( пример )

Тем не менее, вы должны поддержать интересные, творческие материалы, такие как:

• OISC на основе математического уравнения
• Завершенный по Тьюрингу ZISC на основе нейронной сети
• OISC, в котором вывод ввода-вывода происходит другими способами, чем определенные области памяти

выигрыш

Как и в конкурсе популярности , ответ с наибольшим количеством голосов выигрывает! Удачи!

XOISC

Этот OISC основан на X-комбинаторе Фоккера, который определяется следующим образом:

$$X = \lambda f\ . f\ (\lambda g\ h\ x\ . g\ x\ (h\ x))\ (\lambda a\ b\ c\ . a)$$

Если мы признаем тот факт, что SKI-исчисление завершено по Тьюрингу, то вышеупомянутый комбинатор также завершается по Тьюрингу. Это потому , что S , K и I можно записать в терминах X , например:$X$$S$$K$$I$$X$

$$\begin{align} S &= X\ (X\ X) \\ K &= X\ X \\ I = S\ K\ K &= X\ (X\ X)\ (X\ X)\ (X\ X) \end{align}$$

Как работает XOISC

Внутренне XOISC имеет (изначально пустой) стек, оттуда инструкция, принимающая в качестве аргумента, делает следующее:$n$

• Вытяните элементов (функций f 1 … f N ) из стека, нажмите f 1 ( f 2 ( … ( f N X ) … ) $n$$f_1 \dots f_N$$f_1\ (f_2\ (\dots (f_N\ X) \dots ))$

Когда больше не осталось инструкций, XOISC поместит все аргументы командной строки (если они есть) в стек, например:

$$[ \underbrace{s_1, \dots,\ s_M}_{\text{stack before}} ,\ \underbrace{a_1, \dots,\ a_N}_{\text{arguments}} ]$$

Окончательный расчет будет .$(\dots ((\dots (s_1\ s_2) \dots)\ s_M)\ a_1) \dots) a_N$

---

Поскольку одна инструкция в XOISC принимает только один аргумент (смещение памяти), нет никаких оснований даже использовать имя для этой инструкции. Таким образом, допустимый исходный файл будет состоять только из целых чисел, разделенных символами новой строки или пробелами, как, например:

0 0 2 0 1 0 1

Попробуйте онлайн!

пример

Давайте возьмем приведенный выше пример (стек растет справа):

$$\begin{align} & \texttt{0} & \text{pop 0 and apply (ie. push single } X \text{)}: & \quad [X] \\ & \texttt{0} & \text{again simply push } X: & \quad [X,\ X] \\ & \texttt{2} & \text{pop 2 (} a,b \text{) and push } a\ (b\ X): & \quad [X\ (X\ X)] \\ & \texttt{0} & \text{simply push } X: & \quad [X\ (X\ X),\ X] \\ & \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X: & \quad [X\ (X\ X),\ X\ X] \\ & \texttt{0} & \text{simply push } X: & \quad [X\ (X\ X),\ X\ X,\ X] \\ & \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X: & \quad [X\ (X\ X),\ X\ X,\ X\ X] \end{align}$$

Наконец, оцените стек: или с меньшими скобками X ( X X ) ( X X ) ( X X ), который мы распознаем как старый добрый тождество S K K функция.$((X\ (X\ X))\ (X\ X))\ (X\ X)$$X\ (X\ X)\ (X\ X)\ (X\ X)$$S\ K\ K$

Полнота по Тьюрингу

Доказательство идеи

Чтобы XOISC был полным по Тьюрингу, мы должны иметь возможность переводить любое (допустимое) чередование скобок и комбинаторов. Это возможно, потому что при высовывании, применении и толкании это происходит ассоциативно справа (приложение-функция левоассоциативно).$X$

Для перевода любого такого выражения есть простой способ сделать это: всегда выдвигать столько элементов, чтобы с начала текущего уровня скобок оставался только один элемент.$X$

В качестве примера, ранее использовалось выражение: $((X\ (X\ X))\ (X\ X))\ (X\ X)$

• чтобы получить , нам просто нужно$X$0
• Затем мы находимся на новом уровне скобок, поэтому нам снова нужно только 0
• Теперь две круглые скобки закрыты, поэтому нам нужно добавить 2 элемента: 2
• снова мы находимся на новом уровне скобок, поэтому нам нужно 0
• две скобки, снова закройте 2
• и то же самое снова

Таким образом, мы получаем другую (но семантически эквивалентную) XOISC-программу:

0 0 2 0 2 0 2 Попробуйте онлайн!

Если мы будем придерживаться этой стратегии, мы можем легко преобразовать любое выражение, состоящее из комбинаторов, в программу XOISC, которая оставляет в стеке только одну функцию.$X$

Формальное доказательство

Учитывая, что SKI-исчисление завершено по Тьюрингу, нам нужно показать две вещи:

1. -combinator является основой для SKI-исчисления$X$
2. XOISC может представлять любое выражение, сформированное с помощью комбинатора $X$

Первая часть - доказательство трех равенств во введении - очень утомительна и занимает много места, а также не очень интересна. Таким образом, вместо того, чтобы поместить это в этот пост, вы можете найти здесь ^* .

Вторая часть может быть доказана структурной индукцией , хотя легче доказать немного более сильное утверждение: А именно, для любого выражения, образованного комбинаторами, существует программа, которая оставляет это выражение как одно выражение в стеке:$X$

Существует два способа построения такого выражения : либо само X , либо f g для некоторых выражений f и g :$X$$X$$f\ g$$f$$g$

Первый из них тривиален, так как 0оставит в стеке как одно выражение. Теперь предположим, что есть две программы ( F 1 … F N и G 1 … G K ), которые оставят f и g как одно выражение в стеке и докажут, что утверждение верно и для f g :$X$$\texttt{F}_1 \dots \texttt{F}_N$$\texttt{G}_1 … \texttt{G}_K$$f$$g$$f\ g$

Программа сначала сгенерирует f в стеке, а затем сгенерирует g, но вместо того, чтобы извлекать только части g, она также вытолкнет f и применит ее, такой, что он оставляет единственное выражение f g в стеке. ∎$\texttt{F}_1 \dots \texttt{F}_N\ \texttt{G}_1 \dots \texttt{G}_{K-1}\ (\texttt{G}_K + 1)$$f$$g$$g$$f$$f\ g$

переводчик

входные

Поскольку нетипизированное лямбда-исчисление требует, чтобы мы определяли наши собственные типы данных для всего, что мы хотим, и это громоздко, интерпретатор знает о церковных цифрах - это означает, что когда вы вводите входные данные, он автоматически преобразует числа в соответствующие им церковные цифры.

В качестве примера вот программа, которая умножает два числа: Попробуйте онлайн!

Вы также можете предоставить функции в качестве аргументов, используя индексы Де Брюина , например, Sкомбинатор \\\(3 1 (2 1))(или λλλ(3 1 (2 1))). Однако он также признает S, K, Iи, конечно же Xкомбинатор.

Выход

По умолчанию интерпретатор проверяет, кодирует ли выход целое число, если он это делает, он выведет соответствующее число (в дополнение к результату). Для удобства есть -bфлаг, который говорит интерпретатору попытаться сопоставить логическое значение (см. Последний пример).

ассемблер

Конечно, любой низкоуровневый язык нуждается в ассемблере, который преобразует в него высокоуровневый язык, вы можете просто использовать любой ввод (см. Выше) и преобразовать его в XOISC-программу, используя -aфлаг, попробуйте его онлайн! ^**

---

^{* Если ссылка не работает, в этом посте есть копия HTML-комментария.}

^{** Это приводит к программе, которая проверяет на простоту, попробуйте онлайн!}

Привлечь

Draw - это OISC, действующий на двумерной сетке, помечающий квадраты аналогично B-машине Wang. Однако, чтобы язык был как можно более простым и OISC-y, насколько это возможно, все инструкции (из которых всего один) отмечают квадрат, на который только что ступили, и, чтобы иметь возможность остановиться, наступают на отмеченный квадрат завершает программу

Программа состоит из последовательности строк, содержащих идентификатор строки (произвольная строка, не включая # или пробел), два целых числа ( xи y) и еще два идентификатора строки ( aи b).

Трассы программы выглядит следующим образом :
Начиная с линией идентифицированной как startс указателем , указывающим на позицию (0, 0), переместите указатель на величине заданной xи yи отметьте квадрат указатель находится теперь (если квадрат не уже отмечалось, в этом случае исполнение прекращается). Затем перейдите к строке, aесли хотя бы один из непосредственно смежных квадратов также помечен, и к строке в bпротивном случае.

Переводчикам рекомендуется выводить конечный результат таблицы как изображение, холст и т. Д.

Тьюринга Полнота

Draw завершен по Тьюрингу, так как в язык можно скомпилировать модифицированную версию (называемую Alternate) машины Minsky.

Альтернатива действует аналогично машине Мински с двумя счетчиками, но на команды накладывается большое ограничение: команды должны чередоваться для нацеливания на первый и второй счетчики. Чтобы обойти эту модификацию, дополнительная команда была добавлена: nop. Эта команда вообще не изменяет целевой счетчик, что позволяет «дополнять» последовательные изменения одним счетчиком, удовлетворяя ограничению, описанному выше. Это также означает, что регистр, который должен быть изменен, не должен быть задан и для любой данной инструкции может быть непосредственно получен вывод из инструкций, из которых выполнение может перейти к нему.

Пример: это минский аппарат

1 inc A 2
2 inc A 3
3 dec A 3 4
4 halt

превращается в эту альтернативную программу:

1 inc 2
2 nop 3
3 inc 4
4 nop 5
5 dec 6 8
6 nop 5
7 halt
8 halt

Это ограничение необходимо из-за способа, которым конечная программа Draw обрабатывает регистры, то есть она вообще не различает их. Вместо этого программа Draw просто копирует регистр, который не был изменен предыдущей инструкцией, изменяя его в соответствии с выполняемой инструкцией.

Затем альтернативная программа напрямую переводится в Draw следующим образом:

Программа начинается с этого блока.

start 0 0 a a
a 3 0 b b
b -3 1 c c
c 3 0 d d
d -3 2 e e
e 3 0 f f
f 3 -3 i1_a i1_a

inc, decИ nopпереводится почти так же, как друг с другом. Во всех случаях нет разницы между изменением первого или второго регистра (как объяснено выше). Вот приращение, эквивалентное inc 2:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 0 i2_z i2_y
i1_f 5 0 i2_z i2_y

Измените числа в i1_xчастях на индекс текущей инструкции, а в i2_xчастях на индекс следующей инструкции, которая будет выполнена.

nopИнструкция может быть переведена как таковые:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 -2 i2_z i2_y
i1_f 5 -2 i2_z i2_y

Это декремент:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 -2 i3_z i3_y
i1_f 5 -4 i2_z i2_y

i3_x относится к инструкции, которая будет вызвана, если счетчик уже равен 1.

Останов:

i1_y 0 0 0 0
i1_z 0 0 0 0

Измените метки соответствующим образом и просто соедините все вместе. Выполнение этого для примера сверху дает программу Draw в хранилище сверху.

интерпретаторы

В настоящее время есть два переводчика, оба написаны на Python. Их можно найти в репозитории Draw GitHub .

1. draw.py : этот интерпретатор предназначен для командной строки и принимает исходный код программы в качестве аргумента. После каждого шага выводится команда, которая была выполнена, и местоположение указателя команды; после остановки программы выводится количество отмеченных ячеек.
2. draw_golly.py : эта версия использует Golly для совершенно неправильной цели, облегчая графический вывод, беря исходный код через всплывающее окно при запуске скрипта. Golly может быть немного привередливым с Python, поэтому убедитесь, что у вас установлен Python 2 (и не смешивайте 32-битный Golly с 64-битным Python или наоборот). Вывод осуществляется через встроенную ячейку Golly.

Следующее изображение является примером для вывода из второго интерпретатора. Запуск примера программы в репозитории дает это (или подобное):

-3

Вот суть.

объем памяти

Память - это карта лент, где ключи - это строки, а значения - целые числа произвольного размера.

Кроме того, есть набор меток, на которые программа может перейти.

Существует стек, который содержит операнды, которые являются строками.

Существует предложение, которое контролирует, где в лентах памяти он может получить доступ.

Одна инструкция

-, Во-первых, он выталкивает строку LABELиз стека. Если LABELон не определен как метка, он определяет метку и очищает источник этой метки (то есть, откуда она была выдвинута) и текущую инструкцию. В противном случае он выполняет следующие вычисления, используя два верхних значения, Aи B:

if mem[A] < mem[B]:
    jump to LABEL
if mem[A] != mem[B]:
    mem[A]--
else:
    mem[B]++

Обратите внимание, что при наличии избыточных или недостаточных аргументов программа выдаст ошибку, показывая состояние программы.

Смещение может быть изменено путем доступа к значению ..

Пример кода

X-

i i X-
i i X-
i i X-
i i X-
i i X-
i i X-
i i X-

Это устанавливает переменную iв 7, приращением 7раз.

X-

i i X-
i i X-
i i X-
LOOP-
    a a X-
    a a X-
    j i LOOP-

Это умножается i+1на константу 2.

Доказательство полноты по Тьюрингу

Независимо от размеров int в C ++ (то есть, предполагая, что они бесконечны), -3 - это Turing Complete путем сокращения до 3-клеточного мозгового отвращения . Я могу пренебречь этим размером, потому что на компьютере с бесконечной памятью, имеющей произвольно большие ячейки, можно написать интерпретатор для -3.

Я также считаю, что любой BCT может быть записан как программа -3.