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

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

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

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

@Shamil1 · 20.05.2022, 14:07

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

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

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

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

Shamil1, оракул не принимает два текстовых параметра. Он принимает на вход функцию и требуемые ей параметры.

@Shamil1 · 20.05.2022, 14:12

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

Функция prog передаёт в Oracul некорректные параметры.

Не имеет никакого значения, что делает функция G. Это произвольная процедура и она может делать всё, что угодно. Главное, чтобы код скомпилировался.

На шаге 4 мы запускаем Вашу функцию F. Мы передаём ей пораметры согласно спецификации: первым аргументом - функцию, вторым аргументом - всё что угодно.

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

Shamil1, я не буду ничего доказывать, это не моя функция, она была предсказана Аланом Тьюрингом и спецификацию к ней писал он. Я доказываю только то, что его доказательство некорректно. Вы предоставили ваш аналог на c# и я доказал, что оно тоже некорректно, ведь вы полагаете, что оракул на вход принимает 2 строки, а это не так.

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

На шаге 4 мы запускаем Вашу функцию F. Мы передаём ей пораметры согласно спецификации: первым аргументом - функцию, вторым аргументом - всё что угодно.

И что потом? Ждёте? А сколько ждать будете? 10 минут? А если он выполнится за 11? Или через час?

@Shamil1 · 20.05.2022, 14:21

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

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Main()
{
    string text = @"bool Prog(string text)
{
    bool flag = Oracle(text, text);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}";
 
    bool res = Oracle(text, text);
 
    Console.WriteLine(res);
}

Что в данном вызове не соответствует спецификации?

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

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

А сколько ждать будете?

Подожду секунд 30.

@Shamil1 · 20.05.2022, 14:24

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

ведь вы полагаете, что оракул на вход принимает 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
void Main()
{
    string code = @"bool Prog(string text)
{
    bool flag = Oracle(Prog, text);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}
";
 
    var res = Oracle(Prog, code);
    Console.WriteLine(res);
}
 
bool Prog(string text)
{
    bool flag = Oracle(Prog, text);
    if (flag)
    {
        while (true) ;
    }
    else
    {
        return true;
    }
}
 
bool Oracle(Func<string, bool> g, object start_state)
{
    return false;
}

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

Shamil1,

Что в данном вызове не соответствует спецификации?

Собственно, вызов. Вы передаёте какие-то непонятные две строки, а Оракул ожидает одну функцию и множество аргументов для неё.

Подожду секунд 30.

Оракул не обязан выполняться за 30 секунд. Он может выполниться и за минуту и за 100000 лет

@Shamil1 · 20.05.2022, 14:30

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

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

Моя функция принимает строку. Поэтому "множество аргументов для неё" - это произвольная (без ограничений) строка.

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

Оракул не обязан выполняться за 30 секунд.

Я подожду 30 секунд, а потом спрошу у Вас, что вернёт Ваша функция.

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

Shamil1,

По описанию Оракул принимает на вход две строки. Но, если Вы хотите, могу переписать

По какому это ещё описанию? Дайте ссылку на источник, пожалуйста

@Shamil1 · 20.05.2022, 14:41

https://ru.wikipedia.org/wiki/... 0%BA%D0%B8
Даны описание процедуры и её начальные входные данные.

Процедура однозначно описывается её кодом на C#.
Начальными входными данными моей процедуры яляется произвольная строка.

Поэтому в данном случае Оракал принимает две строки: строку с кодом моей функции на C# и произвольную строку (какую я захочу).

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

Shamil1, тут ничего не сказанно про строки

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

Процедура однозначно описывается её кодом на C#.

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

@Shamil1 · 20.05.2022, 14:50

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

тут ничего не сказанно про строки

Какой тип параметров у моей функции?

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

Shamil1, тут - это на википедии, а не в вашей функции. Ваша функция может принимать хоть bazz

@Shamil1 · 20.05.2022, 14:52

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

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

Глобальное состояние моей функции - это та строка, которую я передаю в мою функцию.

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

Shamil1, да, это глобальное состоянние. Поведение вашей функции зависит от text. Что дальше?

@Shamil1 · 20.05.2022, 14:54

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

тут - это на википедии, а не в вашей функции. Ваша функция может принимать хоть bazz

Оракул должен работать для любых функций, в том числе и для моей. А для моей функции start_state - это строка.

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

Shamil1, не для любых, а для корректных

@Shamil1 · 20.05.2022, 14:57

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

да, это глобальное состоянние. Поведение вашей функции зависит от text. Что дальше?

И это глобальное состояние я передаю в Оракулу (см. строки 16 и 17 в моих последних примерах). В строгом соответствии со спецификацией.

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

Shamil1, он и работает. Только вы вызываете не оракула, а какую-то функцию, которая принимает 2 строки

@Shamil1 · 20.05.2022, 14:58

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

не для любых, а для корректных

Моя функция скомпилировалась, значит она корректная.

Новые блоги и статьи Все статьи Все блоги /
Рефакторинг программы уравнивания. 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. Показов 8933. Ответов 176 Метки нет (Все метки) Расскажите пожалуйста, в чём суть проблемы останова и как Тьюринг определяет и доказывает отсутствие оракула? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:09 [ТС]
	Shamil1, оракул не принимает два текстовых параметра. Он принимает на вход функцию и требуемые ей параметры. 0

@Shamil1 Модератор 3138 / 2286 / 469 Регистрация: 26.03.2015 Сообщений: 8,890
	20.05.2022, 14:41
	https://ru.wikipedia.org/wiki/... 0%BA%D0%B8 Даны описание процедуры и её начальные входные данные. Процедура однозначно описывается её кодом на C#. Начальными входными данными моей процедуры яляется произвольная строка. Поэтому в данном случае Оракал принимает две строки: строку с кодом моей функции на C# и произвольную строку (какую я захочу). 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:51 [ТС]
	Shamil1, тут - это на википедии, а не в вашей функции. Ваша функция может принимать хоть bazz 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:53 [ТС]
	Shamil1, да, это глобальное состоянние. Поведение вашей функции зависит от text. Что дальше? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:56 [ТС]
	Shamil1, не для любых, а для корректных 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 14:57 [ТС]
	Shamil1, он и работает. Только вы вызываете не оракула, а какую-то функцию, которая принимает 2 строки 0