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

Question

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

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

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

Answer 1

<цитата>

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

См. здесь

Answer 2

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

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

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

<цитата>

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

Answer 3

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

Answer 4

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

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

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

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

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