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

@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,

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .

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

	Проблема останова. В чём противоречие? 18.11.2021, 08:29. Показов 9342. Ответов 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