Изменения
Нет описания правки
# Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
# Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо перечислимого множества $P$. Она всегда перечислима снизу, но будет вычислимой только при разрешимом $P$.)
# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
# Докажите, что язык программ для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
# Докажите, что язык программ для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является неразрешимым.
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 125-128. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
