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

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

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

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

@Sindbad_M · 06.05.2022, 18:53

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

а в чём заключается его неполноценность?

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

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

Оракул не обязан игнорировать вызовы себя.

непонятна. Но читается она как некоторое ограничение возможностей Оракула

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

OraculCracker вызывает оракула и подаётся на вход оракулу.

Определение OraculCracker-а у вас не наше.

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

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

И все равно не понимаю что такое вложенность. Рекурсивный вызов? Просто вызов одной функцией другой функции?

@Aycon · 11.05.2022, 08:22 **[ТС]**

Sindbad_M, я не понимаю, почему нам так трудно найти общий язык.
1--2 я не ограничиваю Оракула, читайте контекст, пожалуйста.
3 А какое ваше определение? Я ссылаюсь на сообщение в теме:

Shamil1:
Aycon,
Это "неправильный" анализатор. В доказательстве используется другой - который НЕ останавливается, если тестируемый алгоритм останавливается.

C#

C#
1
2
3
4
       
while(HaltedOutsideOracul(function, arguments))       
{             //Остановится          }      
//Не остановится          return 1;

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

@qtkoder777 · 12.05.2022, 10:14

Противоречие искать не надо. Гегель легализовал противоречия.

Метод контрпримера. Строится программа, на которой алгоритм проверки остановки всегда даст неправильный ответ. Одной такой программы достаточно чтоб сказать, что алгоритм проверки остановки, работающий всегда и везде, не существует. Вот эта программа

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

@Aycon · 16.05.2022, 06:51 **[ТС]**

qtkoder777, я указал как обойти это. Для вашего случая:
Программа найдёт вызов себя в функции Prog и вернёт false внутри функции, приведя к остановке Prog.
Если скормить ей Prog - вернёт true.
Повторюсь, это только для вашего случая предполагаемое поведение Oracle.
Функция чистая, поскольку изменила своё поведение только основываясь на аргументе. Всё легитимно. На этой программе не зависнет Oracle

Добавлено через 10 минут
qtkoder777, я по той же логике могу доказать, что программы "a+b" не существует. Контр пример: а - такое число, что "a + b = 0 && a != 0 для любого b". Числа a не существует. Как не существует и функции Prog, которая зависнет. По крайней мере в той конфигурации, в которой вы предоставили. Она может иметь такую реализацию, что её зависание не будет зависеть от Oracle, но в таком случае она не является аргументом в вопросе невозможности реализации Oracle. Oracle просто вернёт false

Добавлено через 6 минут
qtkoder777, или true, в зависимости от конкретного Prog

@Shamil1 · 16.05.2022, 09:24

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

Программа найдёт вызов себя в функции Prog и вернёт false внутри функции, приведя к остановке Prog.
Если скормить ей Prog - вернёт true.

Как она вернёт одновременно и true, и false?

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;
}

Что вернёт Proveritb_Ostanovky(text, text), если text = текст программы Prog?

@Aycon · 16.05.2022, 13:34 **[ТС]**

Shamil1, а что это вообще за функция с двумя аргументами?

Добавлено через 41 секунду
Shamil1, и что лежит в text?

Добавлено через 51 секунду
Shamil1, оракул принимает 1 аргумент. И что лежит в text?

Добавлено через 10 минут
Shamil1, Проинициализируйте text явно и вы всё поймёте. Либо вы пытаетесь создать бесконечную по длине программу (что запрещено), либо вложенность будет конечная и я могу ответить что выведет оракул для каждого конкретного вызова.

Добавлено через 2 минуты
Shamil1, напишите функцию, которая делает то, что вы хотите показать таким образом, чтобы она скомпилировалась.

@Shamil1 · 16.05.2022, 14:02

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

а что это вообще за функция с двумя аргументами?

Оракул - это функция с двумя аргументами (код программы и значения входных параметров программы)

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

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

таким образом, чтобы она скомпилировалась

нужно параметру функции тип строка указать

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

Shamil1, ошибка компилятора. Вы используете переменную text до инициализации

Добавлено через 2 минуты
Даже с указанием типа. Что вы конкретно напишете в text?

