понятие вычислимой/невычислимой функции

[epros]

home-mik в сообщении #1513605 писал(а):

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

Общерекурсивная функция отличается от частично рекурсивной только всюду определенностью.

home-mik в сообщении #1513605 писал(а):

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

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

home-mik в сообщении #1513605 писал(а):

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

Что бы мы про этот алгоритм ни предположили, всё будет противоречивым. Это значит, что такого алгоритма не существует.

-- Пт апр 09, 2021 17:29:49 --

home-mik в сообщении #1513622 писал(а):

А число Busy Beaver $BB(n)$: его же находят по какой-то логике для количества состояний $n = 1,2,3,4$. Хоть перебором всех возможных машин, но это тоже алгоритм. В противном случае, если бы не было вообще никакого алгоритма, как бы его даже для этих четырех значений подсчитали бы?

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

[home-mik]

epros в сообщении #1513630 писал(а):

home-mik в сообщении #1513605
Что бы мы про этот алгоритм ни предположили, всё будет противоречивым. Это значит, что такого алгоритма не существует.

Формально - да, получается, что общего для всех алгоритмов не существует. Но это же исключительный случай: когда на вход алгоритма подается его же описание. Мы можем его исключить из рассмотрения, и тогда это доказательство, выходит, будет уже неверно, т.е. не будет доказано, что общего алгоритма определения останова не существует для всех алгоритмов, кроме него самого.

[epros]

home-mik в сообщении #1513636 писал(а):

Но это же исключительный случай: когда на вход алгоритма подается его же описание.

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

[arseniiv]

home-mik в сообщении #1513583 писал(а):

Т.е. в плане общего понимания, почему есть невычислимые функции, эта проблема останова и доказательство ее неразрешимости, мало что проясняет.

Тут прямее всего по идее должно быть уже упомянутое сравнение мощностей: мощность множества вычислимых функций $A \to B$ для некоторых «конструктивных областей» $A, B$ (например всяческих $\mathbb N^m$) всегда не больше, чем множество всех функций $A \to B$, и точно меньше для счётных. (Если взять оба конечные $A, B$, то окажется, что любая функция $A \to B$ вычислима, но для такого случая нет и проблемы остановки, и такие функции не тьюринг-полны.) И не нужно диагональных аргументов, потому что мощности вычисляются прекрасно без него.

-- Пт апр 09, 2021 22:17:15 --

home-mik в сообщении #1513636 писал(а):

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

Если мы исключим каким-то хитрым способом один случай, мы всё равно ничего не исправим. Тут ситуация ровно такая же как с неполнотой теорий первого порядка: если теория уже достаточно сильна, то добавление никакого количества аксиом без того чтобы сделать их множество рекурсивно неперечислимым, не исправит нам неполноту — или исправит в жирных кавычках, сделав теорию противоречивой. Это всё стороны одной и той же монеты, так что ничего подобного с вычислимостью вы провернуть не сможете, покуда рассматриваемый язык описания алгоритмов как минимум полон по Тьюрингу. Это как первый закон термодинамики — его не обойти новыми конструкциями вечных двигателей.

[tonven]

arseniiv в сообщении #1513672 писал(а):

и точно меньше для счётных

(Оффтоп)

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

[manul91]

epros в сообщении #1513653 писал(а):

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

А в этом вроде, что то есть?
Введем понятие "алгоритмической эквивалентности" (две кодировки машин Тьюринга называются "алгоритмически эквивалентными", если при одном и том же входе соответные машины выводят одно и то же на выход; либо обе зацикливаются).
Теперь поделим алгоритмов (относно возможности разрешать вопроса остановки других алгоритмов по их кодировки) на три класса:
1) Разрешающими (для любого алгоритма по его кодировки выдают верный ответ - останавливается или нет). Как доказано, этот класс пуст
2) "Оптимальными" - такие алгоритмы, которым дозволено ошибаться ТОЛьКО если у них на вход подана кодировка алгоритма принадлежащая их собственному классу алгоритмической эквивалентности. Для всех остальных кодировок/алгоритмов на входе, они дают верный ответ зацикливается или останавливается.
3) Всех прочих (т.е. включительно таких, которых ошибаются при оценки алгоритмов не из их собственного класса эквивалентности)

