Это полицейские и грабители Задача основана на определении языков и доказательстве того, что они выполнены по Тьюрингу.
Это нить полицейских. Нить грабителей здесь .
Менты
Как полицейский, вы подготовите две вещи:
Формальная спецификация языка программирования или другой вычислительной системы. (Вычислительные системы определены ниже.)
Доказательство того, что ваша система является полной по Тьюрингу, согласно несколько более строгому определению, приведенному ниже.
Вы опубликуете свою спецификацию своего языка, и грабители попытаются «взломать» его, доказав его полноту по Тьюрингу. Если ваша заявка не была взломана в течение одной недели, вы можете пометить ее как безопасную и опубликовать доказательство. (Ваш ответ может быть признан недействительным, если кто-то обнаружит ошибку в вашем доказательстве, если вы не можете это исправить.)
Это Популярность-конкурсТаким образом, победителем будет тот ответ, который набрал наибольшее количество голосов, и который не был взломан или признан недействительным. Задача открыта - я не приму ответ.
Ради этой задачи вычислительная система будет определена как четыре вещи:
«Набор программ»
P
. Это будет счетно бесконечный набор, например, строки, целые числа, двоичные деревья, конфигурации пикселей в сетке и т. Д. (Но см. Техническое ограничение ниже.)«Входной набор»
I
, который также будет счетным бесконечным набором и не обязательно должен быть таким же, какP
(хотя это может быть).«Выходной набор»
O
, который аналогично будет счетным бесконечным набором и может или не может быть таким же, какP
илиI
Детерминированная, механистическая процедура для получения выходного сигнала
o
из программыp
и вводаi
, гдеp
,i
иo
являются членамиP
,I
иO
соответственно. Эта процедура должна быть такой, чтобы ее можно было в принципе реализовать на машине Тьюринга или другой абстрактной модели вычислений. Процедура может, конечно, не остановиться, в зависимости от программы и ее ввода.
Наборы P
, I
и O
должны быть такими , что вы можете выразить их в виде строк вычислимым образом. (Для наиболее разумных вариантов это не будет иметь значения; существует это правило, запрещающее вам выбирать странные наборы, такие как набор машин Тьюринга, которые не останавливаются.)
Полнота по Тьюрингу будет определяться следующим образом:
- Для любой вычислимой частичной функции
f
отI
кO
, существует программаp
вP
таким образом, что даноp
и входi
, выход ,f(i)
еслиf(i)
имеет значение. (В противном случае программа не останавливается.)
Слово «вычислимый» в приведенном выше определении означает «может быть вычислено с использованием машины Тьюринга».
Обратите внимание, что ни правило 110, ни битовая циклическая метка не являются полными по Тьюрингу по этому определению, поскольку они не имеют требуемой структуры ввода-вывода. Лямбда-исчисление является полным по Тьюрингу, пока мы определяем I
и O
будем использовать церковные цифры . (Это не полная по Тьюрингу, если мы берем I
и O
будем лямбда-выражениями вообще.)
Обратите внимание, что вам не нужно предоставлять реализацию вашего языка, но вы можете включить один из них в свой ответ, если хотите. Однако вы не должны полагаться на реализацию для определения языка каким-либо образом - спецификация должна быть завершена сама по себе, и если между спецификацией и реализацией существует противоречие, это следует рассматривать как ошибку в реализации.
Ответы:
Арифметика с завязанными глазами
Возможно, довольно простой язык для начала, условно говоря. (Существуют ограничения на то, насколько сложным может быть язык, потому что я должен доказать это по Тьюрингу - завершить сам!)
Для этого языка набор программ - это набор арифметических программ с завязанными глазами, как указано в разделе «Программа» ниже, входной набор - это набор натуральных чисел, а выходной набор - набор целых чисел (весь набор, а не только целые положительные числа).
Этот язык довольно интересен - возможно, даже практически полезен - потому что у него более или менее полное отсутствие потока управления, поскольку он полностью основан на вычислениях чисел, которые вы не видите. Это делает его потенциально полезным в качестве языка для реализации программ внутри гомоморфных систем шифрования .
Спецификация
Арифметика с завязанными глазами - это эзотерический язык программирования со следующими спецификациями:
Хранилище данных
Состояние работающей арифметической программы с завязанными глазами состоит из шести переменных, каждая из которых может хранить целое число. (Там нет никаких ограничений относительно того, как большие или малые эти числа можно получить, в частности, они могут пойти отрицательные.) Переменные называются
a
,b
,c
,d
,e
, иi
.В начале программы,
a
чтобыe
включено каждый инициализируются в 0, иi
инициализируются до положительного целого числа , взятого из пользовательского ввода. (Если вход недоступен,i
инициализируется 1.)Если программа прекращает выполнение (это может произойти только из-за деления на ноль), значение
i
непосредственно перед попыткой деления используется в качестве вывода программы.программа
Арифметическая программа с завязанными глазами - это список команд, каждая из которых имеет одну из следующих форм (где v можно заменить любым именем переменной, возможно, другим именем при каждом ее использовании):
=
v+
v=
v-
v=
v*
v=
v/
vОбратите внимание, что каждый операнд команд должен быть переменной; этот язык не позволяет использовать буквенные целые числа.
Выполнение программы выполняется путем последовательного запуска каждой из команд, а затем возврата к началу и продолжения последовательного запуска команд, до бесконечности (или до тех пор, пока не будет предпринята попытка деления на ноль, что завершает программу). ,
Каждая команда имеет ту же семантику, что и вы ожидаете от нотации, которая ничем не отличается от используемой в большинстве практических языков программирования: значения второй и третьей переменных, указанных в команде, взяты, арифметическая операция (сложение / вычитание) / умножение / деление соответственно для четырех форм команд) применяется к ним, и результирующее значение сохраняется в первой переменной. Деление здесь - это целочисленное деление с округлением до 0.
Нет никакого потока управления, кроме выхода из программы; Команды всегда чередуются последовательно, вплоть до деления на ноль (если оно есть) и завершения программы. В частности, нет возможности напрямую читать переменные, только использовать их в качестве источника вычислений, результаты которых влияют на значения, присвоенные другим переменным.
источник
i
так, чтобы номер состояния - который всегда будет "остановкой") - не будет быть частью результатов), но это достаточно близко, поэтому я не собираюсь отмечать это как безопасный, так как вы, несомненно, получите полный треск при достаточном времени и достаточном разъяснении правил. Я не хочу побеждать в этом соревновании по техническим вопросам.