@Shamil1 · 16.05.2022, 14:32

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

Вы используете переменную text до инициализации

Как выглядит строка с вызовом функции Prog?

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

Что вы конкретно напишете в text?

Текст функции Prog.

Code
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;
}

синтаксическую ошибку только нужно исправить.

@Aycon · 16.05.2022, 15:01 **[ТС]**

Shamil1,

Как выглядит строка с вызовом функции Prog?

откуда мне знать?) Это ваш пример.
Я переведу на английский, если не возражаете.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//
bool Prog(string text)
{
    string args = text;
    bool flag = Oracle(text, args);
    if(flag)
    {
        while(true);
    }
    else
    {
        return true;
    }
}

Если вы запустите этот код, возникнет исключение на строке 0, что переменная непроинициализированна. Если вы проинициализируете её тем же листингом в строке 1 и запустите это, Oracle кинет исключение, ведь args не является константой времени компиляции. args зависит от text, а text внутри args непроинициализированно.
args =

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;
}

Тут не определена переменная text.

Добавлено через 7 минут
Shamil1, если вы подразумеваете, что это объявление функции, а не вызов - я соглашусь, оно скомпилируется, но если вы захотите вызвать функцию Prog, вы получите исключение, поскольку вы скармливаете оракулу некорректный аргумент.

Добавлено через 2 минуты
Shamil1, покажите Main с вызовом Prog, прошу вас.

@Shamil1 · 16.05.2022, 15:52

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;
}

@Aycon · 16.05.2022, 18:11 **[ТС]**

Shamil1, строка 3 переменная текст не определена в скобках. Аргумент не определён, от этого зависит исполнение функции.

Добавлено через 7 минут
Shamil1, можешь сказать, остановится ли эта функция?

C#
1
2
3
4
5
void Foo(int value)
{
    while(value > 10) {}
    return;
}

Она остановится, если value равно 3, 6 или 9, но не остановится, если value = 11.

Здесь нет противоречия, вы пытаетесь скормить функции неконстантное значение. Попробуйте скомпилировать это:

C#
1
2
3
4
5
void Foo(string value = string.Empty)
{
    while(value.Length > 10) {}
    return;
}

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

Добавлено через 1 минуту
Shamil1, И это логично, вы определили не все переменные.

Добавлено через 1 минуту
Shamil1, добавьте инициализацию text внутри кавычек

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

@Shamil1 · 16.05.2022, 19:19

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

Она остановится, если value равно 3, 6 или 9, но не остановится, если value = 11.

Поэтому Оракул принимает 2 аргумента - код функции и входные аргументы.

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

И это логично, вы определили не все переменные.

У меня программа отработала без ошибок.

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

добавьте инициализацию text внутри кавычек

В кавычках должен быть код функции Prog.

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

вы пытаетесь скормить оракулу бесконечную программу. Это лишено смысла для любой функции

Наоборот. Весь смысл Оракула - определить, является ли программа "бесконечной" (остановится или нет).

@Aycon · 16.05.2022, 19:48 **[ТС]**

Shamil1, должен быть, но оракул, которого вы вызвали внутри prog об этом не знает.Остановится программа или нет и является ли она бесконечной в размере исходного кода - это не одно и то же. Вы этого правда не видите или вы просто не понимаете о чём я говорю? Вы указали не все исходные данные.

Добавлено через 1 минуту
Shamil1, покажите мне программу целиком на брейнфак, которая сломает Оракула, пожалуйста. Всё остальное я доказать не могу.

Добавлено через 2 минуты
Shamil1, вы не ответили на мой довод, что аргумент функции Prog должен быть константой времени компиляции. Для вашего кода. Если хотите понять о чём я говорю, передавайте на вход statesment, а не текст. Ну или покажите аналог на брейнфак, если считаете, что он существует.

@Aycon · 16.05.2022, 19:54 **[ТС]**

Shamil1, https://ru.wikipedia.org/wiki/... prov=sfla1
Программа конечна ПО ОПРЕДЕЛЕНИЮ. Если вы собираетесь скормить Оракулу бесконечную последовательность любым способом, эта последовательность - не программа.

