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

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

0

Тут дело не в веришь - не веришь. Пока вы не смогли описать правила построения какой-либо цепочки. Все объяснения путаные, на уточняющих вопросах рассыпаются.

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

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

вы пытаетесь свести математическую проблему к вере в авторитеты.
Вы в восьмом классе в теорему Пифагора верили или разобрались с доказательством?

0

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

Добавлено через 1 минуту
Sindbad_M, задайте конкретный вопрос. Я дам конкретный ответ. Не о моей вере и попытках, а о моей функции.

0

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

Сообщение от Aycon генерация невозможна только бесконечных строк.

но ведь раньше было

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

вы постоянно бросаете нить рассуждений и вновь и вновь декларируете какие-то новые тезисы. И совершенно непонятно, то ли вы уже отказались от предыдущих утверждений, то ли просто раздумывете над ответом.

Ок. Пусть есть некоторая функция, которая возвращает текст программы на некотором алгоритмической языке. Дальше что? Эта функция умеет определять завершится та или иная из сгенерированных ей программ за конечное время?

0

Сообщение от Aycon генерация невозможна только бесконечных строк. Бесконечных программ не бывает

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

Примеры попроще есть:

https://ru.wikipedia.org/wiki/... стое_число

0

Sindbad_M, эта функция может упорядочить множество всех программ. С помощью неё можно сгенерировать последовательность символов, которой нет ни в одной из существующих программ, с помощью циклического сдвига каждого символа программы.Засовываете эту последовательность в оракула и он может определить своё присутствие в любом аргументе. Причём многократное. Таким образом это чистая функция и она может вернуть true, если найдёт себя во входных данных. Мы с вами об этом говорили, разве вы не помните? Или это издевательство надо мной?

Добавлено через 8 минут
vantfiles, без контекста и бабка с яйцами бывает, простите. Sindbad_M написал:

, 22:07[В закладки] [Окно ответа] 39 (permalink) Честно, не вижу смысла в написании какой-либо функции на каком-либо языке. Вполне можно мысленно представить или описать на естественном языке цепочку строк, которые будут генерироваться условной функцией. А учитывая то обстоятельство, что генерация некоторые строк с помощью вашей функции все равно практически не достижима, функция не имеет прикладного значения.

На что я ему ответил, что на практике не существует бесконечных программ. Ещё ни одна бесконечная по количеству символов программа ни была написана и не будет. Можно написать метод, который генерирует такую программу, но нельзя написать её, потому что у вас нет бесконечного количества памяти в реальности. Число пи есть, но никто его никогда не записал ещё целиком. С прикладной точки зрения бесконечных программ не существует. Я очень устал объяснять одно и то же, у меня истерика, я прошу вас, закройте этот вопрос и я больше никогда не напишу в этот раздел. Я не могу больше вывозить это, я хочу вскрыть себе вены.

0

Сообщение от vantfiles То есть иррациональные числа бывают, а программ нет.

Именно. Существование иррациональных чисел никак не обосновывает существование бесконечных программ.

Сообщение от vantfiles Примеры попроще есть:

Все "незаконные" числа по ссылке - натуральные, а не иррациональные.

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

Более того, их не существует и в теории. Под алгоритмом понимают конечный набор инструкций.

Сообщение от Aycon эта функция может упорядочить множество всех программ

Ок. Будем считать программы упорядоченными в том порядке, в котором функция их возвращает при последовательных вызовах.

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

Тут уже что-то странное начинает происходить. С помощью функции можно генерировать программу за программой и ничего более.

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

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

Сообщение от Aycon Засовываете эту последовательность в оракула и он может определить своё присутствие в любом аргументе.

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

Сообщение от Aycon это чистая функция и она может вернуть true, если найдёт себя во входных данных.

Вообще ничего непонятно в этой фразе. Как интерпретируется это true и какое отношение оно имеет к вопросу завершится ли та или другая программа?

Сообщение от Aycon Мы с вами об этом говорили, разве вы не помните?

Мы много о чем говорили. После предложения сформулировать теорию с чистого листа были "последнее натуральное число" и "бесконечные листинги", но "оракула определяющего свое присутствие в любом аргументе" точно не было.

Сообщение от Aycon Я очень устал объяснять одно и то же

Ровно потому, что ваши объяснения часто противоречат сами себе. Каждый раз, когда вы не смогли ответить на вопрос или опровергнуть утверждение следует считать, что вся(!) ваша теория признана несостоятельной. Да, вы строите новую теорию на основе старой. Но пишете только какой-то фрагмент. В результате получается какая-то каша из путанных пояснений. Намного продуктивнее будет каждый раз описывать ваш метод опровержения <что вы там хотите опровергнуть> c самого начала и до конца. С определениями, описанием, что такое в вашем понимании "оракул", "генерирующая функция", "программа" и т.д. Впрочем, при таком тщательном подходе вы самостоятельно будете находить ошибки в рассуждениях и на этом все завершится.

2

Сообщение от Sindbad_M Под алгоритмом понимают конечный набор инструкций.

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

0

Сообщение от vantfiles Алгоритм вывода всех натуральных чисел без использования цикла или рекурсии.

И? Что это за алгоритм?

0

