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

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

0

Sindbad_M, давайте условимся, что алгоритм рассматривается в отрыве от входных данных и конечен (это мешает бесконечной Q существовать, но это можно обойти.

2) да, могу. Исходная:

141592...

Слева:
041592...

Справа:
241592

Так, что-то тут нечисто)

0

Сообщение от Aycon Слева: 041592... Справа: 241592

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

И обсуждаемая последовательность должна быть такой:

3,1415... --> 11.00100100001111110111... --> 1100100100001111110111...

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

Хотя тут внимательнее прочитал ваши правила упорядочивания, вы упорядочиваете последовательности, читая их справа налево. И как тогда определить место и соседей для последовательностей правая часть которых бесконечна и непериодична? Допустим, мы развернем все такие последовательности, пусть неопределенной будет левая часть:

...1110111111000010010011

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

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

0

Sindbad_M, при всём уважении, вы задали мне задачу с числом Pi, я предложил её решение. Эта последовательность - не алгоритм. В последнем сообщении я предложил условиться, что алгоритм конечен и рассматривается в отрыве от исходных данных.

Добавлено через 1 минуту
Sindbad_M, если вы уже перевернули последовательность - очень легко, слева на единицу меньше - справа на единицу больше.
Предлагаю вернуться к конечным последовательностям. Полагаете, её нельзя пронумеровать в натуральных числпх?

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

0

Aycon, если бесконечные цепочки (алгоритмы) выведены из рассмотрения, то все ваши рассуждения нужно проделать заново, от начала до конца. Сделаете - обсудим.

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

0

Sindbad_M, извольте, для конечных последовательностей.
Берём длинну последовательности, в двоичном виде. Например 101 - 6 элементов.

Генерируем последовательность простых чисел:
2, 3, 5, 7, 11....
Берём каждое второе число и умножаем их на маску длинны.
Отобранные числа: 3, 7, 13.
Шаблон: 1 0 1
Результат: 1*3 * 0*7 * 1*13 = 99 (убираем нулевые)

Берём оставшиеся простые числа - каждое нечётное и умножаем их на биты последовательности, например на 100011.
Получаем число Y.
Умножаем Y на 99. И получаем число K.

Число K и будет нашим номером в таблице. Записи не будут повторяться.

0

Сообщение от Aycon извольте,

Не, не, не
Нужно начать со слов "Представим себе множество всех программ, записанных в виде конечной последовательности символов некоторого конечного алфавита. Например, в двоичном виде...." и т.д. построить опровержение доказательства проблемы останова от начала до конца.

0

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

0

Aycon, все ваше рассуждение рассыпается если из него убрать бесконечные цепочки. И правила упорядочивания. И бесконечная цепочка Q уже не алгоритм. Старое рассуждение поломалось, несите новое, обсудим.

0

Sindbad_M, сортируете как я описал.
Ищете последовательность, которой нет в ряду. Это очень легко, это будет любое произведение с двумя или большим количеством простых чисел в произведении. Например, число 4. В него не свернётся ни одна программа. Без данных. Добавляете число 4 в свою программу и это и есть ваш идентификатор

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

0

Aycon, вы строите очередную квадратуру круга. Очевидно же, что это работает только потому, что вы в рассуждениях допустили ошибку. Когда всё рассуждение было собрано вместе, слабые места были видны как на ладони. Все эти заплатки "см. выше, там все написано" не формируют полного и понятного рассуждения. Что толку от сортировки без алгоритма нахождения Q, которое "одновременно принадлежит множеству и не принадлежит множеству"? Соберите все заплатки в одном месте и обсудим.

1

Sindbad_M,
Наверное, вы правы. Я не могу решить эту задачу

0

Sindbad_M, вероятно, на выходных или немного позже я смогу предоставить реализацию функции на c#, которая может вернуть любую программу на языке brain****. Конечные по длинне листинги программы будут возвращаться за конечное количество итераций функции, бесконечные листинги только за бесконечные. Функция будет возвращать бесконечный IEnumerable<string>. Это одномерное множество, в котором будут упакованы все строки (конечные и бесконечные) любого конечного алфавита. Вы рассмотрите моё решение, или мне не стоит браться за это?

Добавлено через 6 минут
Sindbad_M, это было бы физическим воплощением опровержения диагонального аргумента Кантора, полагаю.Если сгенерировать последовательность по его методу, то для этой последовательности также будет место в перечислении, которое вернёт моя функция.

Добавлено через 4 минуты
Sindbad_M, я не смогу назвать порядковый номер последовательности Кантора в перечислении, которое вернёт моя функция, поскольку это число бесконечно велико, но для любой конечной или бесконечной последовательности я могу точно сказать левее или правее она находится относительно другой последовательности в перечислении.

Добавлено через 9 минут
Sindbad_M, в общем, я соберу все заплатки вместе)

0

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

И что на практике означает возврат бесконечного листинга? Это ведь означает что функция не завершится никогда, значит такая функция не может претендовать на роль Анализатора.

И, судя по всему, эта функция генерирует что-то, но не последовательности по алгоритму изложенному Кантором.

