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

[Teletranslator]

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

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

Что есть "общий случай"?

[warlock66613]

Teletranslator в сообщении #886394 писал(а):

Что есть "общий случай"?

Мне тоже это непонятно.

[Skeptic]

Есть общий случай, независящий от языка программирования. Копия текста программы хранится вне её в файле. Входящий текст сравнивается сравнивается с копией.

[Aritaborian]

Не об этом говорим.

[Skeptic]

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

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 писал(а):

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

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

Есть принципиальная разница: в машинном коде не хранятся имена идентификаторов и другая служебная информация, предназначенная для удобства программиста.
warlock66613, вы считаете, что в памяти машины хранятся слово "Environment.NewLine" и символы "{", "}"?

-- 11.07.2014, 18:56 --

Aritaborian в сообщении #886606 писал(а):

Не об этом говорим.

Как не об этом? Моя тривиальная программа подходит под начальные условия.

Цитата:

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

Никаких ограничений не наложено.

[Teletranslator]

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

Есть принципиальная разница: в машинном коде не хранятся имена идентификаторов и другая служебная информация, предназначенная для удобства программиста.
warlock66613, вы считаете, что в памяти машины хранятся слово "Environment.NewLine" и символы "{", "}"?

Вы же не собираетесь подавать программе на вход машинный язык, если условились сравнивать исходники? В чём принципиальность этой разницы?

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

Есть общий случай, независящий от языка программирования. Копия текста программы хранится вне её в файле. Входящий текст сравнивается сравнивается с копией.

По причине тривиальности не обсуждается. У машин Тьюринга никаких файлов нет.

Спросите, в конце концов, у топикстартера, что он имел ввиду. У него, как видите, никаких файлов нет, только функции.

[warlock66613]

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

warlock66613, вы считаете, что в памяти машины хранятся слово "Environment.NewLine" и символы "{", "}"?

В случае приведённой мной программы - да, хранятся. Но я понял к чему вы клоните. Да, для машинного языка для архитектуры вроде x86 всё делается существенно проще, согласен. Но нужно добавить условия: код в секции данных исполнять нельзя, из секции кода читать нельзя. По сути это аналогично требованию не использовать рефлексию в языках, где она есть. И вот уже снова принципиальной разницы нет.

[_hum_]

наверное, это все же задача из теории вычислимых функций по теме "теорема Клини о неподвижной точке", потому и решать желательно в общей постановке.

[EtCetera]

Вот пример такой программы на C99:

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

#include <stdio.h>
#include <string.h>

int i;
char s[2000], c, p[2000];
const char r = '\r', n = '\n', t = '\t', b = '\\', q = '\"',
l0[] = "#include <stdio.h>",
l1[] = "#include <string.h>",
l2[] = "int i;",
l3[] = "char s[2000], c, p[2000];",
l[]  = "%s%c%c%s%c%c%c%c%s%c%c%s%c%cconst char r = '%cr', n = '%cn', t = '%ct', b = '%c%c', q = '%c%c',%c%cl0[] = %c%s%c,%c%cl1[] = %c%s%c,%c%cl2[] = %c%s%c,%c%cl3[] = %c%s%c,%c%cl[]  = %c%s%c,%c%cl4[] = %c%s%c,%c%cl5[] = %c%s%c,%c%cl6[] = %c%s%c,%c%cl7[] = %c%s%c,%c%cl8[] = %c%s%c,%c%cl9[] = %c%s%c;%c%c%c%c%s%c%c{%c%c%c%s%c%c%c%s%c%c%c%c%s%c%c%c%s%c%c%c%c%c%s%c%c}%c%c",
l4[] = "int main(void)",
l5[] = "sprintf(p, l, l0, r, n, l1, r, n, r, n, l2, r, n, l3, r, n, b, b, b, b, b, b, q, r, n, q, l0, q, r, n, q, l1, q, r, n, q, l2, q, r, n, q, l3, q, r, n, q, l, q, r, n, q, l4, q, r, n, q, l5, q, r, n, q, l6, q, r, n, q, l7, q, r, n, q, l8, q, r, n, q, l9, q, r, n, r, n, l4, r, n, r, n, t, l5, r, n, t, l6, r, n, t, t, l7, r, n, t, l8, r, n, r, n, t, l9, r, n, r, n);",
l6[] = "while ((c = getchar()) != EOF)",
l7[] = "s[i++] = c;",
l8[] = "putchar(48 + !strcmp(s, p));",
l9[] = "return 0;";

