2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Posted automatically
Сообщение15.12.2019, 16:49 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 17:48 
Аватара пользователя
Swarg в сообщении #1430332 писал(а):
Если натуральным числам функцией $f$ сопоставить такие алгоритмы...
Такое отображение существует, но оно не является вычислимой функцией (т.е. не существует алгоритма, который по номеру выдаст соответствующий алгоритм). Поэтому искомая функция также не является вычислимой.

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 18:45 
worm2 в сообщении #1430366 писал(а):
Поэтому искомая функция также не является вычислимой.

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

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 19:59 
Аватара пользователя
Swarg в сообщении #1430332 писал(а):
для любого аргумента значение можно вычислить с любой точностью
Нужно уточнять, что это значит.
Swarg в сообщении #1430332 писал(а):
Если натуральным числам функцией $f$ сопоставить такие алгоритмы
А точно множество таких алгоритмов вычислимо?

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 21:00 
mihaild в сообщении #1430396 писал(а):
Нужно уточнять, что это значит.

Для любого $n$ можно установить любой знак после запятой $f(n)$.
mihaild в сообщении #1430396 писал(а):
А точно множество таких алгоритмов вычислимо?

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

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 21:09 
Аватара пользователя
Swarg в сообщении #1430415 писал(а):
Для любого $n$ можно установить любой знак после запятой $f(n)$.
Равномерно (существует алгоритм, который по числам $n$ и $m$ выдает $m$-й знак после запятой числа $f(n)$) или неравномерно (для любого $n$ существует алгоритм)?

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

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение15.12.2019, 21:17 
mihaild
Равномерно. Спасибо, попытаюсь.

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение16.12.2019, 00:04 
Аватара пользователя
Swarg в сообщении #1430332 писал(а):
Рассматриваются функции $\mathbb{N} \to \mathbb{R}$ такие, что для любого аргумента значение можно вычислить с любой точностью.

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

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

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение16.12.2019, 00:40 
Аватара пользователя
И правда. Я подумал что стандартная конструкция "запускаем всё параллельно в бесконечном числе копий и где считаем долго время от времени пишем нули", но так гарантия будет только на то, что все начальные отрезки встретятся [а это можно было бы получить и проще].

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение16.12.2019, 03:17 
Someone в сообщении #1430452 писал(а):
Это не одно и то же. Более того, это второе определение вычислимого числа является плохим, так как число, разложение которого вычислимо (алгоритмом) в одной системе счисления, может оказаться невычислимым в этом смысле в другой системе счисления.
Стандартно действительное число называется вычислимым, если существует алгоритм, вычисляющий его с любой наперёд заданной точностью.

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

 
 
 
 Re: "Наибольшая" из некоторых функций N -> R
Сообщение16.12.2019, 18:55 
Аватара пользователя
Swarg в сообщении #1430472 писал(а):
что мешает вычислить его с точностью $k^{-n-1}$, а потом вычислить $n$-й знак получившегося числа?
Ну, предположим, есть у нас алгоритм,который вычисляет некоторое число с погрешностью, меньшей любой наперёд заданной величины. Задаём мы ему на входе последовательно $10^{-2}$, $10^{-4}$, $10^{-8}$, $10^{-16}$, … И получаем на выходе, соответственно, $0{,}099374$, $0{,}10000071945$, $0{,}09999999992967743$, $0{,}10000000000000000099947$, …
И какая же у этого числа первая цифра после запятой? $0$ или $1$?

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group