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

[Sender]

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

Да вот хотя бы по определению из книжки Шеня:

Это не определение, а свойство.

[Someone]

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

Ну вот последнего утверждения как и следующей из него теоремы 1.5.1 я как раз и не пойму.

epros немного ошибся в своём ответе. Определить, является ли строка символов кодом алгоритма действительно можно, анализируя синтаксическую правильность (разумеется, разрабатывая способ кодирования, нужно об этом позаботиться). Проблема как раз в проблеме останова: чтобы применить диагональное построение, нам нужно из всех алгоритмов выбрать все те, которые определяют общерекурсивные функции, то есть, останавливаются при всех значениях аргумента. Однако не существует алгоритма, который по записи алгоритма определяет, останавливается тот или нет. Поэтому не существует алгоритма, перечисляющего все алгоритмы, вычисляющие общерекурсивные функции (и только их).

[epros]

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

Цитата:

Однако никакие меры не могут предотвратить зацикливание некоторых программ на некоторых входах, — и любые усилия в этом направлении бессмысленны.

Ну вот последнего утверждения как и следующей из него теоремы 1.5.1 я как раз и не пойму.

Вот этого последнего утверждения? А что в нём непонятного?

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

-- Чт апр 08, 2021 15:44:14 --

Кстати, а зачем было морочиться со всей этой ерундой, если из предположения, что есть алгоритм, нумерующий все частично рекурсивные функции $f_i(k)$, сразу следует, что функция $f_n(n)+1$ тоже частично рекурсивная, однако видно, что никакое $n$ не является её номером, а значит предположение было ложным?

-- Чт апр 08, 2021 15:56:55 --

А, ну да, какой-то $n$ может оказаться её номером, просто $f_n(n)$ может быть не определено.

Запутали Вы меня с этими дурацкими диагональными процедурами

[tonven]

home-mik
У Вас затык в непонимании диагонального метода. Проще его понять, используя не невычислимые функции, а невычислимые числа.
У Босса объяснение через алгоритмы, модель которых зиждется на интуиции. А это ненадёжная вещь.
Но вот представьте, работаете вы почтальоном. На почту приходят письма, их надо разнести по адресам. Берём самое старое из них и вручаем адресату. Затем следующее по сроку. И для любого письма мы можем указать день, когда мы понесём письмо.
Но приходит инструкция: "В первую очередь отправлять письма с пометкой "Срочно". И мы занимаемся только "срочной" почтой, так и не притронувшись к письмам обычным. Причём, эта тенденция бесконечна, т.е. нет никакой перспективы, что стопка обычных писем когда-либо уйдёт с почты. В этом ключевой момент: срок отправки и зацикливание, не дающее двигаться дальше.

[epros]

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

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

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

[home-mik]

Sender в сообщении #1513430 писал(а):

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

Да вот хотя бы по определению из книжки Шеня:

Это не определение, а свойство.

Да нет, вроде определение. Привожу полный фрагмент:

Цитата:

Функция $f$ с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм $A$, что

1) если $f(n)$ определено для некоторого натурального $n$, то алгоритм $A$ останавливается на входе $n$ и печатает $f(n)$;

2) если $f(n)$ не определено, то алгоритм $A$ не останавливается на входе $n$

Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве $A$ надо взять программу, которая всегда зацикливается).
2. Можно было бы изменить определение, сказав, так: "если $f(n)$ не определено, то либо алгоритм $A$ не останавливается, либо останавливается, но ничего не печатает". На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

Вот и возникает вопрос: если программа, вычисляющая функцию, зациклилась, функция невычислима или не определена? То же и с аналогией с почтальоном, который tonven двумя постами выше привел: там тоже зацикливание, которое получается можно и как неопределенность можно трактовать, и как невычислимость.

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

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

[Sender]

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

Да нет, вроде определение.

Напомню, вопрос был

Sender в сообщении #1513406 писал(а):

Что вы понимаете под неопределённостью функции?

Приведённый фрагмент не содержит ответа на него.

[home-mik]

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

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

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

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

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

[epros]

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

Вот и возникает вопрос: если программа, вычисляющая функцию, зациклилась, функция невычислима или не определена?

Вам же всё написали, что ещё может быть непонятно? Если функция представима алгоритмом, то она вычислимая, независимо от того, на каких аргументах он зацикливается.

А Вы думали, что для части аргументов функция вычислимая, а для других (для которых алгоритм зацикливается) - невычислимая? Так не бывает.

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

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

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

[home-mik]

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

Вот этого последнего утверждения? А что в нём непонятного?

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

Кстати, а зачем было морочиться со всей этой ерундой, если из предположения, что есть алгоритм, нумерующий все частично рекурсивные функции $f_i(k)$, сразу следует, что функция $f_n(n)+1$ тоже частично рекурсивная, однако видно, что никакое $n$ не является её номером, а значит предположение было ложным?

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

[пианист]

(Оффтоп)

Цитата:

Q: Следуя вашему FAQ "Как варить яйцо в микроволновке" я стал его варить, но оно взорвалось и сильно испачкало мне аппарат!
A: Вы должны были внимательно дочитать FAQ до конца, не прерывая чтение после названия.

[epros]

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

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

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

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

Пока в правильном направлении идёте, товарисчи (© В.И. Ленин).

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

А после того, как алгоритм отработает и вернет либо ноль (исследуемая программа останавливается), либо единицу (программа не останавливается) "дискредитируем" этот результат намеренно зациклив программу в первом случае, и остановив во втором. Получится, что алгоритм - гамно, из чего заключаем, что в общем случае такого алгоритма не существует.

Ой-ой, перемудрили. Зачем нам нули и единицы? Нам нужно, чтобы строго в том случае, когда исследуемый алгоритм не останавливается, проверяющий алгоритм остановился и напечатал: "Зацикливается". А в остальных случаях давайте сделаем так, чтобы проверяющий алгорим входил в бесконечный цикл.

Вопрос такой: Что будет, если подать для проверки (в качестве аргумента) код самого проверяющего алгоритма?

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

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

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

Поэтому для ВСЕХ алгоритмов либо есть способ определения наличия точки останова, либо нет. И теорема нам говорит, что алгоритм таковым способом быть не может (если, конечно, это не алгоритм с Оракулом).

-- Пт апр 09, 2021 14:03:42 --

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

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

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

Это же было прямым текстом написано, в том числе, в приводимых Вами цитатах из книжки. Как Вы не прочитали?

[home-mik]

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

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

Это же было прямым текстом написано, в том числе, в приводимых Вами цитатах из книжки. Как Вы не прочитали?

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

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

-- 09.04.2021, 14:34 --

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

Ой-ой, перемудрили. Зачем нам нули и единицы? Нам нужно, чтобы строго в том случае, когда исследуемый алгоритм не останавливается, проверяющий алгоритм остановился и напечатал: "Зацикливается". А в остальных случаях давайте сделаем так, чтобы проверяющий алгорим входил в бесконечный цикл.

Вопрос такой: Что будет, если подать для проверки (в качестве аргумента) код самого проверяющего алгоритма?

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

[home-mik]

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

Вам же всё написали, что ещё может быть непонятно? Если функция представима алгоритмом, то она вычислимая, независимо от того, на каких аргументах он зацикливается.

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

[Aritaborian]

(arseniiv)

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

Надо писать книгу.

«Цназария в стране Рекурсии».