Тогда существование алгоритмов типа 2, вроде ничему не противоречит.
А это наилучшее, на что мы можем рассчитывать.

arseniiv в сообщении #1513672 писал(а):

сли мы исключим каким-то хитрым способом один случай, мы всё равно ничего не исправим. Тут ситуация ровно такая же как с неполнотой теорий первого порядка: если теория уже достаточно сильна, то добавление никакого количества аксиом без того чтобы сделать их множество рекурсивно неперечислимым, не исправит нам неполноту — или исправит в жирных кавычках, сделав теорию противоречивой. Это всё стороны одной и той же монеты, так что ничего подобного с вычислимостью вы провернуть не сможете, покуда рассматриваемый язык описания алгоритмов как минимум полон по Тьюрингу. Это как первый закон термодинамики — его не обойти новыми конструкциями вечных двигателей.

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

[mihaild]

manul91 в сообщении #1513690 писал(а):

Тогда существование алгоритмов типа 2, вроде ничему не противоречит.

Противоречит.
Для начала нужно уточнить - наш алгоритм $A$ получает на вход кодировку алгоритма и говорит, останавливается ли этот закодированный алгоритм на пустом входе. Пусть $x$ - код какого-нибудь алгоритма, который останавливается на пустом входе и отличается от $A$. Рассмотрим алгоритм $B$, который на входе $x$ выдает $0$, а получив пустой вход, запускает $A(\ulcorner B \urcorner)$ и инвертирует результат. Получаем всё то же самое.

manul91 в сообщении #1513690 писал(а):

чтобы теория была полной хотя бы относно всех других утверждений, которые НЕ сводятся к "геделевским утверждением" данной теории

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

[arseniiv]

(Оффтоп)

tonven в сообщении #1513686 писал(а):

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

Теория вычислительной сложности уже давно создана и активно развивается. Но тут-то обсуждаются другие вопросы, и я бы не сказал что они слишком абстрактные. Не слишком, во всякой абстракции есть своя нужда, но не все обязаны её видеть сразу же. (А иначе от абстракций было бы мало толку.)

И я бы не называл физические модели «евклидовскими». Пространство-время той же СТО псевдоевклидово, а нерелятивистской физики, галилеево, даже сложнее устроено. И чтобы наложить условия какой-то физической реализуемости, потребуется больше хитрой математики, а не меньше.

manul91 в сообщении #1513690 писал(а):

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

А что значит «не сводятся»?

[manul91]

mihaild в сообщении #1513693 писал(а):

Для начала нужно уточнить - наш алгоритм $A$ получает на вход кодировку алгоритма и говорит, останавливается ли этот закодированный алгоритм на пустом входе.

Пусть (при этом, А дозволено ошибаться если эта кодировка кодирует алгоритм того же класса как сам А).

mihaild в сообщении #1513693 писал(а):

Пусть $x$ - код какого-нибудь алгоритма, который останавливается на пустом входе и отличается от $A$.

Ок. Например код $x$ состоит из единственной команды "stop"

mihaild в сообщении #1513693 писал(а):

Рассмотрим алгоритм $B$, который на входе $x$ выдает $0$, а получив пустой вход, запускает $A(\ulcorner B \urcorner)$ и инвертирует результат.

Что значит обозначение $A(\ulcorner B \urcorner)$?

mihaild в сообщении #1513693 писал(а):

и инвертирует результат. Получаем всё то же самое.

Что значит "получаем все то же самое"?

-- 10.04.2021, 00:17 --

arseniiv в сообщении #1513695 писал(а):

А что значит «не сводятся»?

