Можно ли вычислить значения функции?

[Dialectic]

Определим функцию F:N-->{0,1} так:
F(n)=1, если в десятичном разложении числа e, имеется n подряд идущих нулей. И F(n)=0 в противном случае.Возникает вопрос: можем ли мы для каждого значения n найти значение функции F(n)?

-- Вт июл 21, 2009 00:20:40 --

И второй вопрос: можно ли и главное как доказать существование такого вещественного числа r, что функция
F(n) заданная по этому числу, как это делается в примере для числа e - заведомо не может быть вычисленна для любого n?
Ну и третий тогда вопрос : приведите такое число! (с доказательством или хотя бы намёком как это можно сделать, для указанного числа). Спасибо.

[volovzi]

Число e — бесконечная непериодическая десятичная дробь, значит, в нём содержатся все конечные последовательности цифр, в том числе и конечные наборы нулей.
По второму вопросу — любое рациональное число.

[Хорхе]

volovzi в сообщении #230289 писал(а):

Число e — бесконечная непериодическая десятичная дробь, значит, в нём содержатся все конечные последовательности цифр

Это вранье.
0,121122111222111122221111122222111111222222...

Цитата:

Возникает вопрос: можем ли мы для каждого значения n найти значение функции F(n)?

Что в этой фразе значит слово "можем"? Это не такой наивный вопрос, как кажется.

-- Вт июл 21, 2009 02:56:15 --

Цитата:

И второй вопрос: можно ли и главное как доказать существование такого вещественного числа r, что функция
F(n) заданная по этому числу, как это делается в примере для числа e - заведомо не может быть вычисленна для любого n?

Вот тут тоже скользкая фраза "заведомо не может быть вычислена". Что это значит? Что не существует конечного алгоритма для вычисления? Тогда существование этого числа доказывается очень легко: конечных алгоритмов счетное число, а возможных последовательностей $F(n)$ --- континуум.

Ну и тогда понятен ответ на третий вопрос --- никто Вам такого числа не предъявит, потому что для его описания понадобится не просто многобукаф, а бесконечное количество букв.

[Профессор Снэйп]

Хорхе в сообщении #230296 писал(а):

Ну и тогда понятен ответ на третий вопрос --- никто Вам такого числа не предъявит, потому что для его описания понадобится не просто многобукаф, а бесконечное количество букв.

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

Всех возможных алгоритмов --- счётное число, и их можно перенумеровать. Пусть $\alpha_i(j)$ --- десятичный разряд, который алгоритм с номером $i$ выдаёт как разряд, стоящий на $j$-ом месте у вычисляемого им числа. Предположим, что $f$ --- перестановка множества $\{ 0, \ldots, 9 \}$, не имеющая неподвижных точек. Тогда число

$$ 0.f(\alpha_1(1))f(\alpha_2(2))f(\alpha_3(3))f(\alpha_4(4))... $$

не вычисляется никаким алгоритмом Хотя с точки зрения ZFC оно задано безупречно

Насчёт первого вопроса о числе $e$ --- ответ не знаю. Это вопрос в основном не к специалистам по теории алгоритмов, а к специалистам по теории чисел.

P. S. Прошу прощения. Я, кажется, ответил не на вопрос автора темы, а на какой-то свой собственный, который сам же себе и задал Но не беда. На вопрос автора я ответил в своём следующем сообщении

[Milliard]

Если число е - нормальное, то F(n)=1 для любого n. Нормальность чисел е и пи пока не доказана, хотя и с большой точностью подтверждается тем, что цифры в десятичном разложении этих чисел встречаются примерно с равной вероятностью до миллиардов знаков после запятой. То есть пока что есть примеры для F(n)=1 при n<11-12... или до скольки знаков там известно число е?

[Профессор Снэйп]

Dialectic в сообщении #230287 писал(а):

И второй вопрос: можно ли и главное как доказать существование такого вещественного числа r, что функция
F(n) заданная по этому числу, как это делается в примере для числа e - заведомо не может быть вычисленна для любого n?

