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

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

0

Проблема остановки

0

Простите за скрин, сижу оффлайн. Почему это не решение?

Миниатюры

 

0

Shamil1,

Добавлено через 1 минуту
Если эту функцию передать в себя с аргументом в качестве себя с аргументом в качестве себя..... и так до бесконечности, то она не зависнет и не ошибётся

0

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

Сообщение от Aycon Почему это не решение?

Решение какой задачи?

0

Почему он неправильный? По определению, которым вы поделились, Oracle делает:

Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.

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

Да, я слышал о теореме Гёделя о неполноте. Она доказывается через диагональный аргумент Кантора, который контринтуитивен и не кажется мне надёжным.

Добавлено через 4 минуты
Решение - решение проблемы остановки

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

0

Сообщение от Aycon Тьюринг привёл частный случай программы Oracle и опроверг его. В чём достижение?

Это не программа Oracle. Это вход, для которого гипотетический Оракул не сможет выдать правильный ответ.

Предположим, что Oracle(code, input) существует.
Подаём ему на вход code = input = "void F(string x) { while (Oracle(x, x)); }".

Вопрос, что вернёт Оракул?

1

Shamil1, мой вернёт true

Добавлено через 5 минут
Shamil1, хотя нет, в данном примере он вернёт false.

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

Добавлено через 3 минуты
Shamil1, всё я понял, кажется. Второй оракул лежит в условии выхода из цикла, но не в цикле. Да, он был прав.

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

Добавлено через 5 минут
Shamil1, сложная тема кароч, на грани полезности

Добавлено через 23 минуты
Shamil1, а если бы в данном примере все оракулы, кроме первого вернули бы false. Вы бы посчитали это корректным результатом? Все оракулы солгали бы кроме первого в рекурсии

0

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

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

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

Сообщение от Aycon Все оракулы солгали бы кроме первого в рекурсии

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

1

Shamil1, Да, вы правы. Пойду писать своего почти Оракула для анализа кода на brai**** без ограничений

0

Shamil1, прошу прощения за душноту, но у меня есть предложение чистой функции, которое решает данный парадокс.

Положение 1:
Представим себе множество всех программ, записанных в виде последовательности символов некоторого конечного алфавита. Например, в двоичном виде. Некоторые последовательности могут быть бесконечны в длинну, в соответствии с определением входных данных на бесконечной ленте машины Тьюринга. Таким образом, любая программа представима в виде последовательности (возможно бесконечной) символов конечного алфавита. Упорядочим набор таких последовательностей следующим образом:
1) На нечётных местах находятся последовательности бесконечной длинны, на чётных - последовательности конечной длинны.
2) Каждая конечная последовательность возрастает, если читать её справа налево.
3) Каждая бесконечная последовательность возрастает, если читать её справа налево от того места, начиная с которого в последовательности бесконечно идут нулевые символы.
4) Первая строка всегда заполнена единицами.

Таким образом, у нас есть следующая последовательность:
1111 1111 111...
0
0000 0000 000...
1
1000 0000 000...
01
0100 0000 000...
11
1100 0000 000...
...
И так далее.
По аналогии с диагональным аргументом Кантора, найдём такую последовательность символов, которой нет в данном порядке.
Для этого возьмём инвертированный бит первой строки, затем инвертированный бит третьей строки и так дальше для всех нечётных строк. Последовательность получится бесконечной длинны, таким образом она будет отличаться от всех чётных (конечных) записей. От всех нечётных записей, она будет отличаться по крайней мере одним битом. Таким образом, существует такая последовательность Q, которая не является ни одной из существующих программ. Запомним её.

Положение 2:
Оракул содержит исполняемый код в своей реализации, а также последовательность Q, которая не препятствует её исполнению.
В момент исполнения Оракул проверяет, существует ли данная последовательность во входных данных, и если существует - возвращает false, если количество таких последовательностей чётно и true, если количество - нечётно, если не существует - работает как оракул.

В чём я ошибаюсь?
Я полагаю, что диагональный аргумент Кантора не работает, это софистика, но я его использую, дабы исключить проблему остановки, либо его.

0

Сообщение от Aycon Представим себе множество всех программ, записанных в виде последовательности символов некоторого конечного алфавита.

