Получила ли программа свой же код на вход?

[tenmin]

Можно ли написать программу, которая говорит передали ей или нет её собственный код? Т.е. такая программа $X$, что $X(X)=1$ и $X(P)=0$ для любых $P\neq X$.

[Lukum]

Можно. И это не сложно реализовать.

-- 09.07.2014, 11:54 --

Есть похожая задача в книге Уэзерелл "Этюды для программистов": написать программу, печатающую свой собственный текст. Можно попробовать для начала решить данную задачу.

[warlock66613]

Это тот же quin. Только printf заменить на scanf и strcmp.

[tenmin]

Используется синтаксис Javascript

function f(p){return f.toString()===p?1:0;}

Да, я уже сам придумал.

[warlock66613]

tenmin, это читерство. Если хотите честно, надо без рефлекшена.

[zt09]

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

Классическая система или переменная не может "знать" собственное значение.

[Skeptic]

Что такое "код программы" - это текст на исходном языке или машинный код после трансляции?

[Aritaborian]

Если понимать в смысле квайна — текст на исходном языке.

[warlock66613]

zt09 в сообщении #885741 писал(а):

Это в общем случае невозможно (по крайней мере для обычной машины Тьюринга).

Это в общем случае элементарно делается. Вот например программа, выводящая свой текст (C#):

(quin)

using System;
using System.IO;
class Program {
static void PatchProgramText(ref string programText) {
programText += "\"" +
programText
.Replace("\\", "\\\\")
.Replace("\"", "\\\"")
.Replace(Environment.NewLine, "\" + Environment.NewLine +" + Environment.NewLine + "\"") +
"\";" + Environment.NewLine +
"PatchProgramText(ref programText);" + Environment.NewLine +
"Console.Write(programText);" + Environment.NewLine +
"Console.ReadLine();" + Environment.NewLine +
"}" + Environment.NewLine +
"}" + Environment.NewLine;
}
static void Main(string[] args) {
string programText =
"using System;" + Environment.NewLine +
"using System.IO;" + Environment.NewLine +
"class Program {" + Environment.NewLine +
"static void PatchProgramText(ref string programText) {" + Environment.NewLine +
"programText += \"\\\"\" +" + Environment.NewLine +
"programText" + Environment.NewLine +
".Replace(\"\\\\\", \"\\\\\\\\\")" + Environment.NewLine +
".Replace(\"\\\"\", \"\\\\\\\"\")" + Environment.NewLine +
".Replace(Environment.NewLine, \"\\\" + Environment.NewLine +\" + Environment.NewLine + \"\\\"\") +" + Environment.NewLine +
"\"\\\";\" + Environment.NewLine +" + Environment.NewLine +
"\"PatchProgramText(ref programText);\" + Environment.NewLine +" + Environment.NewLine +
"\"Console.Write(programText);\" + Environment.NewLine +" + Environment.NewLine +
"\"}\" + Environment.NewLine +" + Environment.NewLine +
"\"}\" + Environment.NewLine;" + Environment.NewLine +
"}" + Environment.NewLine +
"static void Main(string[] args) {" + Environment.NewLine +
"string programText =" + Environment.NewLine +
"";
PatchProgramText(ref programText);
Console.Write(programText);
Console.ReadLine();
}
}

Переделать её в программу, сравнивающую свой текст с введённым, очень просто.

-- 09.07.2014, 22:23 --

Skeptic в сообщении #885742 писал(а):

Что такое "код программы" - это текст на исходном языке или машинный код после трансляции?

Между этими вариантами нет принципиальной разницы.

[ewert]

warlock66613 в сообщении #885911 писал(а):

Между этими вариантами нет принципиальной разницы.

Есть, причём именно принципиальная. Один и тот же алгоритм может быть запрограммирован как заблагорассудится. Благорассуженность же формализовать невозможно. Поэтому исходная постановка задачки, без уточнений -- бессмысленна.

[arseniiv]

Но ведь для каждой заблагорассуженности есть конкретный код программы. Для любого конкретного тьюринг-полного языка задача корректна и отвечается словом «да». Хоть машинный, хоть высокого уровня — и не важно, что какой-нибудь транслятор не переведёт программу на втором в программу на первом или другом втором, или ещё как-нибудь.

[ewert]

arseniiv в сообщении #886015 писал(а):

Но ведь для каждой заблагорассуженности есть конкретный код программы.

Но ведь тут проблема вовсе не в коде программы. А в законах, по которым сей код строится.

[warlock66613]

ewert в сообщении #886020 писал(а):

А в законах, по которым сей код строится.

Код не строится по законам. Код пишется программистом (иногда опосредовано, через компилятор) так как ему хочется.

[Teletranslator]

ewert в сообщении #886001 писал(а):

Поэтому исходная постановка задачки, без уточнений -- бессмысленна.

Знаете, что такое мат. индукция? Это доказательство бесконечной серии утверждений с помощью форумлирования алгоритма создания доказательства утверждения под любым номером.

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

[zt09]

warlock66613
Согласен, я по сути неверно ответил на поставленный вопрос. Из того, что это нельзя сделать в общем случае, вовсе не следует, что этого нельзя сделать для конкретной программы, т.е. для случая X - константа, что в общем-то и подразумевается в условии задачи.

Хотя, при очень сильном желании здесь можно и придраться к условию.