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

[epros]

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

Но как тогда объективно, т.е. независимо от нашего знания, установить, определена функция на данном аргументе или нет?

"Объективно", "независимо от знания" - это одно, а " установить" - это другое, это как раз "зависимо от знания". То, что "объективно", можно знать или не знать.

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

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

Мы повторяемся. Алгоритма общего нет, потому что неизвестно, как исключать машины Тьюринга, которые не останавливаются.

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

Я как-то "заходил" к конструктивным математикам, ужаснулся, и вышел - читал статьи Маркова. В общем понял я еще меньше, чем в классической, поэтому решил придерживаться последней. Хотя поначалу да, у меня как у программиста, прикладника надежды на конструктивизм были большие.

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

[home-mik]

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

home-mik в сообщении #1513902
писал(а):
даже алгоритм общий есть - перебирать все возможные машины Тьюринга и отбирать из них ту, которая дальше зайдет
Мы повторяемся. Алгоритма общего нет, потому что неизвестно, как исключать машины Тьюринга, которые не останавливаются.

Мне непонятно, как тогда для $N = 1,2,3,4$ ее подсчитали? На каком основании их там исключили? Просто так взяли и исключили, потому что не знали, что с ними делать?

-- 11.04.2021, 21:11 --

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

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

Я как-то думал, что на каждое умозаключение в любой логике есть правило вывода, т.е. выводится все.. Можете пример привести? (Прошу прощения, за оффтоп)

-- 11.04.2021, 21:25 --

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

home-mik в сообщении #1513902
писал(а):
Но как тогда объективно, т.е. независимо от нашего знания, установить, определена функция на данном аргументе или нет? В общем случае никак. Привет от классической логики и несчётных множеств.

А для счетных множеств? В теории вычислимости в основном функции натурального аргумента рассматривают.

[arseniiv]

И счётных множеств, не являющихся рекурсивно перечислимыми. Или, когда перечислимости мало, разрешимыми (то есть таких, что перечислимо и оно, и его дополнение до рассматриваемого «конструктивного универсума», который всегда перечислим и потому разрешим).

[epros]

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

Мне непонятно, как тогда для $N = 1,2,3,4$ ее подсчитали? На каком основании их там исключили?

Я же говорил, как-то доказали, что они не останавливаются. Но общего метода доказательства нет.

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

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

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

[Someone]

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

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

Но ведь если мы знаем, что последовательность фундаментальная, то знаем, что она сходится.

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

Б. А. Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973.

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

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

Про теоремы Гудстейна например я прочитал, что она эквивалентна непротиворечивости арифметики Пеано

В русскоязычной Википедии действительно так написано. В англоязычной Википедии я этого не нашёл. Более того, там и термин "consistency" отсутствует. При этом русскоязычная Википедия ссылается на статью Laurie Kirby и Jeff Paris, "Accessible Independence Results for Peano Arithmetic", Bulletin of the London Mathematical Society, (1982), 285-293.
Электронная копия этой статьи у меня есть. В ней термин "consistency" встречается ровно один раз в следующем контексте:

Цитата:

In proving the theorems we rely on work of Ketonen and Solovay [3] on ordinals below $\varepsilon_0$, which in turn develops earlier work by the present authors, Harrington, Wainer, and others. Gentzen [1] showed that using transfinite induction on ordinals below $\varepsilon_0$ one can prove the consistency of $P$, and the Ketonen-Solovay machinery we use here can be viewed as illuminating in more detail the relationship between $\varepsilon_0$ and $P$.

(Note: Goodstein proved the following: if $h\colon N\to N$ is a non-decreasing function, define an $h$-Goodstein sequence $b_0,b_2,\ldots$ by letting $b_{i+1}$ be the result of replacing every $h(i)$ in the base $h(i)$ representation of $b_i$ by $h(i+1)$, and subtracting $1$. Then the statement "for every non-decreasing $h$, every $h$-Goodstein sequence eventually reaches $0$" is equivalent to transfinite induction below $\varepsilon_0$.)

Здесь $P$ обозначает арифметику Пеано, $N$ — натуральный ряд (с нулём), $\varepsilon_0$ — наименьший ординал, удовлетворяющий условию $\omega^{\alpha}=\alpha$; вероятно, подразумевается, что функция $h$ должна удовлетворять условию $h(0)\geqslant 2$ ($\omega$ — наименьший бесконечный ординал, то есть, порядковый тип наименьшего индуктивного множества).

Здесь, как видим, нет ни малейшего намёка на эквивалентность теоремы Гудстейна и совместности (непротиворечивости) арифметики Пеано.

