Проблема останова. В чём противоречие?

@Aycon · Регистрация: 07.05.2015

Студворк — интернет-сервис помощи студентам

Расскажите пожалуйста, в чём суть проблемы останова и как Тьюринг определяет и доказывает отсутствие оракула?

@Shamil1 · 18.05.2022, 12:31

Сообщение от vantfiles

И как же будет выглядеть подключение библиотеки и вызов библиотечной ф-ции?

Вставить её код в нужное место.

@Aycon · 20.05.2022, 11:33 **[ТС]**

Shamil1,

Текст, который я передаю, это и есть описание (код) процедуры. А вторым аргументом я передаю значения всех параметров для этой процедуры.

Вторым аргументом вы передаёте процедуру, которая требует аргумент text. Ваша процедура кодирована строкой, поэтому не возникает ошибки компиляции. В code вы передаёте процедуру, которая требует один текстовый параметр "text". В качестве параметра в arg вы передаёте другую (ту же самую, но компилятор об этом не знает) процедуру, которая требует другой (тот же самый, но компилятор об этом не знает) параметр "text". В итоге у вас всё рано определены НЕ ВСЕ ПАРАМЕТРЫ. TEXT НЕ ОПРЕДЕЛЁН.

Зачем?

Чтобы ты увидел что не так, -оскорбление-.
Вы передаёте первым параметром процедуру, которая ЗАВИСИТ (1) от text.
Это процедура, без параметров.
В качестве параметра, вы передаёте текст, в котором хранится процедура, которая зависит от параметра текст. Если внутри вызова prog я поменяю значение text, prog не изменится, а вот все последующие рекурсивные её вызовы - да. Ты это понимаешь или нет?

<censored>

Добавлено через 2 минуты

Оракул принимает код программы, а не какой-то Action.

Оракул принимает описание программы и её аргументы, а не код.

Добавлено через 1 минуту

Вставить её код в нужное место.

Ты будешь бесконечно вставлять её, потому что твоя функция рекурсивная, зависит от параметра текст, который содержит параметр текст.

Добавлено через 24 секунды
Shamil1, а бесконечных программ не существует по определению

Добавлено через 18 минут
Shamil1, я покажу, что произойдёт, если вы запустите prog:
Prog выполняется без ошибок, вплоть до строки вызова оракула (1), оракул1 видит, что prog внутри процедуры в параметре code1 зависит от вызова оракула2. Оракул2 зависит от text и text1. Text1 не определён, поэтому оракул2 на вход получает некорректную программу, поэтому он сгенерирует исключение argumentException: code is incorrect programm (variable "text" is not defined). Исключение пробросится через оракула1 в prog и она схватит исключение времени выполнения и упадёт.
Оракул2 не знает, чему равен text, потому что text в оракуле2 не равен text в оракуле1. Он вполне мог измениться в prog.

<censored>

Добавлено через 3 минуты
Shamil1,

Строка 1: ты понимаешь, чем отричается "описание функции и все требуемые ей параметры" от "два текстовых параметра"?
Это не одно и тоже, если ты не понимаешь, вернись к строке 1.

Добавлено через 6 минут
Shamil1, я попросил предоставить код на брейнфаке не для того, чтобы усложнить тебе возможность, защитить твою позицию, а исключительно для того, чтобы ты сам убедился, что функция prog не реализуема. На brain****e можно написать любую программу из c#, да, это так, но только корректную программу. Твоя программа компилируется только благодаря заглушке в Oracul()

Я предложил эту задачу, чтобы в процессе реализации ты столкнулся с ограничением и сам себя убедил, что это невозможно, раз уж ты не позволяешь мне убедить тебя.

Добавлено через 4 минуты
Shamil1, с помощью функции prog я могу доказать, что не существует ни одной функции, которая принимает на вход программу и её входные параметры. Я серьёзно. Даже не смотря на то, что программа будет реализована. Покажи мне реализацию хоть одной такой функции и я напишу аналог prog, который доказывает, что этой реализации не существует. Без проблем. По аналогии с оракулом.

@Shamil1 · 20.05.2022, 11:41

Оракул принимает два параметра:
1. Строку, содержащую код функции. От Оракула не требуется запускать этот код. Если он пытается запустить этот код и попадает в рекурсию, то это проблемы Оракула.
2. Значения аргументов, которые принимает эта функция. Никаких ограничений на значение этого параметра нет. Если Оракул пытает его скомпилировать, то это проблемы Оракула.