Смотря как Вы понимаете эту самую функцию $F$. Вы описали её довольно неточно.

Допустим, в разложении некоторого числа встретилось $n+1$ нулей подряд. В последовательности из $n+1$ нулей можно выделить подпоследовательность из $n$ нулей. Считать ли в этом случае $F(n)=1$?

Если да, то тогда $F$ вычислима для любого действительного числа. Но я подозреваю, что автор имел в виду следующее: $F(n)=1$ тогда и только тогда, когда в разложении числа встречается последовательность, содержащая ровно $n$ идущих подряд нулей. Эта последовательность должна быть окружена разрядами, отличными от нуля. То есть не являться подпоследовательностью последовательности, состоящей из большего чем $n$ количества идущих подряд нулей.

В этом случае число, для которого $F$ не вычислима, строится довольно легко. Пусть $\varphi_1(x), \varphi_2(x), \ldots$ --- все вычислимые функции из $\mathbb{N}$ в $\mathbb{N}$ от одной переменной (их счётное число, так что множество таких функций можно занумеровать). Теперь задаём число так. Пусть $\beta_i$ равно нулю, если $\varphi_i(i) = 1$ и $\beta_i = i$ в противном случае. Для числа

$$ 0.1\underbrace{0\ldots0}_{\beta_1 \text{ нулей}}1\underbrace{0\ldots0}}_{\beta_2 \text{ нулей}}1\underbrace{0\ldots0}}_{\beta_3 \text{ нулей}}1\ldots $$

функция $F$ не вычислима.

[Dialectic]

Профессор Снэйп в сообщении #230319 писал(а):

В этом случае число, для которого $F$ не вычислима, строится довольно легко. Пусть $\varphi_1(x), \varphi_2(x), \ldots$ --- все вычислимые функции из $\mathbb{N}$ в $\mathbb{N}$ от одной переменной (их счётное число, так что множество таких функций можно занумеровать). Теперь задаём число так. Пусть $\beta_i$ равно нулю, если $\varphi_i(i) = 1$ и $\beta_i = i$ в противном случае. Для числа

$$ 0.1\underbrace{0\ldots0}_{\beta_1 \text{ нулей}}1\underbrace{0\ldots0}}_{\beta_2 \text{ нулей}}1\underbrace{0\ldots0}}_{\beta_3 \text{ нулей}}1\ldots $$

функция $F$ не вычислима.

Пример сильный. Таким образом Вы доказали, что такие числа существуют и привели пример как построить такое число. Можно сказать, что на вопрос 2 и 3 ответ получен. А как же быть с первым вопросом? Может ответ на него можно получить если изучить свойства алгоритма генерирующего число е? Кстати, такой алгоритм вообще существует? И существует ли алгоритм, который генерирует число e - последовательно? Т.е. $A(n)=b_n$,где $e=b_0,b_1b2,...,b_n...$?

-- Вт июл 21, 2009 17:00:50 --

Хорхе в сообщении #230296 писал(а):

Цитата:

Возникает вопрос: можем ли мы для каждого значения n найти значение функции F(n)?

Что в этой фразе значит слово "можем"? Это не такой наивный вопрос, как кажется.

"Можем" это означает следующее - я называю вам число n , а Вы говорите мне на это -" при данном числе n, значение функции равно F(n)=1 (например). И этому имеется следующее доказательство. Вот оно..."

Хорхе в сообщении #230296 писал(а):

Ну и тогда понятен ответ на третий вопрос --- никто Вам такого числа не предъявит, потому что для его описания понадобится не просто многобукаф, а бесконечное количество букв.

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

[Хорхе]

Dialectic в сообщении #230400 писал(а):

Пример сильный. Таким образом Вы доказали, что такие числа существуют и привели пример как построить такое число. Можно сказать, что на вопрос 2 и 3 ответ получен. .

Вот как раз с ответом на третий вопрос загвоздка.