Геделево утверждение, с одной стороны является утверждением про самой теории типа парадокса лжеца (исходя из таких и таких-то аксиом, не существует такого доказательства что и т.д.).
С другой стороны, то же самое утверждение можно интерпретировать как утверждение насчет некоего свойства натуральных чисел - путем какой-либо однозначной кодировки.
Поскольку кодировок бесконечное множество - то и геделево утверждение представимо через бесконечно многих недоказуемых утверждений о натуральных чисел, назовем это множество $G$.
Т.е. если дано утверждение $X$ о натуральных чисел - "не сводится" в этом смысле, должно означать что "не существует кодировка геделевого утверждения, при котором оно сводится к $X$" - т.е. $X$ не принадлежит $G$.

Для таких утверждений $X$ - доказательство неполноты Геделя вроде не катит (по меньшей мере если в лоб) ибо оно требует хоть какой-либо кодировки себя чтобы получить соответного недоказуемого утверждения о натуральных чисел....

[arseniiv]

manul91 в сообщении #1513700 писал(а):

Что значит обозначение $A(\ulcorner B \urcorner)$?

$\ulcorner B \urcorner$ — это код $B$ (выраженный так, что его можно подать на вход $A$).

manul91 в сообщении #1513700 писал(а):

Поскольку кодировок бесконечное множество - то и геделево утверждение представимо через бесконечно многих недоказуемых утверждений о натуральных чисел, назовем это множество $G$.
Т.е. если дано утверждение $X$ о натуральных чисел - "не сводится" в этом смысле, должно означать что "не существует кодировка геделевого утверждения, при котором оно сводится к $X$" - т.е. $X$ не принадлежит $G$.

Для таких утверждений $X$ - доказательство неполноты Геделя вроде не катит (по меньшей мере если в лоб) ибо оно требует хоть какой-либо кодировки себя чтобы получить соответного недоказуемого утверждения о натуральных чисел....

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

[manul91]

arseniiv в сообщении #1513706 писал(а):

$\ulcorner B \urcorner$ — это код $B$ (выраженный так, что его можно подать на вход $A$).

Т.е. eсли у $B$ на входе подать $\ulcorner stop \urcorner$ то $B$ выдает 0, а если у $B$ подать пустой вход то он выдает $\neg A(\ulcorner B \urcorner)$.
Допустим $A(\ulcorner B \urcorner)$ выдает 0 (что интерпретируем как то что алгоритм $B$ на пустом входе останавливается); значит $B$ выдает 0 на вход $\ulcorner stop \urcorner$, и 1 на пустом входе.
Что дальше?

arseniiv в сообщении #1513706 писал(а):

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

Если не помните, откуда знаете что не единственный? Мне кажется, он по сути единственный (если возможны вариации - то только косметические, не меняющие "суть" - иначе как придем к противоречию? :))
Но даже если и так - не важно; тогда можно взять множество кодировок всех "аналогичных примеров".
Идея как бы понятна - требовать, чтобы теория была "настолько полной, насколько можно"; доказуемости утверждений (или их отрицаний) о натуральных чисел произходящих из кодировок всех геделевских примеров (если он не один такой) не требуем, для всех остальных - требуем.

[manul91]

arseniiv в сообщении #1513706 писал(а):

$\ulcorner B \urcorner$ — это код $B$ (выраженный так, что его можно подать на вход $A$).

Впрочем кажется я понял, о чем речь.
Кажется нужно слегка подправить определение "класса относно разрешения проблемы остановки" на котором разрешающим алгоритмам дозволено ошибаться
Пусть дан "оптимальный" разрешающий алгоритм $A$.
Алгоритм $B$ из "разрешенного для ошибок класса для $A$", если:
- Либо $A(\ulcorner B \urcorner)$ циклит а $B()$ нет, либо $B()$ циклит а $A(\ulcorner B \urcorner)$ нет (т.е. на соответных входов, поведение противоположно в смысле зацикленности)
Так прокатит? :)

[home-mik]

mihaild в сообщении #1513693 писал(а):

manul91 в сообщении #1513690 писал(а):

Тогда существование алгоритмов типа 2, вроде ничему не противоречит.

