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

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

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

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

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

Shamil1,

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

В первый раз - да, но не во второй раз при вызове оракула. Там, в аргументе переменная text не определена. Это подмена понятий

@Shamil1 · 20.05.2022, 15:01

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

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

Я вызываю Оракула. Но, так как кода Оракула у меня нет, то я использую заглушку.

А как, по Вашему мнению, должна выглядеть спецификация (заглушка) Оракула на C#?

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

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

Там, в аргументе переменная text не определена. Это подмена понятий

Ничего не понимаю. Где именно переменная "текст" не определена?

@Aycon · 20.05.2022, 15:05 **[ТС]**

Shamil1, какой у неё результат в таком случае?

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

@Shamil1 · 20.05.2022, 15:12

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

какой у неё результат в таком случае?

Моя функция не изменяет начальное состояние. Поэтому значение параметра text будет оставаться тем, что задано в функции main.

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

это не важно, вы вызываете не оракул

А почему мне нельзя вызывать функцию оракул? Это же прекрасная чистая функция, которая обязательно вернёт мне true или false.

@Aycon · 20.05.2022, 15:21 **[ТС]**

Shamil1, я предположу как будет работать оракул. Он построит дерево исполнения и пометит ветви, которые ведут на своих родителей вне зависимости от исходных данных. А затем подставит в исходную функцию исходные данные и будет следить за её выполнением пошагово. Если на каком-то шаге алгоритм вызывает ветку, ведущую к рекурсии, оракул вернёт false.

Если при построении дерева алгоритм вызывает Оракула, но эта ветка не ведёт к её родителю (конечность её выполнениния не зависит от результата оракула), то он продолжает строить дерево в этой ветке как обычно, а если зависит, то помечает эту ветку как конечную. Если алгоритм при каких-либо исходных данных достигает этой ветки - он возвращает true.

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

Моя функция не изменяет начальное состояние. Поэтому значение параметра text будет оставаться тем, что задано в функции main.

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

Добавлено через 1 минуту
Shamil1, например, указать это явно во втором аргументе. Но почему-то вы яростно отказываетесь инициализировать переменную text во втором аргументе. Почему же?

@vantfiles · 20.05.2022, 15:55

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

предположу как будет работать оракул

https://ru.wikipedia.org/wiki/Гипотеза_Коллатца

Справится?

@Shamil1 · 20.05.2022, 16:06

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

Оракул внутри вашей функции не знает что творит ваша функция до его вызова и это ваше "поэтому" ей не очевидно.

А ему и не нужно знать. Это чистая функция. Она получила что-то на вход и обязана выдать правильный ответ. И этот ответ не должен зависить от предыдущих вызовов Оракула.

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

Это неизвестная переменная, которую нужно проинициализировать до вызова оракула

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

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

например, указать это явно во втором аргументе. Но почему-то вы яростно отказываетесь инициализировать переменную text во втором аргументе. Почему же?

Потому что внутри функции Prog я решаю, что передать вторым аргументом в функцию Оракул. Второй аргумент - это произвольная строка (потому что моя функция принимает произвольную строку). Вы же выдивигаете какие-то странные требования к её значению.

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

Shamil1, строка не подходит.

Добавлено через 40 секунд
Shamil1, предоставьте реализацию prog на брейнфаке

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

Добавлено через 3 минуты
vantfiles, если в какой-то момент обнаружится новый цикл, кроме 4-2-1, оракул это обнаружит и вернёт false, как и для любого другого числа. Если только, вы не задали условием выхода вход в цикл 4-2-1, тогда оракул вернёт истину для любого числа, кроме гиппотетического числа, которое нашло новый цикл.

@Shamil1 · 20.05.2022, 21:05

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

строка не подходит

Для чего не подходит строка и почему? Только обойдитесь без ограничений на код моей функции (кроме того, что этот код должен компилироваться).

Добавлено через 2 минуты
Напоминаю, что вторым аргументом Оракул должен уметь принимать любое значение, которое можно передать моей функции.

@Aycon · 22.05.2022, 04:48 **[ТС]**

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

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

@Shamil1 · 22.05.2022, 14:00

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

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

Нет. Не "только строку", а "в том числе и строку". Раз существует функция, которая принимает строку, то Оракул обязан принимать в том числе и строку.
Если говорить про C#, то тип string приводится к типу object. Это можно сделать для любых значенй типа string.

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

Или вы подразумеваете, что в этой строке может находиться любой сериализованный объект?

Нет.

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

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

Подходит. Во всех современных языках программирования функции описываются строкой (текстом).
Можно выполнить. Многочисленные компиляторы и интерпретаторы это делают.

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

По строке нельзя сказать, скомпилируется ли её содержимое и выполнится ли оно в том пространстве имён, в еотором запущено содержимое строки.

Код моей функции не содержит никаких пространств имён. Моя функция не зависит от окружения. Она зависит только от значения входного параметра.

p.s.
Возможно, так Вам будет легче понять:

C#
1
2
3
4
5
6
7
8
9
int Prog(string text)
{
    bool CopyPasteOfOracle(string code, object start_state)
    {
        return false;
    }
    int Cycle () => Cycle();
    return CopyPasteOfOracle(text, text) ? Cycle() : 0;
}

Эта версия функции, не вызывает Ваш Оракул и не использует переменных. CopyPasteOfOracle (я её написал) всегда возвращает то же, что и Ваш Oracle().

@Aycon · 22.05.2022, 23:00 **[ТС]**