Не совсем понятно, что за множество вы рассматриваете? Это множество каких-то выбранных вами алгоритмов? Или множество абсолютно всех существующих алгоритмов? Какова, на ваш взгляд, мощность такого множества?

0

Sindbad_M, всех алгоритмов.
Википедия говорит, что мощность - это характеристикиа конечного множества:

Мо́щность, или кардина́льное число́, мно́жества (лат. cardinalis ← cardo «главное обстоятельство; основа; сердце») — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

Добавлено через 37 секунд
Если я правильно понял

0

Сообщение от Aycon всех алгоритмов

т.е. абсолютно всех существующих алгоритмов, так?

Сообщение от Aycon Википедия говорит, что мощность - это характеристикиа конечного множества:

нет же:

Сообщение от Aycon характеристика множеств (в том числе бесконечных)

Ок. Спрошу проще. Сколько элементов в этом множестве?

0

А, ок, неправильно. Сейчас разберёмся

Добавлено через 1 минуту
Элементов бесконечно много. Мощность как у натурального ряда. Мне не приходит в голову последовательность, которой нет в этом множестве

Добавлено через 1 минуту
Sindbad_M, написал выше, забыл обратиться

0

Сообщение от Aycon Мне не приходит в голову последовательность, которой нет в этом множестве

как так? А Q?

И все-таки, чтобы потом не было недоразумений, вы рассматриваете множество абсолютно всех существующих алгоритмов, так?

0

Sindbad_M, да, так точно!

Q не принадлежит этому множеству, я не представляю себе такую последовательность. Ровно как и последовательность, которую выводят с помощью Диагонального аргумента Кантора. Поэтому я и говорю , что на мой взгляд его доказательство несостоятельно. Таким образом я хочу развеять одну из этих теорий - проблема останова или диагональный аргумент Кантора.

Добавлено через 3 минуты
Sindbad_M, Кроме того, если вы посмотрите внимательно, вы увидете, что эта последовательность Q -
0111 1111 1111 1111...

Хотя, я всё сделал по правилам, вроде бы.Кантор обошёл это нечестным путём, ведь он не указал в каком порядке мы упорядочиваем последовательность, а это важно. Я мог поступить также и сказать "упорядочим в каком-нибудь порядке", но я хочу разобраться, а не слукавить.

0

Aycon, ну если уж вы рассматриваете не просто последовательности из {0, 1}, а именно алгоритмы, то прежде чем вы перейдете к финалу - пляскам над диагональным аргументом, нужно проговорить множество деталей.

Итак,
1. Есть множество всех возможных алгоритмов. Если алгоритмы-оракулы существуют, то они также являются элементами этого множества, верно?

2. Что символизируют бесконечные цепочки {0, 1}? Обычно алгоритмом называют пусть и сколь угодно длинную, но конечную цепочку команд. Что такое алгоритм бесконечной длины?

Это если говорить об алгоритмах. Если же говорить о множествах, то

Сообщение от Aycon Мощность как у натурального ряда.

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

0

Sindbad_M,

1. Верно (догадываюсь к чему вы клоните)
2. Что-ж, позвольте уточнить, вы рассматриваете алгоритм без входных данных? (Лента Тьюринга)
Тогда да, только конечной. Это упростит мне задачу.
3. Если диагональный аргумент не работает - теория о мощностях множеств, которая на нём зиждется - тоже.

4. Как доказать отсутствие помледовательности, не входящей в описанный выше порядок? Не могу пока представить. У меня есть вопросы к периодическим (повторяющимся) последовательностям, а также иррациональные в двоичном представлении числа, то есть, когда их последовательность апериодична (т. е. все остальные), но я могу найти каждого их соседа слева и справа в порядке. Однозначно. А затем, по индукции если у них есть место в этом ряду, у их соседей есть место в этом ряду, у соседей их соседей есть место в ряду, то исходная последовательность и все её соседи в этом ряду. Мне кажется, это необходимое условие, но недостаточное. Не чувствую где цепляется...

0

Сообщение от Aycon вы рассматриваете алгоритм без входных данных?

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

Сообщение от Aycon , но я могу найти каждого их соседа слева и справа в порядке. Однозначно.

Запишем число Пи в виде бесконечной непериодической двоичной дроби и уберем символ разделения целой и дробной части. Для получившейся последовательности найдите левого и правого соседа.

0