С одной стороны, Вам предъявили континуум таких чисел, потому что занумеровать вычислимые функции можно континуумом способов.

С другой стороны, Вам не предъявили ни одного числа, ведь нельзя сказать, будет ли, скажем, $\pi$ или $\pi^e$ среди них присутствовать. В этом смысле Вам ответа не дали. И никогда не дадут. И как раз потому, что для того, чтобы предъявить нумерацию вычислимых функций, понадобится $\infty$многабукаф.

Цитата:

А как же быть с первым вопросом? Может ответ на него можно получить если изучить свойства алгоритма генерирующего число е? Кстати, такой алгоритм вообще существует? И существует ли алгоритм, который генерирует число e - последовательно? Т.е. $A(n)=b_n$,где $e=b_0,b_1b2,...,b_n...$?

Такой алгоритм существует, конечно. Например, можно взять формулу $e = 1+ 1+ 1/2! + 1/3!+...$ и по ней легко написать алгоритм, используя оценку для остатка ряда. Но дело в том, что такой алгоритм ничего не может сказать о том, присутствуют ли в числе $e$, например, 100 нулей подряд, потому что для ответа (если мы имеем только цифры числа), особенно для отрицательного ответа, надо прочесывать все его многацифар.

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

[Dialectic]

Хорхе в сообщении #230419 писал(а):

Dialectic в сообщении #230400 писал(а):

Пример сильный. Таким образом Вы доказали, что такие числа существуют и привели пример как построить такое число. Можно сказать, что на вопрос 2 и 3 ответ получен. .

Вот как раз с ответом на третий вопрос загвоздка.
С одной стороны, Вам предъявили континуум таких чисел, потому что занумеровать вычислимые функции можно континуумом способов.
С другой стороны, Вам не предъявили ни одного числа, ведь нельзя сказать, будет ли, скажем, $\pi$ или $\pi^e$ среди них присутствовать. В этом смысле Вам ответа не дали. И никогда не дадут. И как раз потому, что для того, чтобы предъявить нумерацию вычислимых функций, понадобится $\infty$многабукаф.

Извините, но я настаиваю, что мне предьявили число.
Когда речь идёт о представлении вещественных чисел бесконечными десятичными дробями, то насколько я понимаю,как и в случаях с бесконечными множествами, да и вообще - как в абсолютно всех случаях, когда произносится слово "бесконечность чего-либо" - речь идёт не о том, чтобы перечислить все разряды этого числа( что заведомо невозможно). А о том, чтобы указать некоторые свойства этого числа, однозначно идентифицирующие его. Я считаю, что такие свойства были предьявлены и было показанно, каким образом построить некоторое конкретное число r. Для этого, необходимо лишь выбрать определённую нумерацию вычислимых функций.Когда такая нумерация будет выполнена, будет предьявленно конкретное число.Поэтому те свойства которые идентифицируют конкретное число r с учётом конретной нумерации вычислимых функций полностью задают это число. Единственно, что Вы могли бы возразить, что множество вычислимых функций хоть и счётно, но неперечислимо. Поэтому, имеются принципиальное ограничение на возможность построения такого числа, так как практическим путём невозможно гарантировать, что мы сможем перечислить все вычислимые функции, чтобы выполнить для них указанное построение числа. Но вроде это не так.
А что касается вопроса о пренадлежности числа $\pi$ или $e$ этому классу, то есть вопроса о разрешимости данного класса относительно всех вещественных чисел, то да, этот вопрос пока в полной мере не раскрыт.Ясно лишь то, что существует не менее континуума вещественных чисел, которые в этом классе не лежат. В частности как для числа $\pi$ так и числа $e$
вопрос остаётся открытым. Но это первый вопрос темы.

Хорхе в сообщении #230419 писал(а):