Противоречит.
Для начала нужно уточнить - наш алгоритм $A$ получает на вход кодировку алгоритма и говорит, останавливается ли этот закодированный алгоритм на пустом входе. Пусть $x$ - код какого-нибудь алгоритма, который останавливается на пустом входе и отличается от $A$. Рассмотрим алгоритм $B$, который на входе $x$ выдает $0$, а получив пустой вход, запускает $A(\ulcorner B \urcorner)$ и инвертирует результат. Получаем всё то же самое.

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

С точки зрения практики она, по-моему, малопригодна. На практике исследующий алгоритм $A$ является своего рода супервизором над исследуемым алгоритмом $B$, т.е. $B$ ничего не знает про $A$ и потому не может использовать результат его работы.

-- 10.04.2021, 05:45 --

arseniiv в сообщении #1513672 писал(а):

home-mik в сообщении #1513583 писал(а):

Т.е. в плане общего понимания, почему есть невычислимые функции, эта проблема останова и доказательство ее неразрешимости, мало что проясняет.

Тут прямее всего по идее должно быть уже упомянутое сравнение мощностей: мощность множества вычислимых функций $A \to B$ для некоторых «конструктивных областей» $A, B$ (например всяческих $\mathbb N^m$) всегда не больше, чем множество всех функций $A \to B$, и точно меньше для счётных. (Если взять оба конечные $A, B$, то окажется, что любая функция $A \to B$ вычислима, но для такого случая нет и проблемы остановки, и такие функции не тьюринг-полны.) И не нужно диагональных аргументов, потому что мощности вычисляются прекрасно без него.

Не совсем понял, почему мощность множества вычислимых функций $A \to B$ точно меньше, чем множество счетных. Можете пример привести?

[manul91]

home-mik в сообщении #1513714 писал(а):

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

Да, все правильно.
Однако как мне видится, тут проблема может быть в следующем.
Чтобы "исключить класс хитрых програм" (и не требовать правильности результата исследующего алгоритма $A$ если такие поданы ему на вход) - нужно "достаточно хорошим образом" уметь определять "является ли некий алгоритм $B$ хитрым" (относно исследующего $A$) или нет.
Даже если это суметь хорошо сформулировать (пока мне интересно, вообще существует ли разумная формулировка этого) - вполне может оказаться, что это тоже алгоритмически нерешимая задача.
Т.е. может оказаться что не существует универсальный алгоритм $Q$, который например если ему подать на вход кодировок $A$ и $B$ - отвечает "является ли $B$ хитрым относно $A$" (и соответно подлежащим исключения), или нет.
В таком случае, не будет возможности полноценно поделить алгоритмы на "хитрые" или "не хитрые" - а значит, вся идея "исключить из рассмотрения этот хитрый класс програм" сводится только к рукомахательством, а при этом реально не осуществима.
(Разумеется, мы могли бы тупо заявить что *по определению* все алгоритмы $B$ с которыми $A$ не справляется (не определяет правильно зацикливаются они или нет) являются "хитрыми" для $A$. Но это бессмысленно - любой алгоритм $A$ тогда будет являться "хорошим исследователем алгоритмов" - даже тот, что ничего не делает)

[home-mik]

manul91 в сообщении #1513715 писал(а):

home-mik в сообщении #1513714 писал(а):

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

Да, все правильно.
Однако как мне видится, тут проблема может быть в следующем.
Чтобы "исключить класс хитрых програм" (и не требовать правильности результата исследующего алгоритма $A$ если такие поданы ему на вход) - нужно "достаточно хорошим образом" уметь определять "является ли некий алгоритм $B$ хитрым" (относно исследующего $A$) или нет.
Даже если это суметь хорошо сформулировать (пока мне интересно, вообще существует ли разумная формулировка этого) - вполне может оказаться, что это тоже алгоритмически нерешимая задача.

Не знаю, разрешимая алгоритмически или нет, но то, что практически реализуемая, это уж точно : как я писал выше, нужно, чтобы исследуемая программа не получала результата работы исследующей, т.е. исследуемый алгоритм $B$ не принимает в качестве аргумента возвращаемое значение $A$. Ну, и контексты их работы, разумеется, изолированы, но это сугубо практическое замечание, для реализации на ЭВМ - для чистых функций, рассматриваемых в математике, это вроде само собой разумеется.