int main(void)
{
        sprintf(p, l, l0, r, n, l1, r, n, r, n, l2, r, n, l3, r, n, b, b, b, b, b, b, q, r, n, q, l0, q, r, n, q, l1, q, r, n, q, l2, q, r, n, q, l3, q, r, n, q, l, q, r, n, q, l4, q, r, n, q, l5, q, r, n, q, l6, q, r, n, q, l7, q, r, n, q, l8, q, r, n, q, l9, q, r, n, r, n, l4, r, n, r, n, t, l5, r, n, t, l6, r, n, t, t, l7, r, n, t, l8, r, n, r, n, t, l9, r, n, r, n);
        while ((c = getchar()) != EOF)
                s[i++] = c;
        putchar(48 + !strcmp(s, p));

        return 0;
}
 

Демонстрация работы программы:

• на вход подается текст программы,
• на вход подается строка, не являющаяся текстом программы.

[Skeptic]

Если есть машина с системой команд С99, то программу, читающую саму себя, написать можно.
Программа же написана на С99, а в современных машинах после компиляции появляется другой текст, отличный от исходного.
Эта задача из времён появления компьютеров. Тогда программы писались в машинных кодах без преобразований, и задача имела смысл и была разрешима.

[_hum_]

Skeptic
это общий фундаментальный факт, вытекающий из теоремы клини о неподвижной точке:
пусть есть универсальный (тьюринг-полный) язык программирования с интерпретатором $U$, который на вход принимает текст $p$ программы и исходные данные $x$ (в том же текстовом виде) для ее выполнения, а на выходе дает (в текстовом виде) результат $U(p,x)$ выполнения соответствующего программе алгоритма над данными $x$. Тогда существует такой текст программы $ p$, что $U(p,p) $ = "1", а $U(p,x)$ = "0", если $x \neq p$.

[Skeptic]

С этим не поспоришь.
Архимед сказал: "Дайте мне точку опоры и я переверну Землю". Только, где такую точку взять?

[EtCetera]

Примеры подобных программ на разных языках.

Skeptic

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

Если есть машина с системой команд С99, то программу, читающую саму себя, написать можно.
Программа же написана на С99, а в современных машинах после компиляции появляется другой текст, отличный от исходного.

Вот я привел ссылки на сайт, куда можно загружать код программы на C99 и входные данные, а при нажатии на кнопку "Run it" выскакивают некие выходные данные. Вы можете определить, используют ли владельцы этого сайта обычную машину и компилятор C99 или машину с системой команд C99?

[Skeptic]

Если такие программы есть, то это ответ на ТС, и тему можно считать закрытой..

[warlock66613]

_hum_ в сообщении #901761 писал(а):

пусть есть универсальный (тьюринг-полный) язык программирования с интерпретатором $U$, который на вход принимает текст $p$ программы и исходные данные $x$ (в том же текстовом виде) для ее выполнения, а на выходе дает (в текстовом виде) результат $U(p,x)$ выполнения соответствующего программе алгоритма над данными $x$. Тогда существует такой текст программы $ p$, что $U(p,p) $ = "1", а $U(p,x)$ = "0", если $x \neq p$.

Я бы сформулировал более сильное утверждение - оно полнее отвечает на вопрос.

Пусть есть универсальный (тьюринг-полный) язык программирования с интерпретатором $U$, который на вход принимает текст $p$ программы и исходные данные $x$ (в том же текстовом виде) для ее выполнения, а на выходе дает (в текстовом виде) результат $U(p,x)$ выполнения соответствующего программе алгоритма над данными $x$. Тогда для любого текста программы $p_0$ существует текст программы $p$ такой, что 1) $U(p, \text{«1»} p)=\text{«1»}$; 2) $U(p, \text{«1»} x)=\text{«0»}$, $x \neq p$; 3) $U(p, \text{«0»} x)=U(p_0,x)$.