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

[Null]

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

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

Вот в случае отрицательного ответа и будет перебирать бесконечно.

[epros]

Null в сообщении #1513290 писал(а):

Вот в случае отрицательного ответа и будет перебирать бесконечно.

У функции busy beaver нет аргументов, в которых функция не определена. Классическая логика в лице закона исключённого третьего утверждает: "Любая машина Тьюринга либо остановится, либо нет". Это значит, что из любого конечного множества машин Тьюринга можно выбрать такую, которая останавливается и перед этим записывает на ленту максимальное количество символов.

[arseniiv]

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

Вычислимая функция - это и есть алгоритм.

Надо отметить для ТС, что могут считать и то, что это класс эквивалентности алгоритмов по тому, одинаковые ли они результаты выдают (включая $\bot$) на все входы. Но само это экстенсиональное равенство конечно же в общем случае неразрешимо, так что в конструктивном контексте от него не очень много толку и можно тогда считать сам алгоритмом и функцией. Или можно считать, что совокупность вычислимых [частичных] функций не образует множества, а образует предмножество, которое отличается от множества ровно тем, что от его элементов отодрали равенство и мы не можем больше знать, равны они или нет (но мы можем вводить разные отношения эквивалентности*, превращая предмножество во всяческие множества, между которыми есть натуральные проекции).

( ∗ )

* Можно подумать, что для установления того, что отношение — эквивалентность — нужно равенство из-за рефлексивности. На деле же мы в таком случае вообще скорее всего будем считать отношением (пред)функцию, которая двум элементам нашего множества сопоставляет предмножество, населённость или ненаселённость которого говорит о том, находятся элементы в отношении или нет (можно считать элементами такого множества всевозможные способы связать два элемента). На языке теории типов мы дальше можем записать требования к отношению $\sim$, чтобы оно было эквивалентностью, как наличие трёх (пред)функций

$$\mathrm{refl} \colon (x \colon X) \to (x \sim x)$$ $$\mathrm{sym} \colon (x \colon X) \times (y \colon X) \times (x \sim y) \to (y \sim x)$$ $$\mathrm{trans} \colon (x \colon X) \times (y \colon X) \times (z \colon X) \times (x \sim y) \times (y \sim z) \to (x \sim z).$$

И к примеру чтобы назвать предфункцию $f \colon X \to Y$ функцией из $(X, \sim_X)$ в $(Y, \sim_Y)$, нам надо будет показать, что населён тип

$$(x \colon X) \times (y \colon X) \times (x \sim_X y) \to (f(x) \sim_Y f(y)),$$

то есть предоставить алгоритм, переводящий свидетеля равенства элементов в свидетеля равенства их образов при $f$.

[ET]

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

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

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

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

[home-mik]

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

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

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

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

Мне в этом примере непонятно вот что: задача вычисления числа Busy Beaver $BB(n)$ для произвольного $n$ и задача подтверждения, что какие-то машины Тьюринга не останавливаются, это две разные задачи или суть одна и та же?

-- 08.04.2021, 11:26 --

ET в сообщении #1513367 писал(а):

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

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

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

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

Это пример с диагональным составлением невычислимой функции, насколько я понимаю. Его я тоже, кстати, до конца не пойму. Когда перечисляют все вычислимые функции $f_{1}(n), f_{2}(n), f_{3}(n) ... f_{k}(n)$, а потом вводят $g(n) = f_{n}(n) + 1$. Да, $g(n)$ получается не совпадает ни с одной из этих выше перечисленных вычислимых функций. С другой стороны очевидно, что прибавление единицы не делает ее невычислимой для машины Тьюринга то уж точно. Т.е. она должна быть вычислимой.

Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

И самое главное, как это на практике выглядит? Ведь на практике мы по этому диагональному рецепту невычислимую функцию никогда не составим. Потому что всегда можно будет число вычислимых функций $f_{n}(n)$ дополнить новым экземпляром в том же программном алфавите так, что построенная до этого $g(n)$ будет уже вычислима.

[epros]

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

Мне в этом примере непонятно вот что: задача вычисления числа Busy Beaver $BB(n)$ для произвольного $n$ и задача подтверждения, что какие-то машины Тьюринга не останавливаются, это две разные задачи или суть одна и та же?