[manul91]

Someone в сообщении #1513928 писал(а):

Здесь, как видим, нет ни малейшего намёка на эквивалентность теоремы Гудстейна и совместности (непротиворечивости) арифметики Пеано.

Я ничего здесь по сути не понимаю... но чисто семантически и по форме, если увязать утверждения в последовательности вот так

Цитата:

...Then the statement "for every non-decreasing $h$, every $h$-Goodstein sequence eventually reaches $0$" is equivalent to transfinite induction below $\varepsilon_0$.)..

Цитата:

....Gentzen [1] showed that using transfinite induction on ordinals below $\varepsilon_0$ one can prove the consistency of $P$....

это похоже на намек... ("...Goodstein sequence eventually reaches $0$" is equivalent to [X; by using X] one can prove the consistency of $P$?)

[kotenok gav]

Someone в сообщении #1513928 писал(а):

В русскоязычной Википедии действительно так написано.

Исправил.

[Xaositect]

Это намек не на эквивалентность, а на то, что теорема Гудстейна сильнее, чем непротиворечивость арифметики (и это действительно так).

[epros]

Someone в сообщении #1513928 писал(а):

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

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

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

[home-mik]

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

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

Мне непонятно, как тогда для $N = 1,2,3,4$ ее подсчитали? На каком основании их там исключили?

Я же говорил, как-то доказали, что они не останавливаются. Но общего метода доказательства нет.

Хорошо, допустим, как исключили в этих четырех случаях, ясно. Но с другой стороны, а зачем вообще эти может быть неостанавливающиеся машины исключать из рассмотрения? Пусть алгоритм перебирает все без исключения машины Тьюринга и работает неопределенно долго. Как я вижу, это вычислимости не противоречит. Например, функция
$f(n) = \begin{cases} 1,&\text{если $x^n + y^n = z^n$ разрешимо в целых числах;}\\ 0,&\text{в противном случае.} \end{cases}$
насколько я знаю, считается вычислимой, даже если не брать в расчет доказательство теоремы Ферма. Хотя тогда установить справедливость $x^n + y^n = z^n$ можно только перебором по всем $x, y, z$ для каждого $n$, а этот перебор тоже может продолжаться бесконечно долго, как и перебор машин Тьюринга для вычисления $BB(n)$. В чем же разница? Почему вторая считается вычислимой, а первая - нет?

[epros]

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

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

Это противоречит определению функции $\Sigma(n)$. Потому что функция $\Sigma(n)$ всюду определена, а предлагаемая Вами функция, которая по очереди запускает все машины Тьюринга и на первой зацикливающейся - зацикливается вместе с ней, нигде не определена.

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

Например, функция
$f(n) = \begin{cases} 1,&\text{если $x^n + y^n = z^n$ разрешимо в целых числах;}\\ 0,&\text{в противном случае.} \end{cases}$
насколько я знаю, считается вычислимой, даже если не брать в расчет доказательство теоремы Ферма.

Мы можем доказать, что эта функция вычислима, только опираясь на знание о том, что вопрос о разрешимости данного уравнения алгоритмически разрешим при каждом заданном $n$.

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

Хотя тогда установить справедливость $x^n + y^n = z^n$ можно только перебором по всем $x, y, z$ для каждого $n$, а этот перебор тоже может продолжаться бесконечно долго, как и перебор машин Тьюринга для вычисления $BB(n)$.

Если Вы определите функцию как перебирающую все $x, y, z$ для каждого $n$, то это будет другая функция.

[mihaild]

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

Хотя тогда установить справедливость $x^n + y^n = z^n$ можно только перебором по всем $x, y, z$ для каждого $n$

Нет.
Вообще, вычислимость функции - это свойство только функции, и больше ничего, поэтому нельзя сказать "функция считается вычислимой, даже если не брать что-то в рассмотрение" - в определении вычислимости нет параметра "что брать в рассмотрение".
Другое дело, что мы можем не знать, является ли конкретная функция вычислимой. Приведенная вами функция вычислима, и это можно вывести из ВТФ. Если бы у нас скажем был результат "если уравнение разрешимо при данном $n$, то у него есть решение не больше $2^{n!}$", то из него тоже можно было бы вывести вычислимость этой функции.

[manul91]

Xaositect в сообщении #1513941 писал(а):

Это намек не на эквивалентность, а на то, что теорема Гудстейна сильнее, чем непротиворечивость арифметики (и это действительно так).

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

[epros]

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

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

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

[Sender]

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