@Aycon · 16.05.2022, 20:05 **[ТС]**

Shamil1, чтобы это было возможно, я предлагаю условиться в следующем. Программа Оракул занимает ячейки от 0 до 9 (10 ячеек), а в 11-ую записывает 1, если считает, что программа справа - остановится и 2, если считает, что не остановится. Вы можете смещать указатель на 0 ячейку для "вызова" Оракула и смотреть результат в 10 ячейке.

@Shamil1 · 17.05.2022, 10:46

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

Программа конечна ПО ОПРЕДЕЛЕНИЮ. Если вы собираетесь скормить Оракулу бесконечную последовательность любым способом, эта последовательность - не программа.

Я соибраюсь скормить Оракулу вот этот конечный текст:

bool Prog(string text)
{
bool flag = Oracle(text, text);
if (flag)
{
while (true) ;
}
else
{
return true;
}
}

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

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

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

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

Добавлено через 6 минут
Код программы, которую я запускаю выглядит так:

C#
1
2
3
4
5
void Main(string[] args)
{
    bool res = Oracle(args[0], args[1]);
    Console.WriteLine(res);
}

@Aycon · 17.05.2022, 20:05 **[ТС]**

Shamil1, в определении Оракула ничего не сказанно про текст. В него передаётся описание процедуры и все необходимые ей параметры.
Попробуйте переименовать переменную text на text1 в аргументе и запустить без кавычек. Программа выдаст ошибку компиляции, потому что text1 не определён

Добавлено через 1 минуту
Shamil1, это говорит о том, что вы передаёте не всё, что подразумеваете. Любая программа делает ровно то, что вы ей сказали, а не то, что вы подразумеваете.

Добавлено через 20 минут
Представим программу string Sum(string a, string b), которая конвертирует аргументы в числа, складывает их и выводит сумму в виде строки:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Main()
{
    string val1 = "1";
    string val2 = "val1 - 3";
 
    string res = Sum(val1, val2);
    
    Console.WriteLine(res);
 
}
 
bool Sum(string val1, string val2)
{
    int a = Converter.ToInt32(val1);
    int b = Convert.ToInt32(val2);
 
    return (a + b).ToString();
}

Вы можете сказать, что выведет main? Не можете? Верно, не можете, поскольку возникнет исключение. Доказывает ли это, что функция Sum не существует? Нет, не доказывает - реализация представлена выше. Так и с вашим примером.

Добавлено через 8 минут
Shamil1, я не писал спецификацию, что Оракул принимает два текстовых аргумента. Я предложил спецификацию несколько постов назад, дополним её аргументами к функции.

bool Oracle(string code, string data)

Код code написан Строго на брейнфаке, data - это последовательность ascii символов на ленте данных при первом запуске программы на brain****. Покажите код на брейнфаке, который вы запишете в переменную code и строку, которую вы запишите в data таким образом, чтобы программа запусказась на интерпретаторе и доказывала, что Oracle не существует. Я признаю это и закрою тему, обещаю.

Добавлено через 14 минут
Shamil1, если вам сложно написать интерпретацию этой программы на брейнфаке (а это воистину невозможно), я предлагаю компромисс. Давайте условимся, что Оракул имеет такую спецификацию:
bool Oracle(Action<object> code, object data)

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

Добавлено через 1 минуту
Shamil1, более того, я докажу, что code в данном случае - это тьюринг машина, а в data можно поместить любую конечную ленту символов на исполнение.

@Shamil1 · 18.05.2022, 11:25

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

в определении Оракула ничего не сказанно про текст. В него передаётся описание процедуры и все необходимые ей параметры.

Текст, который я передаю, это и есть описание (код) процедуры. А вторым аргументом я передаю значения всех параметров для этой процедуры.

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

Попробуйте переименовать переменную text на text1 в аргументе и запустить без кавычек.

Зачем?

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

если вам сложно написать интерпретацию этой программы на брейнфаке (а это воистину невозможно)

Любую C# программу можно переписать на Брейнфак. Но я не хочу этим заниматься.

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

