Вычислимые и невычислимые числа

[Skipper]

Вычислимые числа в одной системе счисления и невычислимые в другой.

Из другой темы (не могу скопировать т.к. кнопки "вставка" нет)

Someone :

Цитата:

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

Это очень интересно.. Я думал что если число невычислимое, то оно всегда невычислимое
вне зависимости от системы счисления .

Но если так, покажите пожалуйста , пример вычислимого числа, допустим в СС = 2, и невычислимого в другой СС ?

Спасибо.

-- Вт янв 08, 2019 22:36:39 --

Дополню : я понимал под вычислимостью-невычислимостью

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

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

[Someone]

Skipper в сообщении #1367017 писал(а):

Из другой темы (не могу скопировать т.к. кнопки "вставка" нет)

Ну да, Вы же в Пургатории писать не можете. Имеется в виду сообщение https://dxdy.ru/post1367007.html#p1367007.

В конструктивной математике много направлений, я подробно знакомился с советской школой конструктивизма по учебнику

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

В этой книге конструктивное действительное число (КДЧ) определяется как слово, которое является либо записью рационального числа, либо записью упорядоченной пары алгоритмов, из которых первый является последовательностью рациональных чисел (это означает, что, получив на входе натуральное число $i$, он на выходе даёт запись рационального числа $\alpha(i)$), а второй называется регулятором фундаментальности и по заданному натуральному числу $n$ выдаёт такое натуральное число $\beta(n)$, что для любых натуральных $m\geqslant\beta(n)$ и $l\geqslant\beta(n)$ выполняется неравенство $\lvert\alpha(m)-\alpha(l)\rvert<2^{-n}$. (Определяются также ослабленные варианты конструктивных действительных чисел, но приведённый здесь рассматривается как основной.)
В общем, это определение означает, что КДЧ — это такое действительное число, для которого существует алгоритм, вычисляющий его с любой наперёд заданной точностью. И это определение не зависит ни от какой системы счисления.

Если у нас есть алгоритм, вычисляющий последовательность цифр числа в какой-нибудь системе счисления, то, разумеется, это число является КДЧ. Но обратное, вообще говоря, неверно.
Например, пусть у нас есть некоторое КДЧ, и мы хотим вычислить его первую десятичную цифру после нуля.
Вычисляем с погрешностью $2^{-4}$, получаем $\frac{19}{20}=0{,}95$.
Вычисляем с погрешностью $2^{-7}$, получаем $\frac{199}{200}=0{,}995$.
Вычисляем с погрешностью $2^{-10}$, получаем $\frac{1999}{2000}=0{,}9995$.
Вычисляем с погрешностью $2^{-14}$, получаем $\frac{19999}{20000}=0{,}99995$.
И так далее. В общем, с какой бы точностью мы ни вычисляли, мы не можем определить, равна ли первая цифра после запятой $9$ или $0$, потому что интервал, в котором содержится точное значение числа (предел фундаментальной последовательности рациональных чисел) всякий раз содержит $1$, причём, определение того, будет ли так продолжаться до бесконечности, или же на каком-то этапе цифра всё-таки определится, может быть связано с какой-нибудь алгоритмически неразрешимой проблемой, так что никаким алгоритмом эту злополучную цифру определить будет нельзя.

Таким неприятным свойством в $d$-ичной системе счисления обладают КДЧ, равные какому-нибудь $d$-ично рациональному числу. Если КДЧ равно $d$-ично рациональному числу, которое не является $m$-ично рациональным, то последовательность его цифр вычислима в $m$-ичной системе счисления и может быть невычислимой в $d$-ичной.

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

Что касается обсуждаемого направления конструктивизма, то тут ситуация такая. Всякая последовательность должна определятся некоторым алгоритмом, то есть, быть конструктивной. В частности, последовательность КДЧ — это алгоритм, который по заданному натуральному числу $i$ выдаёт запись некоторого КДЧ. "Счётность" множества всех КДЧ здесь означала бы существование последовательности КДЧ, содержащей все КДЧ, то есть, множество всех КДЧ было бы перечислимым.
Однако в упомянутой книге доказывается теорема о том, что множество всех КДЧ является эффективно несчётным.
Смысл этой теоремы состоит в том, что существует алгоритм, который, получив на входе записи произвольного интервала и произвольной конструктивной последовательности КДЧ, выдаёт запись КДЧ, лежащего в заданном интервале и не совпадающего ни с одним членом заданной последовательности КДЧ.

