Определение того, является ли язык полным по Тьюрингу, очень важно при разработке языка. Это также довольно трудная задача для многих эзотерических языков программирования, но давайте поднимем ее на ступеньку выше. Давайте создадим некоторые языки программирования, которые так трудно доказать в Turing Complete, что даже лучшие математики в мире не смогут их доказать в любом случае. Ваша задача - разработать и реализовать язык, полнота которого по Тьюрингу зависит от основной нерешенной проблемы математики .
правила
Выбранная вами проблема должна быть поставлена не менее 10 лет назад и должна быть нерешенной на момент публикации этого вопроса. Это может быть любая доказуемая гипотеза в математике, а не только одна из перечисленных на странице Википедии .
Вы должны предоставить спецификацию языка и реализацию на существующем языке.
Язык программирования должен быть завершен по Тьюрингу тогда и только тогда, когда гипотеза верна. (или если и только если гипотеза не верна)
Вы должны приложить доказательство того, почему оно будет полным или неполным по Тьюрингу на основе выбранной гипотезы. Вы можете получить доступ к неограниченной памяти при запуске интерпретатора или скомпилированной программы.
Поскольку нас интересует Тьюринг-полнота, ввод-вывод не требуется, однако цель состоит в том, чтобы сделать наиболее интересный язык, чтобы он мог помочь.
Это конкурс популярности, поэтому победит ответ с наибольшим количеством голосов.
Целевые критерии
Что должен сделать хороший ответ? Вот некоторые вещи, на которые нужно обратить внимание при голосовании, но они не являются технически необходимыми
Это не должно быть простым патчем существующего языка. Изменение существующего языка в соответствии со спецификациями - это хорошо, но исправление условий не рекомендуется, потому что это скучно. Как сказано в ais523 в байте Nineteeth:
Я предпочитаю делать уловки моих эсолангов более прочно запеченными в язык
Это должно быть интересно как самостоятельный эзотерический язык.
источник
Ответы:
Лежандра
Этот язык полон по Тьюрингу только тогда и только тогда, когда гипотеза Лежандра ложна, т. Е. Существует целое число n> 0, такое, что между n ^ 2 и (n + 1) ^ 2 нет простых чисел. Этот язык черпает вдохновение из Underload, хотя в некоторых отношениях он сильно отличается от него.
Программы в Legendre состоят из ряда натуральных чисел (0 особенно запрещено, потому что оно по существу сводит на нет всю цель языка). Каждое целое число соответствует базовой команде в Legendre или потенциальной пользовательской команде. Для какой команды она назначена, зависит от числа простых чисел между ее квадратом и следующим целым числом (эквивалентно последовательности OEIS A014085 ).
Команды языка модифицируют стек, который может содержать произвольно большие положительные целые числа. Если в стеке хранится 0, 0 сразу удаляется. Подробно, команды:
2 (наименьшее целое число, производящее эту команду: 1): поместите следующее целое число в программе в стек.
3 (наименьшее производящее целое число: 4): вставьте верхнее целое в стек и выполните связанную с ним команду.
4 (наименьшее: 6): выведите верхнее целое число. Если это было 1, увеличьте верхнее целое число в стеке.
5 (10): поменяйте местами два верхних стека.
6 (15): уменьшить верхнее целое в стеке. Если это приводит к 0, вытолкните 0 и отбросьте его.
7 (16): дублировать верхнее целое число в стеке.
8 (25): остановить выполнение и распечатать содержимое стека.
Это базовый набор команд, который не может делать ничего интересного, не говоря уже о цикле. Однако есть другая команда, к которой можно получить доступ, только если гипотеза Лежандра окажется ложной.
Если эта команда каким-то образом доступна, язык становится тьюрингово-полным, так как в ней можно смоделировать машину Минского.
Когда команда 8 выполняется или достигнут конец программы, программа завершается и печатается символ (Unicode), соответствующий каждому целому числу в стеке.
Примеры программ
Эта простая программа вводит число 2, затем 3 и, наконец, 10, прежде чем выполнить 4 (команда: 3), что приводит к выталкиванию и выполнению 10 (команда: 5), меняя местами 2 и 3.
Эта программа демонстрирует использование косвенного целочисленного соответствия между командами. Сначала нажимают 5, затем 15 и 1, используя три разных способа кодирования команды 2. Затем 1 выталкивается, и в результате 15 увеличивается до 16 и, наконец, выполняется. Программа заканчивается двумя экземплярами числа 5 в стеке.
Эта программа демонстрирует использование команды 0, используя? в качестве номера заполнителя. Программа сначала сохраняет «1 5» в функции 9, затем «15 31» в 10, прежде чем запустить функцию 9 (используя 24), которая помещает 5 в стек и многократно уменьшает его, пока не достигнет 0 и не будет удалена , Затем программа останавливается.
Минский автомат
Чтобы преобразовать машину Минского в код Legendre, необходимо использовать команду 0 . Поскольку эта команда недоступна, если гипотеза Лежандра не ложна, я использовал заполнитель? вместо.
Обратите внимание, что все имена строк машинных команд Minsky должны иметь целые числа с различными соответствиями A014085 друг от друга и базовых команд, а также 24 (9) и 31 (10).
Инициализация: x INC (A / B) y:A:
B:
x ДЕК (A / B) yz:A:
B:
х ОСТАНОВКА:Чтобы создать конечную программу, добавьте все части (с заменой x, y, z их аналогами) и добавьте одно целое число, чтобы запустить первую инструкцию в цепочке. Это должно доказать полноту по Тьюрингу языка в случае, если гипотеза Лежандра окажется контрпримером ложной.
переводчик
Этот интерпретатор написан на Python (3) и был протестирован на всех трех приведенных выше примерах. Используйте флаги -a / - allowZero, чтобы разрешить? -f / - file для запуска кода непосредственно из файла и -s / - stackOut для вывода стека в виде списка Python. Если файл не указан, интерпретатор входит в режим REPL, который лучше всего использовать с --stackOut.
источник
Союз закрыт
Этот язык программирования является полным по Тьюрингу, если гипотеза о замкнутых множествах неверна.
управления
Список команд:
x ++ Увеличение x (INC)
x-- Уменьшение x (DEC)
j (x, y) Добавить набор инструкций x, если y равно 0, до конца очереди инструкций
Все переменные инициализируются как 0
Синтаксис
Программы написаны в виде набора наборов команд.
Команда1 Команда2 Команда3 ... Команда1 Команда2
...
...
Для определения, является ли программа закрытой объединением, каждый набор учитывает только список различных команд, которые находятся в наборе
j (x, y)! = J (a, b)
+ (x)! = + (Y)
Если какой-либо тип команды (+, -, j) присутствует хотя бы в половине наборов, он ничего не делает.
Программы могут завершиться, если в конце очереди команд нет инструкций
Бесконечные циклы, включая пустой цикл, могут быть достигнуты с помощью j (x, y)
переводчик
Показать фрагмент кода
Полнота по Тьюрингу
Если все три команды, j (x, y), увеличивают, уменьшают, все команды доступны, то есть машина Minsky может быть смоделирована.
Любой набор только с j (x, y), который достигается с помощью j (x, y), равен HALT
x ++, равен INC
x--, DEC
j (x, y) равен JZ
Если гипотеза объединения замкнутых множеств верна, то по крайней мере одна из трех команд всегда будет отключена, что сделает невозможным выполнение этого языка по Тьюрингу.
источник
Ферма простые числа
Язык работает на двух потенциально бесконечных лентах, где каждое местоположение ленты может хранить произвольное целое число. Обе ленты заполняются
-1
при запуске. Есть также две головки ленты, которые начинаются в позиции 0 на обеих лентах.Интерпретатор сначала прочитает ввод и сохранит значения на первой ленте (данных), начиная с позиции 0.
Затем он будет читать предоставленную программу. Для каждого встречаемого числа сначала проверяется, является ли значение простым числом Ферма или нет. Если да, он записывает на вторую (командную) ленту, какое это простое число Ферма, в противном случае он записывает
-1
на ленту с инструкциями.Затем проверьте значение в указателе инструкций и выполните одно из следующих действий:
-1
или меньше: выход из программы0
: Переместите позицию ленты данных на одну влево. Переместить ленту инструкций на одну позицию вправо1
: Переместите ленту данных на одну позицию вправо. Переместить ленту инструкций на одну позицию вправо2
: Увеличить значение в позиции ленты данных. Переместить ленту инструкций на одну позицию вправо3
: Уменьшить значение в позиции ленты данных. Переместить ленту инструкций на одну позицию вправо4
: Если значение в текущей позиции ленты данных равно нулю, перемещайте ленту инструкций вправо, пока не достигнете соответствующего5
(или большего) значения на ленте инструкций или чего-то меньшего, чем0
. Если он5
(или больше), переместите указатель инструкции еще раз вправо, если он меньше, чем0
выйдите из программы. Если значение текущей позиции ленты данных не равно нулю, просто переместите ленту инструкций вправо5
или больше: перемещайте указатель инструкций влево, пока не достигнете соответствующего4
значения или не найдете что-то меньше0
. В последнем случае выйдите из программы.(путем сопоставления
5
(или более) и4
значений это означает, что при поиске правильного значения на ленте инструкций в любое время, когда он встречает то же значение, что и исходная команда (либо5
(или более), либо4
)), ему придется пропустить соответствующее число другого значения (4
или5
(или более) соответственно) в поиске)Цикл, пока инструкция не говорит, что вы должны выйти из программы.
Когда программа завершает работу, выводите значения на ленте данных с позиции
0
до первой позиции на ленте, содержащей-1
значение.доказательство
Обратите внимание, что язык по существу соответствует интерпретатору Brainfuck без ввода-вывода, где
F_5
требуется, чтобы он мог выполнять любые правильные циклы.Однако на основе простой гипотезы Ферма есть только 5 простых чисел Ферма (
F_0
-F_4
). ЕслиF_5
существует, то язык полный по Тьюрингу, поскольку мы знаем, что Brainfuck является полным по Тьюрингу. Однако безF_5
вас не обойдется ни ветвление, ни зацикливание, по сути, блокирование вас в очень простых программах.Реализация
(протестировано с ruby 2.3.1)
Примеры:
Это напишет
H
(сокращенноHello World!
) на экран с новой строкой:Сохраните как
example.fermat
и запустите его так (примечание: вы всегда должны иметь данные):В следующем примере мы сделаем простой шифр в стиле Цезаря, увеличив каждое значение на единицу. Вы, очевидно, должны заменить
?
на 5-е простое число Ферма:Вы можете попробовать, что он работает, включив чит-режим и используя
2 4 1 2 5 3
в качестве исходного кода:источник
5
. Надеюсь у них хорошая клавиатура.Ласточки с кокосом v2
Поскольку в предыдущей версии были ошибки, которые сделали ее недействительной для этого конкурса, и я не хочу, чтобы количество голосов предыдущей версии для этой версии значительно отличалось, эта версия представляется как новое сообщение.
Этот язык не является полным по Тьюрингу, если гипотеза Коллатца может быть доказана для всех натуральных чисел. В противном случае язык Тьюринга завершен.
Этот язык был основан на кардинал .
Во-первых, управление программой рассчитывается по формуле
contVal = sum (сумма (значения ASCII строки) * 2 ^ (номер строки-1))
Затем в каждой точке A или E создаются 2 ласточки, движущиеся в противоположных направлениях, и все операторы условного поворота устанавливаются для ожидания инициализации.
Ласточки, созданные в E, направляются влево / вправо, а ласточки, созданные в A, направляются вверх / вниз.
Наконец, код будет выполнять шаги, пока все указатели не будут удалены или контроль не упадет до одного.
На каждом шаге, если contVal% 2 == 0, он будет делиться на 2, в противном случае он будет умножен на три и увеличен на единицу.
Команды:
0: установить значение 0
+: увеличить значение на 1
>: изменить направление вправо
v: изменить направление вниз
<: изменить направление влево
^: изменить направление вверх
R: последующие указатели после первого указателя сравниваются со значением первый указатель Если равны, идите прямо, иначе поверните направо.
L: последующие указатели после первого указателя сравниваются со значением первого указателя. Если равны, идите прямо, иначе поверните налево.
E: Дублировать указатель, но в направлениях влево и вправо
A: Дублировать указатель, но в направлениях вверх и вниз
? : Удалить указатель, если значение равно 0
Показать фрагмент кода
Объяснение:
Если гипотеза Коллатца может быть доказана для всех натуральных чисел, длительность любой программы, выполняемой на этом языке, конечна, так как contVal всегда будет сходиться к 1, тем самым завершая программу.
В противном случае мне просто нужно доказать, что этот язык может реализовывать следующие функции
Инкремент: который представлен +
константой 0: который представлен 0
Доступ к переменной: переменные сохраняются в виде указателей при их перемещении.
Конкатенация операторов: изменяя расстояние, пройденное до операций, можно изменить порядок выполнения операций.
Цикл For: На этом языке
будет действовать как цикл for> count до 1 (дальнейший код может быть добавлен в цикл)
Точно так же код
Будет действовать до тех пор, пока не станет равным условному значению, заданному в цикле R.
источник
contVal
на каждом шаге (и, следовательно, если гипотеза верна, бесконечных циклов нет), но я не вижу этого явно сформулированного где-либо в ответе. ??Совершенство / Несовершенство
Вот это было весело.
Совершенство / Несовершенство завершается только при наличии бесконечных совершенных чисел. Если есть, это называется Совершенство, а если нет, это называется Несовершенство. Пока эта тайна не разгадана, она держит оба имени.
Совершенное число - это число, сумма делителей которого равна числу, поэтому шесть - это идеальное число, потому что
1+2+3=6
.Совершенство / Несовершенство имеет следующие функции:
Совершенство / Несовершенство основано на стеке, с индексированным стеком.
Команды:
p(x, y)
: выталкивает x в стек в y-й позиции.z(x, y)
: выталкивает x в стек в y-й позиции, избавляется от того, что было ранее в y-й позицииr(x)
: удаляет x-й элемент из стекаk(x)
: возвращает x-й элемент в стекеa(x, y)
: добавляет х и у. При использовании со строками он складывает их в порядке xy.s(x, y)
: вычитает у из х. со строками, удаляет последний len (y) из xm(x, y)
: умножает x и y. Если используется со строками, умножается в x раз на len y.d(x, y)
: делит х на уo(x)
: печатает хi(x, y)
: если x имеет значение true, тогда он выполняет функцию yn()
: возвращает счетчик, на котором вызывается кодовый блок.q()
: возвращает длину стекаt()
: пользовательский вводe(x, y)
: Если x является целым числом, если x и y имеют одно и то же значение, то это возвращает 1. Если y является строкой, то она получает длину y. если x является строкой, то он преобразует y в строку и проверяет, совпадают ли они, и, если они есть, возвращает 1. В противном случае возвращается 0.l(x, y)
: если x больше, чем y, он возвращает 1. Если есть строка, то она использует длину строки.b()
: останавливает программу.c(x, y)
: работает x, затем y.Чтобы получить эквивалент Python
and
, умножьте два значения вместе. Дляor
, добавьте значения, и дляnot
, вычтите значение из 1. Это работает, только если значение равно 1 или 0, что может быть достигнуто путем деления числа на себя.Типы данных: целые числа и строки. Строки обозначены
''
, а все нецелые числа округлены.Синтаксис:
Код состоит из вложенных функций внутри десяти
{}
с. Например, программа , которая получит на входы и распечатать их добавили бы:{o(a(t(), t()))}
. На заднем плане программы есть счетчик, который начинается с 0 и прогрессирует на 1 каждый раз, когда он выполняет блок кода. Первый блок кода работает в0
и так далее. После выполнения десяти кодовых блоков шестой выполняется каждый раз, когда счетчик достигает идеального числа. Вам не нужно иметь все десять блоков кода для работы программы, но вам нужно 7, если вы хотите сделать цикл. Чтобы лучше понять , как работает этот язык, запустите следующую программу, которая печатает счетчик каждый раз , когда счетчик достигает совершенное число:{}{}{}{}{}{}{o(n())}
.Переводчик можно найти здесь: repl.it/GL7S/37 . Либо выберите 1 и введите свой код в терминале, либо вставьте код на
code.perfect
вкладке и выберите 2 при запуске. Это будет иметь смысл, когда вы попробуете это.Доказательство полноты по Тьюрингу / отсутствие полноты по Тьюрингу.
Согласно этой статье об обмене стеками разработки программного обеспечения , завершение Тьюринга должно иметь возможность условного повторения перехода и иметь возможность чтения или записи в память. Он может считывать / записывать память в виде стека и выполнять цикл из-за того, что 6-й кодовый блок выполняется каждый раз, когда счетчик достигает идеального числа. Если существует бесконечное число совершенных чисел, оно может бесконечно зацикливаться и является полным по Тьюрингу, в противном случае это не так.
Интерпретатор Self Bitwise Cyclic Tag, который принимает 5 символов, 1 или 0, в качестве входных данных:
Его можно расширить, чтобы принимать любое количество символов в качестве входных данных. Это может занять бесконечный ввод, но только если есть бесконечные совершенные числа!
источник
Подошвы
Этот язык программирования является полным по Тьюрингу, если гипотеза Шольца верна.
Я написал этот язык, потому что @SztupY говорил, что не будет никаких результатов, которые полагаются на гипотезу, чтобы быть правдой, чтобы быть завершенным по Тьюрингу
Список команд
С помощью этих команд этот язык может симулировать машину Минского.
переводчик
Я очень рекомендую не запускать это. Он использует чрезвычайно медленный метод проверки цепочки сложений.
Показать фрагмент кода
Полнота по Тьюрингу
В языке используется счетчик количества запускаемых команд, который он проверяет на соответствие гипотезе Шольца, чтобы изменить полноту тьюринга языка.
Если гипотеза Шольца верна, эта программа работает точно так же, как обычная машина Минского, с
инкрементным
скачком уменьшения
при нулевой
остановке
Однако, если гипотеза Шольца ложна, счетчик в конечном итоге достигнет значения, для которого гипотеза Шольца не верна. Поскольку язык предназначен для выхода при достижении числа, для которого гипотеза Шольца ложна, программа будет выходить каждый раз после выполнения такого количества команд. Поэтому все программы будут иметь ограниченную длину. Поскольку это не соответствует требованиям, предъявляемым к языку, который должен быть завершен по Тьюрингу,
язык не будет полным по Тьюрингу, если гипотеза Шольца будет ложной
источник
Обрученные
Обрученный Гитхуб .
Файл readme и спецификация находятся на github, в разделе "README.txt".
Как правило, программа обручения состоит из пар линий, длина которых представляет собой отдельные пары с двумя простыми числами или пары с обручением (дубликатов быть не может). Программа выполняется путем поиска «гибких подмножеств» первой строки в паре во второй строке. Количество таких подмножеств в сочетании с левенштейновым расстоянием между исходной второй строкой и второй строкой без податливых подмножеств определяют команду для выполнения.
Я приведу выдержку из этого поста:
источник
b
. Это интерпретирует программу BF, которая помещается после нее, напримерb+++++.
. Размер программы, однако, ограничен 10 символами. Хотя он может интерпретировать BF, он не может вычислить все программы, которые может использовать машина Тьюринга.Дружное соотношение
Этот язык основан на том, существуют ли какие-либо дружные числа с противоположной четностью .
команды
Контроль потока
Программа циклически повторяется слева направо, а затем возвращается к началу. Если он встречает «j», он проверяет значение, чтобы определить, следует ли ему менять строки. Если число является дружественным числом с четностью, противоположной его совпадению, оно уменьшается на одну строку (возвращаясь к началу). В противном случае, если число является дружественным числом, оно поднимается на одну строку, если его еще нет в верхней строке.
Программа может завершиться только в том случае, если программа достигает x в любом ряду за пределами верхнего ряда.
Полнота по Тьюрингу
Эта программа может использоваться для моделирования машины Минского, предполагая, что есть пара дружных чисел с противоположной четностью.
j, {и} можно использовать для имитации JZ (r, x), хотя он будет проверять наличие дружных чисел, а не нуля.
+ - это INC (r)
- это DEC (r)
x - это HALT
Если вы не можете покинуть первый ряд, команды x и} ничего не делают. Это приводит к тому, что программа не может войти в состояние HALT, если она не является пустой программой. Следовательно, согласно описанию, что для полноты по Тьюрингу требуется состояние HALT , язык будет неполным по Тьюрингу.
переводчик
Показать фрагмент кода
источник
Новая линия
Отказ от ответственности: это немного беспорядок и довольно просто. Это первый язык, который я когда-либо писал, и гипотеза - единственная, которую я понял. Я знаю, что у другого пользователя был более длинный ответ с тем же, но я все равно решил написать это.
Чтобы писать в Newline, у вас должно быть много времени и новых строк (
\n
). Это работает на основе гипотезы Лежандра. Каждый оператор должен попадать в число в гипотезе Лежандра, которое мы начинаем с n = 1. Каждый раз, когда у вас есть оператор, вы берете количество \ n и вставляете его в гипотезу Лежандра и получаете диапазон, следующий за следующим простым числом \ n должны войти. Итак, для начала\n\n
вы переходите к оператору, а\n
затем к другому оператору, мы находимся на 3 новых строках. Теперь следующий - это 5, так что вы добавляете\n\n
и включаете оператор, чтобы убедиться, что последняя строка оператора имеет правильное количество новых строк, что вы находитесь на простом количестве, которое попадает в гипотезу Лежандра, которую мы начали.Числа (массив) похожи на переменные. Каждый раз, когда оператор запускается (использует числа), он увеличивается.
Пока у нас есть неограниченное число простых чисел, которые следуют правилам, этот язык имеет бесконечную ленту.
Минский автомат
Как это устроено:
Попробуйте это на KhanAcademy .
источник
Taggis
Taggis - это язык, основанный на системах тегов .
Тьюринговая полнота Таггиса основана на гипотезе Коллатца
Синтаксис
Синтаксис программы Taggis - это просто три строки (производственные правила), состоящие полностью из букв a, b и c, разделенных пробелами.
выполнение
Единственное состояние программы Taggis - это строка, состоящая из тех же трех символов.
Taggis реализует систему тегов TS (3, 2), в которой на каждом шаге удаляются первые 2 буквы текущего «тега», а к самой первой букве, которая была в этой удаленной части, добавляется соответствующее производственное правило, добавляемое в конец строка.
Например, программа Taggis
bc a aaa
реализует задачу 3n + 1, где итерации представлены соответствующим числомa
s, а шаг 3n + 1 заменяется на (3n + 1) / 2 [1], что приводит к выводу программы:Полнота по Тьюрингу
Конечно, эта простая система может показаться слишком простой, чтобы эмулировать полноту Тьюринга, но оказывается, что любая машина Тьюринга с 2 символами (класс, включающий универсальные машины) может быть преобразована в систему тегов с 2 удаленными символами из головы, и 32 * m правил производства, где
m
число состояний в машине Тьюринга.Наименьшая известная универсальная машина Тьюринга, содержащая только 2 символа, использует 18 состояний, и, следовательно, соответствующая система тегов содержит колоссальные 576 правил производства [2].
Однако вычислительный класс множества всех систем тегов с 3 продукцией и 2 удаленными символами связан с гипотезой Коллатца [2]. Если гипотеза Коллатца окажется ложной, то Таггис полон по Тьюрингу. Иначе, это основано на ДРУГОЙ нерешенной проблеме в математике, находя меньшую машину Тьюринга, чем
что эквивалентно исходной функции Коллатца, так как 3n + 1 нечетного
n
всегда будет четным, и, следовательно, деление может быть применено автоматическиСистемы тегов и коллатц-подобные функции, Liesbeth De Mol ,
источник