Моя функция компилируется. Поэтому все требования соблюдены. Свою заглушку Oracle в коде своей функции я заменю на реальный код Вашего Оракула, как только Вы мне этот код предоставите.

@Aycon · 20.05.2022, 12:10 **[ТС]**

Shamil1, где написано, что оракул принимает два параметра? Вы перечитайте википедию или первоисточник, покажите ссылку? Он принимает описание функции и параметр к ней. Форма не регламентированна, ваша форма не даёт достаточно информации.

@Shamil1 · 20.05.2022, 12:19

Сообщение от Aycon

Он принимает описание функции и параметр к ней.

Это и есть два параметра.
1. описание функции
2. параметры функции

@Aycon · 20.05.2022, 12:24 **[ТС]**

Shamil1, параметры функции не могут быть параметром. Описание должно быть однозначным.

Добавлено через 32 секунды
Shamil1, иначе это не параметры, а это не описание.

Добавлено через 1 минуту
Shamil1, описание в вашем примере однозначно, но параметр не однозначен, потому что он зависит от какого-то text, который не определён на момент компиляции, я сто раз уже сказал об этом

@Shamil1 · 20.05.2022, 12:27

Сообщение от Aycon

параметры функции не могут быть параметром

Я не понял, почему параметр функции не может быть параметром функции.

Формальным языком:
Для любой функции F(G, start_state) которая может определять останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F, результат выполнения будет противоположен тому, который предсказывает F.

https://ru.wikipedia.org/wiki/... 0%BA%D0%B8

Добавлено через 1 минуту

Сообщение от Aycon

параметр не однозначен, потому что он зависит от какого-то text, который не определён на момент компиляции

Я Вам привёл значение этого параметра. Как конкретный набор символов может быть неоднозначным?

@Aycon · 20.05.2022, 12:29 **[ТС]**

Shamil1, параметр может быть параметром, а параметрЫ не могут быть параметром

Добавлено через 1 минуту
Shamil1, вы согласны, что start_state должен быть определён перед вызовом?

@Shamil1 · 20.05.2022, 12:31

Сообщение от Aycon

параметр может быть параметром, а параметрЫ не могут быть параметром

Если функция принимает несколько аргументов, то все аргументы можно объеденить в один объект, который и будет параметром функции. Но в данном случае исследуемая функция принимает всего один аргумет типа "строка". У неё один параметр, и я привёл его значение.

Добавлено через 12 секунд

Сообщение от Aycon

вы согласны, что start_state должен быть определён перед вызовом?

Да. start_state должен быть определён перед вызовом Оракула.

@Aycon · 20.05.2022, 12:47 **[ТС]**

Shamil1,
Это однозначное определение функции:
F(x) = x+ x
А это однозначное определение параметра:
x = 2
А это неоднозначное определение параметра:
x = a × 2

Потому что x - это не константа, она зависит от a.

Да, вы проинициализировали a выше, но оракул, которому на вход подаётся что-то вроде этого:
Oracul("F(x) = x + x", "x = a × 2")
Вернёт исключение, ведь весь контекст с которым он работает - это его два параметра и будет прав. Более того, если я запущу вот это:
Var x = a × 2
F(Var) => Var × Var
return F(x)

Это тоже не скомпилируется.

Более того, если вы дадите школьнику этот пример:
а*2 + a*2, ОН тоже его не решит. Максимум, он вынесет a за скобки и скажет, что ответ зависит от a.

Почему оракул не видит, чему равно а?
Потому что это ЧИСТАЯ функция, она не видит внешний КОНТЕКСТ. Она видит только и исключительно ТОЛЬКО то, что у неё в параметрах.
А чистая она по определению.

А как правильно?
А правильно вот так:

Code
1
Oracul("F(x) = x + x", "a = 3, x = 2 × a")

А как тогда вызвать prog?
А никак, если вы не определили text в параметре, но вы не можете его определить, потому что text ЗАВИСИТ от text

Добавлено через 2 минуты
Shamil1, вам известны определения "чистая функция" и "контекст исполнения программы"? Может быть, дело в том, что вы не знакомы с этими понятиями?

@Shamil1 · 20.05.2022, 13:05

Сообщение от Aycon

если вы не определили text в параметре, но вы не можете его определить, потому что text ЗАВИСИТ от text

Текст - это список символов, который я передаю Оракулу. Для Оракула это уже готовый набор символов - констаната. Константа не может ни от чего зависеть.

@Aycon · 20.05.2022, 13:19 **[ТС]**

Shamil1, посмотрите внимательно на эти два листинга:

1:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void Main()
{
    string text = @"bool Prog(string text)
{
    string args = text;
    bool flag = Oracle(text, args);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}";
 
    bool res = Prog(text);
    
    Console.WriteLine(res);
 
}
 
bool Prog(string text)
{
    bool flag = Oracle(text, text);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}
 
bool Oracle(string text, object args)
{
    return false;
}

2:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void Main()
{
    string text = @"bool Prog(string text)
{
    string args = text;
    bool flag = Oracle(text, args);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}";
 
    bool res = Prog(text);
    
    Console.WriteLine(res);
 
}
 
bool Prog(string text)
{
    text = "42";
    bool flag = Oracle(text, text);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}
 
bool Oracle(string text, object args)
{
    return false;
}

Оракул в первом листинге и во втором должен вернуть одинаковое значение? Я изменил значение text перед вызовом оракула.
Он должен всегда возвращать одинаковый результат при одном и том же значении входных параметров - быть детерминированным по определению.
Почему же он может изменить свой результат? Потому что его start_state зависит от глобального состояния. Передайте в него константное (в смысле не динамическое, не изменяющееся во время выполнения) значение и он без проблем отработает.

Добавлено через 6 минут
Shamil1,

Текст - это список символов, который я передаю Оракулу. Для Оракула это уже готовый набор символов - констаната. Константа не может ни от чего зависеть.

Вы забываете, что его нужно интерпретировать. Если не Оракулу, то Prog

Добавлено через 3 минуты
Shamil1, я могу доказать, что функции Prog не существует.
Что она вернёт, если передать ей саму себя? И во второй аргумент тоже.
Верно, ничего, ответ не определён. Значит, функция Prog не существует.

@Shamil1 · 20.05.2022, 13:21

Сообщение от Aycon

Передайте в него константное (в смысле не динамическое, не изменяющееся во время выполнения) значение и он без проблем отработает.

Я и передаю константное значение. Текстовый литерал, по определению, является констанотой, независимо от содержимого.

Сообщение от Aycon

Оракул в первом листинге и во втором должен вернуть одинаковое значение?

Необязательно. Раз вход различается, то и результат может различаться.

Сообщение от Aycon

Я изменил значение text перед вызовом оракула.

Вы подали на вход функции другую константу. Константа, по определению, не может содержать вызовов функций. Это всего лишь Ваша интерпретация данного набора символов. Меня не интересует Ваша интерпретация этой константы. Меня интересует, что вернёт Оракул.

@Aycon · 20.05.2022, 13:23 **[ТС]**

Shamil1, я могу доказать, что функции Prog не существует.
Что она вернёт, если передать ей саму себя? И во второй аргумент тоже.
Верно, ничего, ответ не определён. Значит, функция Prog не существует.

@Shamil1 · 20.05.2022, 13:25

Сообщение от Aycon

Вы забываете, что его нужно интерпретировать. Если не Оракулу, то Prog

Что нужно Оракулу, меня не волнует. Вы его написали, поэтому всё, что он делает - это Ваша ответственность.

А моя функция Prog не интерпретирует этот текст. Она просто передаёт его другой функции.

Добавлено через 54 секунды

Сообщение от Aycon

Значит, функция Prog не существует.

Как не существует, если у нас перед глазами её код? Причём, этот код можно скомпилировать и запустить.

@Aycon · 20.05.2022, 13:39 **[ТС]**

Shamil1, покажите имплементацию Prog на брейнфак. Если она существует, то это можно сделать.

Добавлено через 1 минуту
Shamil1,

Что нужно Оракулу, меня не волнует

Меня не волнует, что тебя волнует. У Оракула есть спецификация и вы обязаны соблюдать её, если хотите использовать его в своей функции.

Добавлено через 5 минут
Shamil1, а вот так. Не существует. Я воспользовался тем же доказательством, что и вы. Если бы она существовала, то её вызов был бы определён. А раз он не определён, для этих параметров, то эта функция не существует. Ну или... ну я даже не знаю... ИЛИ МОЖЕТ БЫТЬ доказательство неверно?

@Shamil1 · 20.05.2022, 13:49

Сообщение от Aycon

покажите имплементацию Prog на брейнфак. Если она существует, то это можно сделать.

Не вижу смысла в имплементации на брейнфак. Если функцию можно написать на одном тьюринг-полным яп, то можно и на другом.

Напоминаю кратко, что происходит и в какой последовательности.

1. Вы пишите функцию F(G, start_state) и даёте мне.