Это одна задача. $\Sigma(n)$ определяется так: Нужно взять все машины Тьюринга с количеством состояний не более $n$ (их конечное количество), стартующие с пустой ленты. Среди тех машин, которые останавливаются, выбрать такую, которая записала на ленту максимальное количество символов (такая машина и называется busy beaver). Вот это количество символов и есть $\Sigma(n)$.

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

[home-mik]

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

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

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

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

[Sender]

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

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

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

[epros]

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

Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

Вы что-то неправильно прочитали. Дело не в том, что $f_{n}(n)+1$ не определена для любого $n$, а в том, что нет алгоритма, нумерующего все вычислимые функции, а потому функция, аргументом которой является номер вычислимой функции, не является вычислимой.

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

И самое главное, как это на практике выглядит? Ведь на практике мы по этому диагональному рецепту невычислимую функцию никогда не составим. Потому что всегда можно будет число вычислимых функций $f_{n}(n)$ дополнить новым экземпляром в том же программном алфавите так, что построенная до этого $g(n)$ будет уже вычислима.

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

[home-mik]

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

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

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

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

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

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

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

[Sender]

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

[epros]

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

И для этого надо их запустить и подождать бесконечное количество времени) Т.е. сама последовательность действий то ясна, просто надо бесконечное количество времени для получения результата.

Это очень странная трактовка. Если алгоритм не останавливается, значит и "результата" у него никакого не будет.

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

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

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

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

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

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

-- Чт апр 08, 2021 13:23:24 --

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

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

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

[home-mik]

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

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

Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

Вы что-то неправильно прочитали. Дело не в том, что $f_{n}(n)+1$ не определена для любого $n$, а в том, что нет алгоритма, нумерующего все вычислимые функции, а потому функция, аргументом которой является номер вычислимой функции, не является вычислимой.

Алгоритм перебора то там как раз дается (это из книжки В. Босс "Лекции по математике" том 6):

Цитата:

Как уже отмечалось, процедура вычислений отождествляется с программой работы компьютера, представляющей собой запись алгоритма на некотором языке в некотором алфавите $А$,
$P = a_{1}a_{2}...a_{N}$, все $a_{j} \in A$ (1.2)
Программа применяется к различным входным словам. Если входные и выходные данные кодируются числами, программа
определяет вычислимую функцию.

Запись программы вычислений в виде (1.2) позволяет все вычислимые функции перенумеровать,
$f_{1}(n), ..., f_{k}(n), ...$ (1.3)
Сначала перечисляются все программы из одной буквы, потом из двух, потом из трех и так далее.

Ну а дальше само утверждение:

Цитата:

1.5.1. Теорема. Любая попытка ввести понятие вычислимой
функции $f(n)$ так, чтобы она была определена при любом $n$, — неразумна.

Доказательство диагональным рассуждением я приводил выше - повторять наверное не буду.

Дальше пояснение идет:

Цитата:

Если какие-то функции в перечислении (1.3) определены не при всех $n$, конструкция $g(n) = f_{n}(n) + 1$ к противоречию не приводит. (?)

Формулировка теоремы 1.5.1, конечно, слегка зашкаливает, но здесь важно заострить внимание. Определение вычислимой
функции $f(n)$ при любом $n$ — принципиально обречено на провал. Или получаются слишком узкие классы функций, дискредитирующие понятие вычислимости, или какие-то $f(n)$ перестают вычисляться. А попытка доопределить $f(n)$ «силовым методом» не проходит, иначе получается сказка про белого бычка — возврат к теореме 1.5.1, и — по тому же кругу.

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

[epros]

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

алгоритм перебора то есть всегда. Просто он бесконечным может быть.

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

-- Чт апр 08, 2021 13:54:14 --

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

Алгоритм перебора то там как раз дается (это из книжки В. Босс "Лекции по математике" том 6):

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

[home-mik]

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

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

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

Цитата:

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

Можно было бы изменить определение, сказав так: "если $f(n)$ не определено, то либо алгоритм $A$ не останавливается, либо останавливается, но ничего не печатает

-- 08.04.2021, 13:22 --

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

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

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

Примерно то же кстати и В. Босс пишет в качестве прелюдии к этой теореме 1.5.1:

Цитата:

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

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