Действительно ли возможно создать Куайна на каждом полном Тьюрингом языке?
Я просто хотел знать, на ли 100% возможно, если мой язык полон Тьюрингом, для записи программы в нем, которая распечатывает себя (конечно, не использование функции чтения файла)
Таким образом, если язык просто имеет действительно необходимые вещи для создания его Тьюрингом завершенный (я доказал бы, что путем перевода Brainf*ck кодируют к нему), как вывод, переменные, условия и gotos (ад да, gotos), я могу попытаться писать Куайну в нем?
Я также спрашиваю это, потому что я не уверен, что Куайн непосредственно вписывается в закон Turing's, что машина Тьюринга способна к любой вычислительной задаче. Я просто хочу знать, таким образом, я не пробую в течение многих лет, не зная, что это может быть невозможно.
3 ответа
Любой язык программирования, который является полным по Тьюрингу и который может выводить любую строку (вычислимой функцией строки как программы - это техническое условие, которое удовлетворяется на каждом существующем языке программирования ) есть программа quine (и, фактически, бесконечно много программ quine, и многие подобные курьезы) согласно теореме о неподвижной точке.
Можно иметь язык программирования, который не может печатать все символы в своем представлении. Например, ввод-вывод может быть ограничен 7-битными символами ASCII с языковыми ключевыми словами на арабском языке. Это единственное исключение, о котором я могу думать.
Я столкнулся с этой проблемой пару месяцев назад.
Хотя написание квина не обязательно доказывает, что язык является полным по Тьюрингу, это сильное предположение ;) Что касается полноты по Тьюрингу, если вы можете (как вы сказали) обеспечить корректный перевод с вашего языка на другой полный по Тьюрингу язык, то ваш язык является полным по Тьюрингу.
Учитывая это, любой язык, который является полным по Тьюрингу и может вывести строку, должен быть способен генерировать квин. Также из Википедии:
Кином называется неподвижная точка среды выполнения, когда среда выполнения рассматривается как функция. Квины возможны в любом языке программирования, который имеет возможность выводить любую вычислимую строку, как прямое следствие теоремы рекурсии Клейна. Для развлечения программисты иногда пытаются разработать самый короткий возможный квин на любом данном языке программирования.