"Наибольшая" из некоторых функций N -> R

[Swarg]

Рассматриваются функции $\mathbb{N} \to \mathbb{R}$ такие, что для любого аргумента значение можно вычислить с любой точностью.
Есть ли среди них такая(такие), у которой область значений включает(в качестве подмножеств) области значений всех остальных таких функций? Известна ли она?
UPD: похоже, это так, т. к. предполагается, что $n$-й символ двоичного представления каждого числа из области определения можно вычислить с помощью нек-го алгоритма(с вводом n), записанного конечным алфавитом и конечным числом символов. Если натуральным числам функцией $f$ сопоставить такие алгоритмы, а каждому алгоритму функцией $g$ — соответствующее вещественное число, а затем взять композицию этих двух функций, то получим искомую функцию. Я прав?

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

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

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[worm2]

Swarg в сообщении #1430332 писал(а):

Если натуральным числам функцией $f$ сопоставить такие алгоритмы...

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

[Swarg]

worm2 в сообщении #1430366 писал(а):

Поэтому искомая функция также не является вычислимой.

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

[mihaild]

Swarg в сообщении #1430332 писал(а):

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

Нужно уточнять, что это значит.

Swarg в сообщении #1430332 писал(а):

Если натуральным числам функцией $f$ сопоставить такие алгоритмы

А точно множество таких алгоритмов вычислимо?

[Swarg]

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

Нужно уточнять, что это значит.

Для любого $n$ можно установить любой знак после запятой $f(n)$.

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

А точно множество таких алгоритмов вычислимо?

Не точно, и, если верить worm2, неверно. Да, это ошибка в доказательстве.

[mihaild]

Swarg в сообщении #1430415 писал(а):

Для любого $n$ можно установить любой знак после запятой $f(n)$.

Равномерно (существует алгоритм, который по числам $n$ и $m$ выдает $m$-й знак после запятой числа $f(n)$) или неравномерно (для любого $n$ существует алгоритм)?

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

[Swarg]

mihaild
Равномерно. Спасибо, попытаюсь.

[Someone]

Swarg в сообщении #1430332 писал(а):

Рассматриваются функции $\mathbb{N} \to \mathbb{R}$ такие, что для любого аргумента значение можно вычислить с любой точностью.

Swarg в сообщении #1430332 писал(а):

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

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

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

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

Такая функция фактически позволяет перечислить все вычислимые числа, поэтому она невозможна. Дело в том, что множество вычислимых действительных чисел эффективно несчётно в том смысле, что существует алгоритм, который по заданной вычислимой последовательности вычислимых чисел и по заданному интервалу $(a,b)$ (с вычислимыми концами $a<b$) строит вычислимое число, которое содержится в заданном интервале и не равно никакому члену последовательности. Доказательство можно посмотреть в книге Б. А. Кушнера "Лекции по конструктивному математическому анализу" (глава 3, § 4). В книге обсуждение идёт в рамках конструктивной математики, но приведённое там доказательство легко переписать в стиле классической математики.

[mihaild]

И правда. Я подумал что стандартная конструкция "запускаем всё параллельно в бесконечном числе копий и где считаем долго время от времени пишем нули", но так гарантия будет только на то, что все начальные отрезки встретятся [а это можно было бы получить и проще].

[Swarg]

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

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

Значит находящий рациональное, удалённое не более, чем на $\varepsilon$? Если так, что мешает вычислить его с точностью $k^{-n-1}$, а потом вычислить $n$-й знак получившегося числа?

[Someone]

Swarg в сообщении #1430472 писал(а):

что мешает вычислить его с точностью $k^{-n-1}$, а потом вычислить $n$-й знак получившегося числа?

Ну, предположим, есть у нас алгоритм,который вычисляет некоторое число с погрешностью, меньшей любой наперёд заданной величины. Задаём мы ему на входе последовательно $10^{-2}$, $10^{-4}$, $10^{-8}$, $10^{-16}$, … И получаем на выходе, соответственно, $0{,}099374$, $0{,}10000071945$, $0{,}09999999992967743$, $0{,}10000000000000000099947$, …
И какая же у этого числа первая цифра после запятой? $0$ или $1$?