Bitok & NeonCipher
Bitok
Вот что получилось:
"Попробовал написать программу, которая сама себя печатает, используя только XOR и рекурсию. Она выводит свой код только если ввод — палиндром длиной в три символа. Думаешь, можно как-то применить этот трюк для строк любой длины?
NeonCipher
Ты можешь попробовать, но утонешь в комбинаторике. Приём с палиндромом – это просто удобная неподвижная точка XOR-оператора для трёхзначного ключа. Для более длинных входных данных нужен универсальный интерпретатор, способный восстанавливать свой исходный код из входной строки. Закодируй программу как неподвижную точку более сложного преобразования, или создай маленький интерпретатор внутри кода, который переписывает сам себя. В принципе, это реализуемо, но объём кода растёт быстрее, чем длина входных данных. Попробуй самовоспроизводящуюся древовидную структуру; это поможет удержать рекурсию в рамках и не позволит XOR обмануть.
Bitok
Ну, если бы я выбирал, то сделал бы что-то на основе дерева, но даже тогда получается квадрег из ксеров, который нужно собирать во время выполнения – по сути, мини-компилятор. Если есть возможность хранить O(n²) бит для промежуточного представления, можно просто написать маленький интерпретатор, который перестраивает дерево на ходу, но это уже не в духе "только ксеры". Похоже, единственный элегантный вариант – выбрать самоограничивающийся язык, полный Тьюринга, и закодировать весь интерпретатор в фиксированной точке этого языка, но это уже совсем другой уровень головоломки.
NeonCipher
Ну что, снова вернулся к этой затее – построить интерпретатор из одной примитивной операции? Выбери язык с самоограничивающимися конструкциями – типа минимальной лямбда-математики или кодировки, вдохновленной PostScript. Потом встрой интерпретатор в точечную комбинаторную финкцию. Этот трюк с XOR – просто детская игрушка, как только перейдёшь на полноценную Тьюринг-завершенную базу, самовоспроизводящийся код станет тривиальным сочетанием "применить" и "сложить". На практике тебе придётся пожертвовать изяществом XOR ради чистого, рекурсивного определения, которое проще доказать. Если хватит смелости, напиши интерпретатор один раз, а потом позволь ему обрабатывать входные данные как информацию – вот этот "чистый трюк" ты и ищешь.
Bitok
Ну, идея с интерпретатором неплохая, но как только скормишь ей исходник лямбда-исчисления, она превращается в бездну, которая каждый раз при запуске печатает свой собственный код, и ты начинаешь вылавливать баги, как белка, гонящаяся за глюками. Помни: если тебе нужен этот самоограничивающийся фокус, тебе понадобится комбинатор фиксированной точки, столь же хорошо документированный, как остальной код, иначе ты будешь ловить синтаксические ошибки в своей голове.
NeonCipher
Похоже на типичный случай: "Я написал код, теперь я и отвечаю за ошибки". Держи комбинизатор простым, отлаживай строку за строкой и помни, что только чистая, корректная фиксированная точка поможет избежать самовоспроизводящегося цикла ошибок. Удачи в охоте.