Также проблема в том, что невозможно предсказать не только номер последовательности в перечислении. Вы не можете также назвать ближайших соседей произвольной последовательности. Вообще, множество ваших последовательностей более чем счетно. А в доказательстве неразрешимости проблемы останова рассматривается именно счетное множество алгоритмов: https://ru.wikipedia.org/wiki/Проблема_остановки

0

Sindbad_M, паттерн итератор. В методе используется оператор yeld. Это сложно объяснить в двух словах, это синтаксический сахар языка программирования. Аргументов не будет. Каждый раз при вызове функции она возвращает вам новый сгенерированный листинг программы. В строгом порядке и без повторений.

0

А зачем? Какое отношение это имеет к проблеме останова?

1

Sindbad_M,

Сообщение от Aycon Представим себе множество всех программ, записанных в виде последовательности символов некоторого конечного алфавита. Например, в двоичном виде. Некоторые последовательности могут быть бесконечны в длинну, в соответствии с определением входных данных на бесконечной ленте машины Тьюринга. Таким образом, любая программа представима в виде последовательности (возможно бесконечной) символов конечного алфавита. Упорядочим набор таких последовательностей следующим образом

Я собираюсь создать функцию, при каждом вызове которой, возвращается новый листинг программы без повторений и без пропусков. В том числе и бесконечный (если вам удастся запустить эту функцию бесконечное количество раз) что доказывает, что это множество можно поставить в соответствие натуральным числам. Значит их размерности совпадают.
Важно понимать, что все бесконечные последовательности в листинге сгенерируются "в конце" после предельного перехода, но в строгом порядке (в соответсвии с алгоритмом функции) и без повторений. Да, это невозможно в действительности, но вы тоже не можете вывести все натуральные числа и "последнее натуральное число" (запомните пожалуйста термин) можно вывести после предельного перехода.

Сообщение от Sindbad_M И что на практике означает возврат бесконечного листинга? Это ведь означает что функция не завершится никогда, значит такая функция не может претендовать на роль Анализатора.

Это итеративная функция, которая также выводит итератор каждый раз при обращении. Это значит она возвращает объект, который может вернуть следующий элемент последовательности (конечной или бесконечной последовательности символов в листинге) за конечное время. Это значит, что вы можете вывести любое конечное количество символов листинга за конечное время или весь бесконечный листинг за бесконечное время, как если бы вы считали все натуральные числа от 0.

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

Сообщение от Sindbad_M Также проблема в том, что невозможно предсказать не только номер последовательности в перечислении. Вы не можете также назвать ближайших соседей произвольной последовательности.

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

Сообщение от Sindbad_M Вообще, множество ваших последовательностей более чем счетно. А в доказательстве неразрешимости проблемы останова рассматривается именно счетное множество алгоритмов

Это неверно. Когда я напишу функцию, я это докажу.

Сообщение от Aycon По аналогии с диагональным аргументом Кантора, найдём такую последовательность символов, которой нет в данном порядке. Для этого возьмём инвертированный бит первой строки, затем инвертированный бит третьей строки и так дальше для всех нечётных строк. Последовательность получится бесконечной длинны, таким образом она будет отличаться от всех чётных (конечных) записей. От всех нечётных записей, она будет отличаться по крайней мере одним битом. Таким образом, существует такая последовательность Q, которая не является ни одной из существующих программ. Запомним её.

Это возможно, потому что я могу добавить к натуральному ряду ещё одно число и его размерность останется такой же. Пример: натуральный ряд: 0, 1, 2, 3, 4... Новый ряд: А, 0, 1, 2, 3, ...
В общем случае к любому бесконечному ряду я могу добавить любое конченое количество элементов. По диагональному аргументу Кантора следует, что для любого двумерного (по его определению) перечисления я могу найти такую последовательность.

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

Собственно да.
Из этого следует, что либо может существовать Оракул, либор не работает диагональный аргумент Кантора, либо и то и другое.

Добавлено через 18 минут
Sindbad_M, Все программы можно отобразить во множество натуральных чисел с помощью паттерна (числового) ABACABAD... ABACABA pattern

Добавлено через 4 минуты
Sindbad_M, С точки зрения алгоритма это означает обход бесконечного в ширину и бесконечного в глубину дерева.

0

Я все никак не могу понять, а вы постоянно путаетесь при объяснении, что за таинственные "некоторые бесконечные последовательности"? Вот например:

Сообщение от Aycon Важно понимать, что все бесконечные последовательности в листинге сгенерируются "в конце" после предельного перехода,

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

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

Сообщение от Aycon "последнее натуральное число" (запомните пожалуйста термин)

В математике нет такого термина. Дайте определение.

Вообще, любое натуральное число записывается конечной последовательностью цифр
И для любого натурального числа N существует (N+1) - натуральное число

Сообщение от Aycon Все программы можно отобразить во множество натуральных чисел с помощью паттерна (числового) ABACABAD... ABACABA pattern

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

0

Sindbad_M, Короче, я всё покажу, когда напишу эту функцию

0

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

0

Sindbad_M, можно, но вы мне не поверили(

Добавлено через 3 минуты
Sindbad_M, я уверен, что если вам покажут работающего Оракула, даже если это будет лично Тьюринг, вы скажете, что он ошибся

0