Такой алгоритм существует, конечно. Например, можно взять формулу $e = 1+ 1+ 1/2! + 1/3!+...$ и по ней легко написать алгоритм, используя оценку для остатка ряда. Но дело в том, что такой алгоритм ничего не может сказать о том, присутствуют ли в числе $e$, например, 100 нулей подряд, потому что для ответа (если мы имеем только цифры числа), особенно для отрицательного ответа, надо прочесывать все его многацифар.

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

[Профессор Снэйп]

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

-- Ср июл 22, 2009 13:29:41 --

Хорхе в сообщении #230419 писал(а):

Вот как раз с ответом на третий вопрос загвоздка.

Как видите, на третий вопрос возможен ответ, не содержащий в себе никакой загвоздки

[Dialectic]

Профессор Снэйп в сообщении #230518 писал(а):

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

Мне очень интересно. Приведите пожалуйста такой пример.

[Профессор Снэйп]

Dialectic в сообщении #230533 писал(а):

Мне очень интересно. Приведите пожалуйста такой пример.

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

Множество вычислимых функций, как было справедливо замечено выше, действительно алгоритмически не перечислимо. Зато алгоритмически перечислимо множество программ, вычисляющих одноместные функции. В принципе, об этом достаточно много сказано в любом учебнике по теории алгоритмов, так что поясню тезис довольно кратко. Если мы зафиксируем вычислительное устройство и язык программирования (например, машину Тьюринга со стандартной системой команд или обычный компьютер, снабжённый потенциально бесконечной памятью, и один из стандартных языков программирования, типа Паскаля или Си), то процедура проверки синтаксической правильности программы эффективна и существует алгоритм, проверяющий любой текст за конечное время и определяющий, является ли этот текст синтаксически правильно написанной программой. Так что мы можем, тупо перебирая все тексты (i.e. конечные последовательности символов заранее заданного конечного алфавита), выбирать из них все, являющиеся программами без синтаксических ошибок, и составлять из них список. Таким образом, мы можем эффективно сформировать список $P_0, P_1, P_2, \ldots$ всех программ , которые синтаксически корректны.

Далее. Из программ мы, на самом деле, можем выбирать только те, которые начинаются с оператора ввода некоторого числа, а заканчиваются оператором вывода некоторого числа, причём других операторов ввода и вывода в программе не присутствует. Таким образом, мы можем считать, что каждая программа в нашем списке предназначается для вычисления некоторой функции из $\mathbb{N}$ в $\mathbb{N}$. Мы считаем, что наше вычислительное устройство обладает свойством универсальности, то есть что для любой вычислимой функции из $\mathbb{N}$ в $\mathbb{N}$ найдётся число $i_0$, такое что программа $P_{i_0}$ вычисляет эту функцию.

Но тут есть одна тонкость. Несмотря на то, что каждая вычислимая функция вычисляется некоторой программой из нашего списка, отнюдь не каждая программа из списка вычисляет всюду определённую вычислимую функцию из $\mathbb{N}$ в $\mathbb{N}$. Дело в том, что программа, даже если она не содержит синтаксических ошибок, при некоторых входных данных может "зацикливаться", никогда не заканчивая работу. Стандартное соглашение, принимаемое в теории алгоритмов на этот счёт, гласит, что при тех входных данных, при которых программа "зацикливается", значение вычисляемой ею функции не определено. Таким образом, если не ограничиваться определёнными на всех натуральных аргументах функциями, а рассматривать наряду с ними также частичные функции из $\mathbb{N}$ в $\mathbb{N}$, то можно считать, что каждого $i \in \mathbb{N}$ программа $P_i$ вычисляет некоторую частичную функцию $\varphi_i$.

Далее. Введём трёхместную частичную функцию $\varphi_i^t(x)$ от трёх натуральных аргументов: $i$, $t$ и $x$. Мы считаем, что $\varphi_i^t(x)=n$, если программа $P_i$, вычисляя значение $\varphi_i(x)$, выдала ответ $n$ не более чем за $t$ шагов работы вычислительного устройства. В противном случае мы считаем, что $\varphi_i^t(x)$ не определено. Очевидно, что