Shamil1, этот код вы передаёте в text?

C#
1
2
3
4
5
6
bool Prog(text)
{
      bool b=Proveritb_Ostanovky(text, text);//true значит программа остановится, false значит программа зависнет
      if(b==true)Zavisnytb();
      if(b==false)return true;
}

Добавлено через 1 минуту
Shamil1, он компилируется? Зависает? Нет? Оракул вернёт - false

Добавлено через 4 минуты
Shamil1, если в text вы передаёте какой-то другой код - покажите его ещё раз, пожалуйста.

@Shamil1 · 23.05.2022, 11:57

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

этот код вы передаёте в text?

Вот этот:

C#
1
2
3
4
5
6
7
8
9
int Prog(string text)
{
    bool CopyPasteOfOracle(string code, object start_state)
    {
        return false;
    }
    int Cycle () => Cycle();
    return CopyPasteOfOracle(text, text) ? Cycle() : 0;
}

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

он компилируется? Зависает? Нет? Оракул вернёт - false

Он компилируется.
Если Ваш Оракул вернёт false, то этот код не зависает. Значит, Ваш Оракул ошибается.

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

@Aycon · 23.05.2022, 17:42 **[ТС]**

Shamil1,

C#
1
2
3
4
5
6
7
8
9
10
int Prog(string text) 
{     
    bool CopyPasteOfOracle(string code, object start_state)
    {         
        return false;  
    }     
    
    int Cycle () => Cycle();
    return CopyPasteOfOracle(text, text) ? Cycle() : 0; 
}

Я запустил этот код и он выдал ошибку компиляции, ведь Cycle() не определён. Даже когда я заменил вызов оракула на false, а cycle() на while(true); - код скомпилировался и выполнился без зависаний. Ведь это только объявление функции, а не её вызов. Оракул правильно вернул false. Попробуйте сами.

Добавлено через 1 минуту
Shamil1, конкретно этот код, если заменить Cycle() компилируется и не зависает.

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

C#
1
2
3
4
5
6
7
8
9
10
11
int Prog(string text)
{         
   bool CopyPasteOfOracle(string code, object start_state)
   {              
      return false;      
   }
 
   if(CopyPasteOfOracle(text, text))
      while(true);
   return 0;
}

@Shamil1 · 23.05.2022, 17:49

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

Я запустил этот код и он выдал ошибку компиляции

Я не знаю, какой компилятор выдал Вам ошибку и какую ошибку он Вам выдал. У меня этот код компилируется.

Вот тут тоже компилируется:
https://www.programiz.com/csha... -compiler/

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

ведь Cycle() не определён

Cycle() определена в строке 8.

@Aycon · 23.05.2022, 17:53 **[ТС]**

Shamil1, Да, прошу прощения. Скомпилировалась. Но не зависла. Оракул верно ответил false. Как это доказывает его невозможность?

@Aycon · 23.05.2022, 18:02 **[ТС]**

Shamil1, кароче, брехня эта проблема останова и теорема Гёделя о неполноте тоже брехня. Как и вся теория вычислимости.

@Shamil1 · 23.05.2022, 19:09

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

Оракул верно ответил false.

false означает, что программа не остановится (то есть, зависнет). Оракул ответил неверно.

@Aycon · 23.05.2022, 21:08 **[ТС]**

Shamil1, ок, я заменил на true и программа не зависла

@Aycon · 23.05.2022, 21:10 **[ТС]**

Shamil1,

Новые блоги и статьи Все статьи Все блоги /
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .

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

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

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

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	20.05.2022, 17:02 [ТС]
	Shamil1, строка не подходит. Добавлено через 40 секунд Shamil1, предоставьте реализацию prog на брейнфаке Добавлено через 2 минуты vantfiles, да, как и с факторизацией очень большого полупростого числа. Только анализ может быть сопостовим по времени с вызовом самой функции. Добавлено через 3 минуты vantfiles, если в какой-то момент обнаружится новый цикл, кроме 4-2-1, оракул это обнаружит и вернёт false, как и для любого другого числа. Если только, вы не задали условием выхода вход в цикл 4-2-1, тогда оракул вернёт истину для любого числа, кроме гиппотетического числа, которое нашло новый цикл. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	22.05.2022, 04:48 [ТС]
	Shamil1, строка не подходит в качестве описания функции, потому что строку нельзя выполнить или построить по ней граф исполнения. По строке нельзя сказать, скомпилируется ли её содержимое и выполнится ли оно в том пространстве имён, в еотором запущено содержимое строки. Всё это касается и аргумента в общем случае. Добавлено через 3 минуты Shamil1, когда вы передаёте вторым аргументом строку оракулу, вы подразумеваете, что любая функция может принимать только строку в качестве аргумента? Или вы подразумеваете, что в этой строке может находиться любой сериализованный объект? В таком случае ваша строка нуждается в интерпретации, верно? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	23.05.2022, 17:53 [ТС]
	Shamil1, Да, прошу прощения. Скомпилировалась. Но не зависла. Оракул верно ответил false. Как это доказывает его невозможность? Миниатюры 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	23.05.2022, 18:02 [ТС]
	Shamil1, кароче, брехня эта проблема останова и теорема Гёделя о неполноте тоже брехня. Как и вся теория вычислимости. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	23.05.2022, 21:08 [ТС]
	Shamil1, ок, я заменил на true и программа не зависла 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	23.05.2022, 21:10 [ТС]
	Shamil1, Миниатюры 0