P.S. Заметим, что в советской школе конструктивизма говорили не "алгоритм", а "алгорифм".

[Aritaborian]

(Оффтоп)

Skipper в сообщении #1367017 писал(а):

Из другой темы (не могу скопировать т.к. кнопки "вставка" нет)

Если немного попотеть, можно и из такой темы вставить цитату с полным оформлением. Просто нужно всё это делать ручками ;-)

[Skipper]

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

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

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

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

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

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

Здесь всё очевидно и понятно.

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

Что касается обсуждаемого направления конструктивизма, то тут ситуация такая. (... )

А вот с этим, пока не разобрался..

[mihaild]

Skipper в сообщении #1367111 писал(а):

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

Проблема в привязке к цифрам в том, что по алгоритмам, вычисляющим цифры $a$ и $b$, нельзя эффективно (алгоритмически) построить алгоритм, вычисляющий цифры $a + b$.

[Skipper]

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

Skipper в сообщении #1367111 писал(а):

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

Проблема в привязке к цифрам в том, что по алгоритмам, вычисляющим цифры $a$ и $b$, нельзя эффективно (алгоритмически) построить алгоритм, вычисляющий цифры $a + b$.

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

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

Формальным языком, это можно сказать так -
Обозначим исследуемое число буквой $A$ , пусть посредством алгоритма мы можем получить "числа-приближения" к нему : $B_1$ , $B_2$ , $B_3$ ... $B_n$ ,
со сколь угодно большой точностью.
Т.е. для любого сколь угодно малого $\varepsilon > 0$ , существует $m$ , такое что для всех $n > m$ , расстояние между числами, т.е. $|A - B_n |$ $< \varepsilon $ .

Мне кажется интуитивным, что мощность множества всех подобных чисел $A$ , будет счётным.

Я здесь прав?
Если это так, то вся математика, по сути и имеет дело только, со счётным множеством чисел.
Хотя и называются они "иррациональными", "трансцендентными" и т.д.

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

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

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

А вот упрощение в математике - может и наступить, если считать что всё изучаемое множество вещественных чисел - счетно.

Я пока до конца не разобрался со всеми аргументами против, (к примеру "Что касается обсуждаемого направления конструктивизма, то тут ситуация такая. (... ) ") .

но первое видение этой темы, кажется вот таким .

[mihaild]

Skipper в сообщении #1367174 писал(а):

Я здесь прав?

Нужно уточнить - вы хотите, чтобы была просто вычислима сходящаяся к данному числу последовательность, или чтобы можно было по $n$ найти приближение с точностью $\frac{1}{n}$. Оба определения имеют право на жизнь, но есть числа, которые вычислимы по первому определению, но не по второму.
Естественно что т.к. каждое вычислимое число (по обоим определениям) задается алгоритмом, то вычислимых чисел счетно.

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

И считаете ли вы, что "существует" вещественное число, такое, что $n$-й бит его равен $1$ тогда и только тогда, когда $n$-я формула арифметики верна в стандартной модели?

[Skipper]

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

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

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

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

Т.к. множество всех машин Тьюринга (как и целых чисел в двоичном представлении) - счётно,
то отсюда следует что и множество таких всех вещественных чисел - счётно.

А то, что в математике пишут, что "существуют" некие другие вещественные числа, благодаря которым, утверждается что
множество всех вещественных чисел имеет бОльшую счетного, мощность континнума - возникает вопрос "где они существуют" ??
Если нет никакого алгоритма, и никакой машины Тьюринга, позволяющих вообще как то строить эти числа (бесконечно близко аппроксимировать),
или как то изучать .

Какая выгода математике, как науке в целом, если мы не будем думать, что существует только описуемое формально ? (остальное - не существует.
не плодим сущности без необходимости по принципу Оккама).

[mihaild]

Не все машины Тьюринга задают какое-то КДЧ.

Skipper в сообщении #1367187 писал(а):

Т.к. множество всех машин Тьюринга (как и целых чисел в двоичном представлении) - счётно,

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

[Skipper]

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

Не все машины Тьюринга задают какое-то КДЧ

Недопонял..
Если это так, то здесь и находится главный камень преткновения.

Утверждается же, что с помощью машины Тьюринга, можно построить любой алгоритм?
КДЧ - конструктивное действительное число? Значит если оно конструктивное, то и алгоритм для его построения должен быть?

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

существует биекция между этим множеством и множеством натуральных чисел

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

-- Ср янв 09, 2019 17:05:44 --

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

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

