Можно ли создать quine на каждом языке, который подходит для обучения?

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

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

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

Ответ 1

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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