Изменения
Нет описания правки
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 172-175. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha − a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима. Последовательность называется вычислимой, если существует программа, которая по номеру $i$ выдает соответствующий элемент последовательности $a_i$.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
# Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы.
# Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
# Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
# Докажите, что множество функций-приближений для рациональных вычислимых чисел $\alpha$ является неразрешимым. Указание: вспомните теорему о рекурсии.
# Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо множества $P$.
# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел
# Множество $A$ назвается эффективно бесконечным, если существует всюду определенная вычислимая функция $f$, которая по числу $n$ выводит $n$ различных элементов множества $A$. Докажите, что если множество $A$ содержит бесконечное перечислимое подмножество, то оно эффективно бесконечно.
# Докажите, что если множество $A$ эффективно бесконечно, то оно содержит бесконечное перечислимое подмножество.
# Обозначим как $L(p)$ множество слов, которые допускается программой $p$. Множество $A$ назвается эффективно неперечислимым, если существует всюду определенная вычислимая функция $f$, которая по программе $p$ указывает слово $x$, такое что $x \in L(p) \oplus A$. Докажите, что дополнение к диагонали универсального множества $\overline D$, где $D = \left\{p | \langle p, p\rangle \in U\right\}$, является эффективно неперечислимым.
# Докажите, что дополнение к универсальному множеству $\overline U$ является эффективно неперечислимым.
# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
