2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Получила ли программа свой же код на вход?
Сообщение10.07.2014, 23:02 


26/06/14
83
zt09 в сообщении #886369 писал(а):
Из того, что это нельзя сделать в общем случае, вовсе не следует, что этого нельзя сделать для конкретной программы, т.е. для случая X - константа, что в общем-то и подразумевается в условии задачи.


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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение10.07.2014, 23:10 
Заслуженный участник


02/08/11
6874
Teletranslator в сообщении #886394 писал(а):
Что есть "общий случай"?
Мне тоже это непонятно.

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение11.07.2014, 18:37 


01/12/11

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение11.07.2014, 18:39 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Не об этом говорим.

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение11.07.2014, 18:51 


01/12/11

1047
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$.

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение11.07.2014, 19:31 


26/06/14
83
Skeptic в сообщении #886611 писал(а):
Есть принципиальная разница: в машинном коде не хранятся имена идентификаторов и другая служебная информация, предназначенная для удобства программиста.
warlock66613, вы считаете, что в памяти машины хранятся слово "Environment.NewLine" и символы "{", "}"?


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

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


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

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение11.07.2014, 21:36 
Заслуженный участник


02/08/11
6874
Skeptic в сообщении #886611 писал(а):
warlock66613, вы считаете, что в памяти машины хранятся слово "Environment.NewLine" и символы "{", "}"?
В случае приведённой мной программы - да, хранятся. Но я понял к чему вы клоните. Да, для машинного языка для архитектуры вроде x86 всё делается существенно проще, согласен. Но нужно добавить условия: код в секции данных исполнять нельзя, из секции кода читать нельзя. По сути это аналогично требованию не использовать рефлексию в языках, где она есть. И вот уже снова принципиальной разницы нет.

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение28.08.2014, 17:20 


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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение29.08.2014, 02:57 
Заслуженный участник


28/04/09
1933
Вот пример такой программы на 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;
}
 

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение29.08.2014, 14:47 


01/12/11

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение29.08.2014, 17:19 


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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение30.08.2014, 07:29 


01/12/11

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение30.08.2014, 08:57 
Заслуженный участник


28/04/09
1933
Примеры подобных программ на разных языках.

Skeptic
Skeptic в сообщении #901681 писал(а):
Если есть машина с системой команд С99, то программу, читающую саму себя, написать можно.
Программа же написана на С99, а в современных машинах после компиляции появляется другой текст, отличный от исходного.
Вот я привел ссылки на сайт, куда можно загружать код программы на C99 и входные данные, а при нажатии на кнопку "Run it" выскакивают некие выходные данные. Вы можете определить, используют ли владельцы этого сайта обычную машину и компилятор C99 или машину с системой команд C99?

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение30.08.2014, 10:05 


01/12/11

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

 Профиль  
                  
 
 Re: Получила ли программа свой же код на вход?
Сообщение02.09.2014, 12:07 
Заслуженный участник


02/08/11
6874
_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)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group