Побег с брезента (Копы)

9

Это Задача основана на определении языков и доказательстве того, что они выполнены по Тьюрингу.

Это нить полицейских. Нить грабителей здесь .

Менты

Как полицейский, вы подготовите две вещи:

  • Формальная спецификация языка программирования или другой вычислительной системы. (Вычислительные системы определены ниже.)

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

Вы опубликуете свою спецификацию своего языка, и грабители попытаются «взломать» его, доказав его полноту по Тьюрингу. Если ваша заявка не была взломана в течение одной недели, вы можете пометить ее как безопасную и опубликовать доказательство. (Ваш ответ может быть признан недействительным, если кто-то обнаружит ошибку в вашем доказательстве, если вы не можете это исправить.)

Это Таким образом, победителем будет тот ответ, который набрал наибольшее количество голосов, и который не был взломан или признан недействительным. Задача открыта - я не приму ответ.

Ради этой задачи вычислительная система будет определена как четыре вещи:

  • «Набор программ» 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будем лямбда-выражениями вообще.)

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

Натаниель
источник
9
Извините, ребята, но популярность - это объективный критерий победы. Быть поп-мошенником - не проблема не по теме, и никогда не было. В последней мета-дискуссии было достигнуто согласие +27 в пользу этого, поэтому, хотя пятеро из вас, возможно, предпочли бы, чтобы оно было другим, у вас действительно нет никакой ноги, чтобы стоять на нем. Поскольку этот вопрос был закрыт против согласованной политики, я прошу его вновь открыть.
Натаниэль
2
(обратите внимание, что WhatWizard закрыл его по другой причине.)
user202729
2
Пожалуйста, не используйте закрытые голоса в качестве кнопки «Я не согласен» или «Мне не нравится это». Близкие голоса должны использоваться для обеспечения соблюдения политики сайта. Если вы не согласны с политикой, отнеситесь к ней мета - не закрывайте проблемы, которые обсуждаются по общему согласию сообщества.
Mego
1
@Mego Я проголосовал за то, чтобы закрыть это как слишком широкое, но я также думаю, что это не по теме нашими существующими правилами для поп-минусов. Мы ожидаем, что конкурсы популярности будут иметь «четкую спецификацию цели, которая должна быть достигнута», этот вопрос является наиболее креативным. Мне ясно, что нет другой цели, кроме как получить правильный ответ, и что тег pop-con прикреплен только для того, чтобы он оставался открытым.
Специальный охотник за
2
@WhatWizard цель, которая должна быть достигнута, состоит в том, чтобы быть неочевидным завершенным по Тьюрингу, причем неочевидность оценивается по тому, что она не взломана в течение недели. Разве это не ясно?
Натаниэль

Ответы:

10

Арифметика с завязанными глазами

Возможно, довольно простой язык для начала, условно говоря. (Существуют ограничения на то, насколько сложным может быть язык, потому что я должен доказать это по Тьюрингу - завершить сам!)

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

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

Спецификация

Арифметика с завязанными глазами - это эзотерический язык программирования со следующими спецификациями:

Хранилище данных

Состояние работающей арифметической программы с завязанными глазами состоит из шести переменных, каждая из которых может хранить целое число. (Там нет никаких ограничений относительно того, как большие или малые эти числа можно получить, в частности, они могут пойти отрицательные.) Переменные называются a, b, c, d, e, и i.

В начале программы, aчтобы eвключено каждый инициализируются в 0, и iинициализируются до положительного целого числа , взятого из пользовательского ввода. (Если вход недоступен, iинициализируется 1.)

Если программа прекращает выполнение (это может произойти только из-за деления на ноль), значение iнепосредственно перед попыткой деления используется в качестве вывода программы.

программа

Арифметическая программа с завязанными глазами - это список команд, каждая из которых имеет одну из следующих форм (где v можно заменить любым именем переменной, возможно, другим именем при каждом ее использовании):

  • v = v + v
  • v = v - v
  • v = v * v
  • v = v / v

Обратите внимание, что каждый операнд команд должен быть переменной; этот язык не позволяет использовать буквенные целые числа.

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

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

Нет никакого потока управления, кроме выхода из программы; Команды всегда чередуются последовательно, вплоть до деления на ноль (если оно есть) и завершения программы. В частности, нет возможности напрямую читать переменные, только использовать их в качестве источника вычислений, результаты которых влияют на значения, присвоенные другим переменным.

ais523
источник
Можете ли вы проверить, если мой ответ что-то не хватает?
user202729
@ user202729: (комментируя здесь, так как у меня нет представителя, чтобы комментировать там) Вы не можете смоделировать «движение, если ложь» из «флип» и «движение, если истина», потому что вы не можете отменить флип после переезда Поэтому вам понадобится другой способ справиться с этим (например, способ инвертировать тесты, который не должен быть сложным). Что еще более важно, это доказательство полноты по Тьюрингу с точки зрения поведения остановки, но определение в вопросе требует, чтобы вы также имели возможность выполнять ввод-вывод, поэтому вам нужно доказать, что вы можете это сделать.
ais523
Я надеюсь, что часть ввода / вывода (сейчас) в порядке. Что касается другой проблемы, я понимаю, что внутренние, если даже не нужны, промежуточные состояния решают все проблемы (хотя я не уверен, как это
выразить
@ user202729: это все еще не совсем верно (например, вопрос требует, чтобы вы могли выводить отрицательные числа, и вам также нужно изменить назначение iтак, чтобы номер состояния - который всегда будет "остановкой") - не будет быть частью результатов), но это достаточно близко, поэтому я не собираюсь отмечать это как безопасный, так как вы, несомненно, получите полный треск при достаточном времени и достаточном разъяснении правил. Я не хочу побеждать в этом соревновании по техническим вопросам.
ais523
Это очень близко к ограничениям, которые использует de.ioccc.org/years-spoiler.html#1992_buzzard.1 . Эта реализация использует целые числа фиксированного размера и поэтому не является полной по Тьюрингу, и эта величина серьезно ограничена числом имеющихся у вас переменных, но я думаю, что доказательство тем не менее схоже.
b_jonas