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

@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 некорректные параметры. В соответмтвии с этой спецификацией, это не Оракул, ведь Оракул зависит только от параметров, которые приходят ему на вход.

Новые блоги и статьи Все статьи Все блоги /
Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .	Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .	Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .

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

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

@Shamil1 Модератор 3142 / 2290 / 469 Регистрация: 26.03.2015 Сообщений: 8,920
	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