2. Я пишу функцию G(start_state). Так как у меня уже есть функция F(G, start_state), то я могу в функции G вызывать функцию F.

3. Я придумываю константу start_state. Она может содержать всё, что мне хочется - любую абракадабру.

4. Я запускаю Вашу функцию F, передавая ей G и start_state, подготовленные мной на шагах 2 и 3. Ваша функция F должна через конечное время вернуть true или false. Если она вернула что-нибудь другое или упала или зациклилась, то она не удовлетворяет требованиям, предъявляемым к Оракулу.

5. Мы проверяем, правильный ли ответ вернула функция F.

@Aycon · 20.05.2022, 13:53 **[ТС]**

Shamil1, как в пункте 4 вы определите, что она зациклилась?

@Shamil1 · 20.05.2022, 13:59

Сообщение от Aycon

Если бы она существовала, то её вызов был бы определён.

Неверно. Произвольная функция может вести себя как угодно - что-то возращать, падать с ошибкой, зависать и так далее.

Оракул отличается от произвольной функции тем, что должен работать без ошибок и всегда возвращать правильный результат согласно спецификации. Если Ваша функция F не удовлетворяет ВСЕМ предъявляемым к Оракулу требованиям, то она не является Оракулом.

@Aycon · 20.05.2022, 14:04 **[ТС]**

Shamil1, чтобы она удовлетворяла спецификации, её нужно вызывать в соответствии со спецификацией. Сделайте это и результат будет соответствующий. Функция prog передаёт в Oracul некорректные параметры. В соответмтвии с этой спецификацией, это не Оракул, ведь Оракул зависит только от параметров, которые приходят ему на вход.

Новые блоги и статьи Все статьи Все блоги /
Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .	Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .	Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой anaschu 23.05.2026 Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .	Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15 anaschu 23.05.2026 Внезапно хорошее здоровье сотрудников не нужно капиталистам?))	Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул anaschu 23.05.2026 Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418

	Проблема останова. В чём противоречие? 18.11.2021, 08:29. Показов 8952. Ответов 176 Метки нет (Все метки) Расскажите пожалуйста, в чём суть проблемы останова и как Тьюринг определяет и доказывает отсутствие оракула? 0

@Shamil1 Модератор 3138 / 2286 / 469 Регистрация: 26.03.2015 Сообщений: 8,890
	20.05.2022, 11:41
	Оракул принимает два параметра: 1. Строку, содержащую код функции. От Оракула не требуется запускать этот код. Если он пытается запустить этот код и попадает в рекурсию, то это проблемы Оракула. 2. Значения аргументов, которые принимает эта функция. Никаких ограничений на значение этого параметра нет. Если Оракул пытает его скомпилировать, то это проблемы Оракула. Моя функция компилируется. Поэтому все требования соблюдены. Свою заглушку Oracle в коде своей функции я заменю на реальный код Вашего Оракула, как только Вы мне этот код предоставите. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 12:10 [ТС]
	Shamil1, где написано, что оракул принимает два параметра? Вы перечитайте википедию или первоисточник, покажите ссылку? Он принимает описание функции и параметр к ней. Форма не регламентированна, ваша форма не даёт достаточно информации. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 12:24 [ТС]
	Shamil1, параметры функции не могут быть параметром. Описание должно быть однозначным. Добавлено через 32 секунды Shamil1, иначе это не параметры, а это не описание. Добавлено через 1 минуту Shamil1, описание в вашем примере однозначно, но параметр не однозначен, потому что он зависит от какого-то text, который не определён на момент компиляции, я сто раз уже сказал об этом 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 12:29 [ТС]
	Shamil1, параметр может быть параметром, а параметрЫ не могут быть параметром Добавлено через 1 минуту Shamil1, вы согласны, что start_state должен быть определён перед вызовом? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 13:23 [ТС]
	Shamil1, я могу доказать, что функции Prog не существует. Что она вернёт, если передать ей саму себя? И во второй аргумент тоже. Верно, ничего, ответ не определён. Значит, функция Prog не существует. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 13:53 [ТС]
	Shamil1, как в пункте 4 вы определите, что она зациклилась? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:04 [ТС]
	Shamil1, чтобы она удовлетворяла спецификации, её нужно вызывать в соответствии со спецификацией. Сделайте это и результат будет соответствующий. Функция prog передаёт в Oracul некорректные параметры. В соответмтвии с этой спецификацией, это не Оракул, ведь Оракул зависит только от параметров, которые приходят ему на вход. 0