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

[home-mik]

Всем доброго времени суток.

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

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

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

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

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

[Sender]

home-mik, а с существованием неразрешимых проблем готовы мириться?

-- Вт апр 06, 2021 14:12:35 --

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

[epros]

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

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

Где Вы взяли определение? В студию его плизз!

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

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

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

https://en.wikipedia.org/wiki/General_r ... e_function

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

Помимо общерекурсивности также стоит посмотреть частичную рекурсивносить, рекурсивную перечислимость, рекурсивную соперечислимость, примитивную рекурсивность.

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

Если любой, то как вообще функция может быть невычислима.

https://en.wikipedia.org/wiki/Busy_beaver

Если что, по ссылке - пример всюду определённой функции $\mathbb{N} \to \mathbb{N}$, которая не является общерекурсивной (вычислимой).

[arseniiv]

Есть некоторое неудобство в определении вычислимой функции вообще, потому что есть куча формализмов, эквивалентных между собой, но хороших с разных сторон*, и доказательства эквивалентности их между собой занимают время, и обобщение всех этих формализмов во что-то одно абстрактное скорее всего даст ещё более непонятное для изучающих впервые определение. Потому часто люди дают рукомахательное определение с каким-то «вычислителем», которое разумеется проваливается ровно там где и должно. Грустная ситуация.

* Например часто всё ограничивается либо функциями $\mathbb N^m \to \mathbb N$, либо функциями $\Sigma^* \to \Sigma^*$ для какого-то конечного алфавита $\Sigma$. Хотя вычислимые функции естественно рассматривать куда более широко. Или формализм заставляет совершать акробатические номера, чтобы доказывать и определять простые вещи типа композиции функций. Или ещё что-то…

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

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

[home-mik]

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

Где Вы взяли определение? В студию его плизз!

В книге Верещагина, Шеня "Вычислимые функции" такое определение:

Цитата:

Функция $f$ с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм $A$ , что
- если $f(n)$ определено для некоторого натурального $n$, то алгоритм $A$ останавливается на входе $n$ и печатает $f(n)$;
- если $f(n)$ не определено, то алгоритм $А$ не останавливается на входе $n$

И из книги В. Босс "Лекции по математике" том 6:

Цитата:

Целочисленную функцию $f(n)$ называют вычислимой, если существует алгоритм, вычисляющий значения $f(n)$, но необязательно приводящий к результату

А в первом посте я попытался своими словами дать определение, насколько ухватил суть из этих двух.

-- 06.04.2021, 17:07 --

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

home-mik, а с существованием неразрешимых проблем готовы мириться?

Ну, опять же: неразрешимых в рамках какой-то теории или теорий) Неразрешимой вообще - это строго говоря безосновательное утверждение, если только ты - не Господь Бог

[Sender]

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

В книге Верещагина, Шеня "Вычислимые функции" такое определение:

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

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

Ну, опять же: неразрешимых в рамках какой-то теории или теорий)

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

[epros]

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

В книге Верещагина, Шеня "Вычислимые функции" такое определение:

Цитата:

Функция $f$ с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм $A$ , что
- если $f(n)$ определено для некоторого натурального $n$, то алгоритм $A$ останавливается на входе $n$ и печатает $f(n)$;
- если $f(n)$ не определено, то алгоритм $А$ не останавливается на входе $n$

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

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

В итоге, в чём вопрос?

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

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

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

[пианист]

home-mik
Гляньте книжечку Роджерса "Теория рекурсивных функций и эффективная вычислимость", есть в сети, $\S 1.1$.

[svv]

home-mik, посмотрите тут примеры неразрешимых проблем:
https://en.wikipedia.org/wiki/List_of_u ... e_problems
Мне, например, понравился упомянутый там «карманный пример» такой проблемы — mortal matrix problem. В одном из её вариантов с доказанной алгоритмической неразрешимостью — даны $6$ целочисленных матриц $3\times 3$, требуется определить, существует ли составленное из них (возможно, с повторениями) конечное произведение, дающее нулевую матрицу.

Понятно, что в некоторых случаях (например, все $6$ матриц невырождены) на этот вопрос можно ответить быстро. Иногда может повезти, и Вы найдёте перебором такое произведение, если его можно составить из небольшого числа сомножителей. Но общего алгоритма нет. Грубо говоря, в общем случае для вывода о несуществовании такого произведения (когда его не существует) понадобилось бы проделать бесконечное количество вычислений.

[home-mik]

svv в сообщении #1513099 писал(а):

Понятно, что в некоторых случаях (например, все $6$ матриц невырождены) на этот вопрос можно ответить быстро. Иногда может повезти, и Вы найдёте перебором такое произведение, если его можно составить из небольшого числа сомножителей. Но общего алгоритма нет. Грубо говоря, в общем случае для вывода о несуществовании такого произведения (когда его не существует) понадобилось бы проделать бесконечное количество вычислений.

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

[svv]

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

Или беда в том, что перебирать придется до бесконечности?

Да. Проверив всевозможные комбинации $10^{100...000}$ множителей и не найдя нужной комбинации, Вы всё ещё не можете гарантировать, что её не существует.

Чтобы лучше почувствовать вкус этой задачи, приведу пример со stackexchange.com. Некто Peter взял две матрицы
$A=\begin{bmatrix}0&1&-1\\0&1&-1\\1&0&1\end{bmatrix}\quad\quad B=\begin{bmatrix}-1&0&1\\-1&-1&0\\-1&1&1\end{bmatrix}$
(Сразу оговорюсь, что для двух матриц $3\times 3$ никто не утверждает неразрешимости проблемы, тем не менее, пример показательный.) И Peter стал искать произведение этих матриц с повторениями, дающее нулевую матрицу. Я не проверял его результат, но он сообщает, что таковое отыскалось лишь для 17 сомножителей:
$ABBAAABBBBAABABBA=0$
Все произведения с меньшим числом множителей нуля не дали!

И вот мы для 6 матриц, не зная, существует комбинация или нет, проверили перебором все произведения вплоть до 16 (или 1000000, или...) множителей и ничего не нашли. Что делать, как рапортовать? (Естественно, я опираюсь на то, что алгоритмическая неразрешимость задачи $M(6, 3\times 3)$, как она там обозначается, доказана.)

[epros]

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

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

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

[home-mik]

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

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

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

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

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

[Sender]

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

когда алгоритм вычисления функции требует бесконечного числа шагов - функция неразрешима или не определена?

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

[epros]

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

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

Нет, нельзя. Я Вам давал ссылку на статью википедии про невычислимую функцию busy beaver. Формально значение функции определено для любого натурального аргумента. Но доказано, что она растёт быстрее любой вычислимой функции. Это значит, что сама эта функция не является вычислимой.

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