Это пока не обдумал, не такой уж простой вопрос.

[Someone]

Skipper в сообщении #1367111 писал(а):

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

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

Skipper в сообщении #1367187 писал(а):

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

"Существуют" они там же, где и конструктивные, то есть, в человеческой психике. И не забывайте, что с точки зрения конструктивной математики множество КДЧ "несчётно": их нельзя конструктивно занумеровать натуральными числами.

[Skipper]

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

вы хотите, чтобы была просто вычислима сходящаяся к данному числу последовательность, или чтобы можно было по $n$ найти приближение с точностью $\frac{1}{n}$. Оба определения имеют право на жизнь, но есть числа, которые вычислимы по первому определению, но не по второму.

Кажется, что в обоих этих случаях , можно назвать данное число вычислимым.

-- Ср янв 09, 2019 17:12:53 --

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

не забывайте, что с точки зрения конструктивной математики множество КДЧ "несчётно": их нельзя конструктивно занумеровать натуральными числами.

Значит существует конструктивное число, для бесконечно близкой аппроксимации которого, не найдётся соответствующей машины Тьюринга?

-- Ср янв 09, 2019 17:26:07 --

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

Естественно что т.к. каждое вычислимое число (по обоим определениям) задается алгоритмом, то вычислимых чисел счетно.

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

Почему нет ? Приведите пример, пожалуйста.

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

Вот,

Skipper в сообщении #1367174 писал(а):

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

Формальным языком, это можно сказать так -
Обозначим исследуемое число буквой $A$ , пусть посредством алгоритма мы можем получить "числа-приближения" к нему : $B_1$ , $B_2$ , $B_3$ ... $B_n$ ,
со сколь угодно большой точностью.
Т.е. для любого сколь угодно малого $\varepsilon > 0$ , существует $m$ , такое что для всех $n > m$ , расстояние между числами, т.е. $|A - B_n |$ $< \varepsilon $ .

Ваша "последовательность вычислимых чисел" - сходится к какой то точке, т.е. начиная с какого то номера, все элементы последовательности ближе
фиксированного $$\varepsilon$ $ ?

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

В определении вычислимых (конструктивных) чисел ничего не говорится о цифрах.

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

-- Ср янв 09, 2019 17:41:03 --

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

считаете ли вы, что "существует" вещественное число, такое, что $n$-й бит его равен $1$ тогда и только тогда, когда $n$-я формула арифметики верна в стандартной модели?

Могу ошибаться, но первое что приходит на ум - да, такое число существует, и более того - это вычислимое вещественное число
(каких должно быть счётное множество) .
Потому что должна существовать машина Тьюринга, которая бесконечно близко аппроксимирует данное число, т.е. последовательно вычисляя каждый
$n$-й бит - тем самым, "приближается" к результату.

Занумеруем все формулы арифметики в стандартной модели - некой цепочкой правил, по которым формула будет связана с целым числом.
Нужно проверить $n$-й бит . Алгоритм (машина Тьюринга) - проверяет истинность этой $n$-й формула арифметики (правила подобной проверки видимо
тоже можно описать алгоритмически ) . Получаем "истина" или "ложь", третьего не дано.
И записываем в $n$-й бит $ = 0$ или $1$.
Переходим к следующему биту и т.д.

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

[Someone]

Skipper в сообщении #1367174 писал(а):

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

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

Skipper в сообщении #1367174 писал(а):

Если это так, то вся математика, по сути и имеет дело только, со счётным множеством чисел.

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

Skipper в сообщении #1367174 писал(а):

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

А вот упрощение в математике - может и наступить, если считать что всё изучаемое множество вещественных чисел - счетно.

И изучить может, и потеряет очень много. И жить станет много труднее.

Skipper в сообщении #1367199 писал(а):

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

Как говорил кот Матроскин, "это — национальная индейская изба".

Skipper в сообщении #1367199 писал(а):

Кажется, что в обоих этих случаях , можно назвать данное число вычислимым.

Да, они оба "вычислимы", но в разных смыслах. В сильно разных.

Skipper в сообщении #1367199 писал(а):

Значит существует конструктивное число, для бесконечно близкой аппроксимации которого, не найдётся соответствующей машины Тьюринга?

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

Skipper в сообщении #1367199 писал(а):

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

По-моему, я уже давно определение сформулировал. Вам обязательно придумывать от себя?

Skipper в сообщении #1367199 писал(а):

быстро понять основы "конструктивной математики"

