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

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

Новые блоги и статьи Все статьи Все блоги /
FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .

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

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