bool Oracle(Action<object> code, object data)

Оракул принимает код программы, а не какой-то Action.

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

более того, я докажу, что code в данном случае - это тьюринг машина, а в data можно поместить любую конечную ленту символов на исполнение.

Зачем это доказывать?

@vantfiles · 18.05.2022, 12:26

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

Любую C# программу можно переписать на Брейнфак.

И как же будет выглядеть подключение библиотеки и вызов библиотечной ф-ции?

Новые блоги и статьи Все статьи Все блоги /
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .

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

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

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 06:51 [ТС]
	qtkoder777, я указал как обойти это. Для вашего случая: Программа найдёт вызов себя в функции Prog и вернёт false внутри функции, приведя к остановке Prog. Если скормить ей Prog - вернёт true. Повторюсь, это только для вашего случая предполагаемое поведение Oracle. Функция чистая, поскольку изменила своё поведение только основываясь на аргументе. Всё легитимно. На этой программе не зависнет Oracle Добавлено через 10 минут qtkoder777, я по той же логике могу доказать, что программы "a+b" не существует. Контр пример: а - такое число, что "a + b = 0 && a != 0 для любого b". Числа a не существует. Как не существует и функции Prog, которая зависнет. По крайней мере в той конфигурации, в которой вы предоставили. Она может иметь такую реализацию, что её зависание не будет зависеть от Oracle, но в таком случае она не является аргументом в вопросе невозможности реализации Oracle. Oracle просто вернёт false Добавлено через 6 минут qtkoder777, или true, в зависимости от конкретного Prog 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 13:34 [ТС]
	Shamil1, а что это вообще за функция с двумя аргументами? Добавлено через 41 секунду Shamil1, и что лежит в text? Добавлено через 51 секунду Shamil1, оракул принимает 1 аргумент. И что лежит в text? Добавлено через 10 минут Shamil1, Проинициализируйте text явно и вы всё поймёте. Либо вы пытаетесь создать бесконечную по длине программу (что запрещено), либо вложенность будет конечная и я могу ответить что выведет оракул для каждого конкретного вызова. Добавлено через 2 минуты Shamil1, напишите функцию, которая делает то, что вы хотите показать таким образом, чтобы она скомпилировалась. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 14:25 [ТС]
	Shamil1, ошибка компилятора. Вы используете переменную text до инициализации Добавлено через 2 минуты Даже с указанием типа. Что вы конкретно напишете в text? 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 19:48 [ТС]
	Shamil1, должен быть, но оракул, которого вы вызвали внутри prog об этом не знает.Остановится программа или нет и является ли она бесконечной в размере исходного кода - это не одно и то же. Вы этого правда не видите или вы просто не понимаете о чём я говорю? Вы указали не все исходные данные. Добавлено через 1 минуту Shamil1, покажите мне программу целиком на брейнфак, которая сломает Оракула, пожалуйста. Всё остальное я доказать не могу. Добавлено через 2 минуты Shamil1, вы не ответили на мой довод, что аргумент функции Prog должен быть константой времени компиляции. Для вашего кода. Если хотите понять о чём я говорю, передавайте на вход statesment, а не текст. Ну или покажите аналог на брейнфак, если считаете, что он существует. 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 19:54 [ТС]
	Shamil1, https://ru.wikipedia.org/wiki/... prov=sfla1 Программа конечна ПО ОПРЕДЕЛЕНИЮ. Если вы собираетесь скормить Оракулу бесконечную последовательность любым способом, эта последовательность - не программа. Миниатюры 0

@Aycon 13 / 11 / 2 Регистрация: 07.05.2015 Сообщений: 418
	16.05.2022, 20:05 [ТС]
	Shamil1, чтобы это было возможно, я предлагаю условиться в следующем. Программа Оракул занимает ячейки от 0 до 9 (10 ячеек), а в 11-ую записывает 1, если считает, что программа справа - остановится и 2, если считает, что не остановится. Вы можете смещать указатель на 0 ячейку для "вызова" Оракула и смотреть результат в 10 ячейке. 0