Сообщение от Sindbad_M Что это за алгоритм?

Распечатать число 1
Распечатать число 2
Распечатать число 3
...

0

Этот алгоритм выводит только три первых натуральных числа

2

Sindbad_M,

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

Покажу как я это вижу. Программа Оракул, она же анализатор. Принимает на вход любое конечное множество символов языка brain****, который полон по Тьюрингу, если запущен на правильном интерпретаторе. Оракул - это функциия с одним аргументом (листингом программы) и возвращает истину (true), если в результате анализа выясняет, что программа в его аргументе остановится. И возвращает ложь, если программа не остановится. Предполагается, что на вход ей передаётся всегда корректная с точки зрения синтаксиса brain**** программа. Проблему останова можно описать с помощью псевдокода:
По определению, Оракул всегда останавливается и всегда даёт верный результат. Если Оракулу на вход подать исходный код функции Oracle Cracker, то он не сможет дать верный ответ. Его результат не определён. Оракул должен быть Чистой функцией без Побочных эффектов. Я полагаю, что без побочных эффектов Оракул может идентифицировать наличие вызова себя в функции OracleCracker и изменить возвращаемое значение таким образом, чтобы остановить функцию OracleCracker и вернуть истину (и не соврать в этом конкретном случае). Для этого я должен найти способ отличить исходный код вызова Оракула от любого другого кода. Для этого я собираюсь использовать зарезервированный кусок кода на brain****. А чтобы отличить его от обычного кода, я думал кодировать его следующим набором символов в порядке, который вызывает моя функция. Кажется, именно это не сработает, поскольку в Оракула передаётся не модифицированный предварительно код, однако я полагаю, что обнаружить своё присутствие в своём аргументе Оракул теоретически может (будучи чистой функцией) и проблема останова (в такой интерпретации) не имеет силы (не верна).

Добавлено через 14 минут
Sindbad_M, WriteResult конечно же

0

Сообщение от Aycon и возвращает истину (true), если в результате анализа выясняет, что программа в его аргументе остановится. И возвращает ложь, если программа не остановится.

Вот тут хотелось-бы подробностей. Вы знаете способ как по листингу произвольной корректной программы на Brain**** определить остановится ли она за конечное время?

0

Sindbad_M, конкретно - пока нет. Но проблема останова о том, что, дескать, даже теоретически это не возможно. Я хочу доказать обратное

0

Сообщение от Aycon конкретно - пока нет.

Если бы вы знали способ определения завершится ли тот или иной алгоритм, то ничего больше доказывать не требовалось бы. Просто предъявляете ваш алгоритм, и всё, неразрешимость проблемы останова опровергнута!

Но пока решения это задачи нет ни у кого. И нет никаких признаков, что это решение у кого-то появится. Да и доказано уже, ни у кого не появится.

Неразрешимость проблемы останова доказывается от противного. Делается предположение "допустим Анализатор (Оракул) существует". И из этого предположения выводится противоречие.

Но если при доказательстве от противного из предположения не выводится противоречия, то это совершенно ничего не значит. Отсутствие противоречия не подтверждает и не опровергает истинность пердположения.

Итого,
- если вы сможете построить Анализатор для Brain****, то ничего больше городить не требуется, анализатор подтверждает свое существование сам по себе
- если вы предполжите существование Анализатора, то в рамках этой же цепочки рассуждений не сможете подтвердить его существование. Вы сможете либо получить противоречие (что доказывает невозможность Анализатора), либо не получить противоречие, что ничего не доказывает.

0

Есть ли исключения из правила: "не существует правил без исключений"?

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

Добавлено через 4 минуты
Напоминает теорему Гёделя о неполноте.

0

Sindbad_M,

Да и доказано уже, ни у кого не появится.

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

Добавлено через 1 минуту
Sindbad_M, создать Оракула - непомерно более сложная задача, чем опровергнуть предположение о проблеме останова.

Добавлено через 2 минуты
Shamil1, которая также весьма спорная. Я полагаю, что и она не верна

0

Сообщение от Aycon Тьюринг допустил ошибку в рассуждениях

Ну тогда надо доказывать ошибочность рассуждений Тьюринга. Если Тьюринг допустил ошибку, то нужно именно на эту конкретную ошибку и указывать. А не растекаться мыслью по древу. И, видимо, начать с воспроизведения того фрагмента доказательства, которое содержит ошибку. Затем сформулировать, в чем ошибка заключается. Затем доказать сформулированное утверждение.

Сообщение от Aycon .важно только то, что оракул вернёт на самом верхнем уровне вложенности

Что такое "уровни вложенности" у Оракула? И использовал ли Тьюринг такое понятие в своем доказательстве?

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

Зависит от определения Оракула. Только зачем нам доказывать возможность существования неполноценного Оракула?

0

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

0

Сообщение от Aycon важно только то, что оракул вернёт на самом верхнем уровне вложенности.

Оракул - это функция. У неё нет уровней вложенности. И, кстати, в примере можно заменить вызов Оракула на код Оракула.

0

Shamil1, OraculCracker вызывает оракула и подаётся на вход оракулу. Это я и подразумеваю под словом вложенность. Я не вижу смысла в том, чтобы отказываться от общепринятой терминологии.

0