Можно ли создать квин на каждом языке, полном тьюринга?

Question

Я просто хотел узнать, возможно ли на 100%, если мой язык завершен по Тьюрингу, написать в нем программу, которая печатает сама себя (конечно, без использования функции чтения файлов)

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

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

Answer 1

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

Смотрите здесь

Answer 2

Я столкнулся с этой проблемой пару месяцев назад.

Хотя написание квинны не обязательно доказывает, что язык является полным по Тьюрингу, это сильное предложение;) Что касается полноты по Тьюрингу, если вы можете (как вы сказали) предоставить правильный перевод с вашего языка на другой Turing-Complete язык, тогда ваш язык - Turing Complete.

При этом любой язык, который является полным по Тьюрингу и может выводить строку, должен иметь возможность генерировать квин. Также из Википедии:

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

Answer 3

Возможно иметь язык программирования, который не может печатать все символы в своем представлении. Например, ввод / вывод может быть ограничен 7-битными символами ASCII с ключевыми словами языка на арабском языке. Это единственное исключение, о котором я могу подумать.

Answer 4

Ну, технически, не всегда. Согласно доказательству в Википедии , язык программирования должен иметь допустимую нумерацию. Практические и вменяемые языки программирования Тьюринга - все допустимые нумерации. А язык программирования с компоновкой Тьюринга является допустимой нумерацией, если есть возможность перевести эту и другую допустимую нумерацию.

Пример языка программирования, полного по Тьюрингу, который не является допустимой нумерацией:

Исходный код всегда содержит одну или две экранированные строки в двойных кавычках. Если входные данные пусты, выведите первую строку, если есть две строки, или выполните цикл навсегда, если он есть. В противном случае оцените последнюю строку в Python, используя исходные данные в качестве входных данных.

Это не допустимая нумерация, потому что, учитывая программу на Python, мы должны знать ее поведение, когда ввод пуст, чтобы перевести его на этот язык. Но мы можем никогда не узнать, является ли это бесконечным циклом, поскольку мы не можем решить проблему остановки. Мы знаем, что перевод всегда существует.

Невозможно писать квины на этом языке.