$$\varphi_i(x)=n \Leftrightarrow \exists t(\varphi_i^t(x)=n) \Leftrightarrow \exists t_0 (\forall t \geqslant t_0)(\varphi_i^t(x)=n)$$

Кроме того, очевидно, что введённая трёхместная функция вычислима в самом сильном смысле. То есть по данной тройке натуральных чисел $\langle i,t,x \rangle$ мы за конечное число шагов можем сказать, определено ли значение $\varphi_i^t(x)$, и если оно определено, то можем сказать, чему оно равно.

Теперь мы хотим задать действительное число $0.\gamma_0\gamma_1\gamma_2\ldots$. Мы опишем некоторую эффективную процедуру (i.e. алгоритм), который будет перечислять последовательность десятичных разрядов $\gamma_0, \gamma_1, \ldots$. Процедура будет работать по шагам. На каждом шаге мы будем перечислять один или более элементов этой последовательности в порядке возрастания их индексов. Имея такую процедуру, мы можем утверждать, что функция, сопоставляющая натуральному числу $i$ разряд $\gamma_i$, вычислима. Действительно, чтобы для данного $i$ вычислить, чему равно $\gamma_i$, нам надо, получив на вход это $i$, запустить указанную процедуру и дождаться, когда она перечислит $i$-ый член последовательности. Это произойдёт за конечное время.

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

Шаг $t$. Смотрим, существует ли активное число $i \leqslant t$, такое что $\varphi_i^t(i)$ определено. Если нет, то перечисляем в последовательность гамма-итых число $1$ и переходим к следующему шагу. Если существует, то пусть $i_0$ --- наименьшее среди таких чисел. Так как $\varphi_{i_0}^t(i_0)$ определено, то мы знаем натуральное число $n$, такое что $\varphi_{i_0}(i_0) = n$. Сделаем число $i_0$ пассивным. Затем если $n=1$, то опять перечисляем в последовательность число $1$ и переходим к следующему шагу. Если же $n \neq 1$, то перечислим в последовательность сначала $1$, затем $i_0$ нулей и перейдём к следующему шагу.

Описание процедуры закончено. Докажем несколько лемм, из которых будет следовать, что для числа $0.\gamma_0\gamma_1\ldots$ функция $F$ не вычислима.

Лемма 1. Если значение $\varphi_i(i)$ определено, то на некотором шаге число $i$ становится пассивным.

Доказательство. Индукция по $i$. Пусть для всех $i' < i$ это так. Пусть $t_0$ настолько велико, что все числа $i' < i$, для которых $\varphi_{i'}(i')$ определено, стали пассивными до шага $t_0$. Пусть теперь $t$ таково, что $t > t_0$, $t \geqslant i$ и $\varphi_i^t(i)$ определено. Если число $i$ ещё не стало пассивным до шага $t$, то оно станет таковым на шаге $t$. $\qed$

Лемма 2. В последовательности $\gamma_0, \gamma_1, \ldots$ встречается ровно $i$ идущих подряд нулей тогда и только тогда, когда на некотором шаге $t$ число $i$ становится пассивным и $\varphi_i(i) \neq 1$.

Доказательство. Напрямую следует из описания конструкции. $\qed$

Лемма 3. Для построенного числа функция $F$ не вычислима.

Доказательство. Пусть $F$ вычислима. Тогда $F(x) = \varphi_i(x)$ для некоторого натурального $i$ и всех натуральных $x$. Так как $F$ определена на всех натуральных аргументах, то значение $\varphi_i(i) = F(i)$ определено. По лемме 1 число $i$ станет пассивным на некотором шаге. По лемме 2 в последовательности десятичных разрядов нашего числа встретится ровно $i$ идущих подряд нулей тогда и только тогда, когда $F(i) = \varphi_i(i) \neq 1$. Противоречие с определением функции $F$. $\qed$

Ну вот, сопственна, и фсё