Извините, но Вам до понимания "основ" ещё очень и очень далеко. Для начала попробуйте понять, что математика, в том числе и конструктивная, много шире возни с числами.

А что касается конструктивизма, то ведь литературу я указал… Только не забывайте, что этих "конструктивизмов" — воз и маленькая тележка. И у всех "конструктивизм" разный.

[Skipper]

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

Я не понимаю, что такое "число, сколь угодно близкое к исследуемому числу".

имел в виду, последовательность вычисляемых (и даже рациональных ) чисел, приближающаяся в пределе к иррациональному вещественному исследуемому числу $A$ , про которое мы даём ответ - вычислимо оно или нет.

Skipper в сообщении #1367174 писал(а):

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

Формальным языком, это можно сказать так -
Обозначим исследуемое число буквой $A$ , пусть посредством алгоритма мы можем получить "числа-приближения" к нему : $B_1$ , $B_2$ , $B_3$ ... $B_n$ ,
со сколь угодно большой точностью.
Т.е. для любого сколь угодно малого $\varepsilon > 0$ , существует $m$ , такое что для всех $n > m$ , расстояние между числами, т.е. $|A - B_n |$ $< \varepsilon $ .

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

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

У всех "конструктивизм" разный, вот и интересно, с таким подходом, как у меня, будет ли множество таких "вычислимых" чисел - счётным?
(если нет, то здесь краеугольный камень преткновения - число и последовательность к нему вычислима, а машину Тьюринга, вычисляющую это
построить нельзя ).

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

-- Ср янв 09, 2019 18:29:13 --

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

или чтобы можно было по $n$ найти приближение с точностью $\frac{1}{n}$.

В определении вычислимости , которое выше я дал, такие числа тоже будут вычислимыми, т.к. в последовательности, начиная с какого то номера, мы получим приближение с точностью $\frac{1}{n}$ , и дальше точность будет возрастать.

[mihaild]

Skipper в сообщении #1367193 писал(а):

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

Не все машины Тьюринга задают какое-то КДЧ

Утверждается же, что с помощью машины Тьюринга, можно построить любой алгоритм?
КДЧ - конструктивное действительное число? Значит если оно конструктивное, то и алгоритм для его построения должен быть?

Любое КДЧ задается какой-то МТ. Но существуют МТ, которые не задают никакого КДЧ (например, никогда не останавливающаяся). И не существует МТ $X$, которая по числу $n$ выдает какую-то МТ $X(n)$, задающую КДЧ, такой, что для любого КДЧ $a$ для какого-то $n$ выполнено "МТ $X(n)$ задает $a$".

Skipper в сообщении #1367193 писал(а):

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

Что значит "связан биекцией"?
Еще раз: счетное множество - это такое, для которого существует биекция между ним и $\mathbb{N}$. Вопрос - "где она существует"? (в том же смысле, в котором вы спрашиваете, "где существуют" невычислимые вещественные числа)
(дело в том, что вычислимой такой биекции не существует: нельзя вычислимо занумеровать все КДЧ)

Skipper в сообщении #1367199 писал(а):

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

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

Почему нет ? Приведите пример, пожалуйста.

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

Не путайте сходимость с существованием предельной точки! Есть известная теорема: если $x_n$ - последовательность вещественных чисел из отрезка $[0; 1]$, то $\exists y \in [0; 1] \forall \varepsilon >0 \forall N \exists n > N: |x_n - y| < \varepsilon$. Но даже если все $x_n$ конструктивны и их последовательность коструктивна (т.е. у нас есть алгоритм $A(m, n)$, который при фиксированном $n$ выдает рациональные приближения $x_n$: $\lim\limits_{m\to\infty} A(m, n) = x_n$), то конструктивного $y$ с нужным свойством может и не найтись.
Пример попробуйте найти сами (подсказка - подумайте, как изменить константу Хайтина; я придумал пример сам, так что это несложно).

Skipper в сообщении #1367199 писал(а):

Алгоритм (машина Тьюринга) - проверяет истинность этой $n$-й формула арифметики (правила подобной проверки видимо тоже можно описать алгоритмически

Нет, нельзя. "Очень сильно" нельзя (проверить, останавливается ли МТ, тоже нельзя, но это всё равно гораздо более простая задача, чем проверить, верна ли формула в стандартной модели).

-- 09.01.2019, 19:43 --

Skipper в сообщении #1367224 писал(а):

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

Можете. Собственно это первое из указанных мной определений

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

чтобы была просто вычислима сходящаяся к данному числу последовательность

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