Как мог Куайн в моем взгляде языка программирования?
Я создал полный Тьюрингом язык программирования (уже доказанный), таким образом, должно быть возможно записать Куайну для него, правильно?
Но все quines, которые я знаю, хранят свой исходный код в строке и затем заменяют специальный символ в нем с помощью чего-то как chr и ord.
Мой язык только имеет следующее
- Базовая арифметика
- Международные и строковые типы
- Переменные
- == оператор
- Условное выражение gotos
Я понятия не имею, как я мог записать Куайну, поскольку я не имею реальной обработки строк в наличии, я могу только произвести постоянные строки. Все же это на 100% полно Тьюрингом.
3 ответа
Если у вас есть целые числа, вы можете кодировать или декодировать строки (для этого достаточно таких простых схем, как A = 1, B = 2 и т. Д.). Вам нужно только иметь возможность сравнивать постоянные строки или сравнивать int. Следовательно, похоже, что фундаментальной проблемы нет.
Вы работаете с числами и пишете такие вещи, как
if (n == 1) print "A"
if (n == 2) print "B"
...
Могут возникнуть некоторые практические трудности. Дело со строками не в том, что в них есть символы, а в том, что они эквивалентны очень большим числам. Здесь вам нужен либо доступ к числам с неограниченной точностью, либо к некоторому массиву чисел фиксированного размера, либо к другой большой структуре данных. Массив чисел сделает за вас то, что может сделать строка. Но если ваш язык является полным по Тьюрингу, у него должен быть способ легко получить доступ к некоторому большому фрагменту памяти
Полный язык Тьюринга, ограниченный 32-битной лентой (или где вы должны дать новое имя каждому другому 32-битному пространству памяти. ) было бы жаль, не уверен, что можно написать квайн с таким ограничением. Кстати, было бы интересно узнать, как вы доказали, что ваш язык является полным по Тьюрингу, если у вас нет массивов или аналогичной структуры. Обычный метод, который я обычно использую, - это реализовать некоторую машину Тьюринга на моем языке. Но для этого мне нужен какой-то массив, имитирующий полосу.
Этот вид кодирования - это в основном то, что Гёдель сделал в своей теореме о неполноте, нашел способ кодировать логические выражения как целые числа, а затем обосновать это.
Если вы дадите еще несколько элементов синтаксиса, мы могли бы даже попробовать это сделать (если у вас нет функций, а есть только gotos, это тоже будет проблемой, но вы также можете смоделировать это). Основная проблема в том, что вам нужно найти способ «сжать» закодированный исходный код. Если у вас есть длинная строковая константа, это, вероятно, может помочь.
Если ваш язык является полным по Тьюрингу и есть один quine, вероятно, их бесконечно много. Вот способ создать лишь некоторые из них:
- Реализуйте интерпретатор Brainfuck (или какой-нибудь другой простой полный язык Тьюринга) на своем языке. Напишите свою программу так, чтобы исходный код
X1при запуске интерпретировал программу Brainfuck.Y1 - Напишите алгоритм
строка f (строка a, строка b)на любом языке по вашему выбору, который при задании любыхaиbвыводит программу Brainfuck что когда run выводит строкуa, весь исходный код Brainfuck, затем строкуb. Вы можете адаптировать для этого существующую Quine Brainfuck. - Вычислите
f (X1, Y1), а затем вставьте полученную программу Brainfuck в свою программу из 1.
Шаг первый самый сложный, но вы, возможно, уже сделали это, потому что один из Самый простой способ доказать, что что-то является завершенным по Тьюрингу, - это реализовать интерпретатор для другого языка, который уже доказал свою завершенность по Тьюрингу.
Второй шаг уже доказан и не зависит от языка вашей программы.
Шаг третий - это простой расчет.
Очевидно, что программа в вашем языке программирования - это строка. Вывод quine - это программа.
Следовательно, вывод quine - это строка. Если у вас нет манипуляций со строками, то написать их невозможно.
Вы должны либо закодировать свою программу в числах (вместо простой человекочитаемой текстовой кодировки), либо реализовать работу со строками.