Редактирование: Список заданий по ДМ 2к 2020 весна

# Формальный степенной ряд $\exp(s) = e^s$ определен как $e^s=1+\frac{1}{1!}s+\frac{1}{2!}s^2+\frac{1}{3!}s^3+\ldots+\frac{1}{n!}s^n+\ldots$. Логично, что $e^{-s}=1-\frac{1}{1!}s+\frac{1}{2!}s^2-\frac{1}{3!}s^3+\ldots+(-1)^n\frac{1}{n!}s^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^se^{-s}=1$.
# Формальный степенной ряд $(1+s)^\alpha$ определен как $(1+s)^\alpha=1+\frac{\alpha}{1}s+\frac{\alpha(\alpha-1)}{1 \cdot 2}s^2+\ldots+\frac{\alpha(\alpha-1)\ldots(\alpha-n+1)}{1 \cdot 2 \cdot\ldots\cdot n}s^n+\ldots$. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.
# Формальный степенной ряд $\cos(s)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {s^{2n}}{(2n)!}$, а $\sin(s)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {s^{2n+1}}{(2n+1)!}$. Докажите, что $\sin^2(s) + \cos^2(s) = 1$.
# Докажите, что $\sin(2s) = 2 \sin(s) \cos(s)$.
# Пусть $B(s) = b_1s+b_2s^2+b_3s^3+\ldots+b_ns^n+\ldots$, причем $b_1\ne 0$. Пусть формальные степенные ряды $A(s)$ и $C(s)$ таковы, что $A(B(s)) = s$, $B(C(s))=s$. Докажите, что $A(s)=C(s)$ Этот ряд называется обратным к $B(s)$, обозначается как $B^{-1}(s)$.
# Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что если $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
# Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
# Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
# Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
# Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k, \ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3 \ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6 \ldots$
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
# Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
# Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
# Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность # Последовательность $1, -2, 3, -4, 5, \ldots$.
# Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
# Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 010.
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 011.
# Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
# То же самое, что в предыдущем задании, но порядок монет не важен.
# Несложно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
# Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Каких?
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками. 
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей.
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0 и не заходящих в отрицательную полупрямую. 
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 5a_{n-1}-6a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Петя заинтересовался, что будет, если последовательность, заданная линейным рекуррентным соотношением, имеет производящую фукнцию, в знаменателе которой стоит $Q(t)=(1-ct)(1+ct)$, ведь тогда асимптотическое поведение членов на четных и нечетных позициях разное. Разберитесь.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Пусть рациональная производящая функция имеет вид $A(s) = \frac {P(s)}{Q(s)}$, где единственный минимальный по модулю корень $Q(s)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^n n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^k P(1 / \beta)} {Q^{(k)}(1 / \beta)}$
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
# Произведением Адамара двух производящих функций $A(t)$ и $B(t)$ называется призводящая функция для ряда $C(t) = a_0b_0+a_1b_1t+a_2b_2t^2+\ldots+a_nb_nt^n+\ldots$. Докажите, что если $A(t)$ и $B(t)$ являются отношениями двух полиномов, то таким же свойством обладает и $C(t)$.
# Найдите произведение Адамара $\frac{1}{1-x}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{1-2x}$ и $\frac{1}{1-3x}$.
# Найдите произведение Адамара $\frac{1}{1+3x-x^2}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{(1-3x)^2}$ и $\frac{1}{(1-2x)^2}$.
# Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Пусть $\mathbb{N}$ - множество натуральных чисел, (вес числа $k$ равен $k$). Пусть $T \subset \mathbb{N}$, обозначим как $T(t)$ производящую функцию для множества $T$. Обозначим как $Seq_T(A)$ множество последовательностей элементов из $A$, где длина последовательности лежит в множестве $T$. Обозначим как $Z$ множество из одного элемента веса $1$. Обозначим как $C^T$ множество представлений в виде суммы, где порядок слагаемых важен и слагаемые выбраны из множества $T$. Осознайте, что $C^T = Seq(Seq_T(Z))$. Найдите производяющую функцию для $C^T$.
# Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
# Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.
# Определим множество "неориентированных последовательностей" $B = USeq(A)$, как множество всех последовательностей элементов из $A$, где последовательность $L$ и $rev(L)$ считаются одинаковыми. Покажите, что $B(t) = \frac 12 \frac {1}{1 - A(t)} + \frac 12 \frac {1 + A(t)}{1 - A(t^2)}$
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где расстояние между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.
# Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых нет более $k$ подряд идущих нулей или единиц.
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.
# Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.
# Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.
# Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.
# Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых, порядок слагаемых не важен.
# Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производяющую функцию для $P^T$.
# Индекс Хирша. Докажите, что $\prod\limits_{n=1}^\infty\frac{1}{1-z^n}=\sum\limits_{n\ge 0}\frac{z^{n^2}}{((1-z)\cdots(1-z^n))^2}$.
# Опишите класс помеченных объектов $seq(cyc(Z))$. Найдите его экспоненциальную производящую функцию.
# Будем обозначать $seq_T$, $cyc_T$, $set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $set(cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
# Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.
# Опишите класс помеченных объектов $set(cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
# Сюръекции на $r$-элементное множество. Осознайте, что $seq_{=r}(set_{\ge 1}(Z))$ задаёт сюръекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
# Разбиения на $r$ множеств. Осознайте, что $set_{=r}(set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
# Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$. 
# Гиперболический синус $\mathrm{sh}\,z$ равен $\frac{1}{2}(e^{z}-e^{-z})$. Гиперболический косинус $\mathrm{ch}\,z$ равен $\frac{1}{2}(e^{z}+e^{-z})$. Рассмотрим разбиения $n$-элементного множества на непустые подмножества. Докажите, что для разбиений на нечетное число подмножеств экспоненциальная производящая функция равна $\mathrm{sh}(e^z-1)$.
# Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
# Докажите, что для четного N количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.
# "Произведение с коробочкой": Обозначим $C = A^{\square} \star B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $C_n$.
# Докажите, что если $C = A^{\square} \star B$, то $C'(z) = A'(z) \cdot B(z)$.
# Докажите, что объединение перечислимых языков перeчислимо.
# Докажите, что пересечение перечислимых языков перeчислимо.
# Докажите, что конкатенация перечислимых языков перeчислима.
# Докажите, что замыкание Клини перечислимого языка перeчислимо.
# Докажите, что декартово произведение перечислимых языков перeчислимо.
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
# Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
# Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
# Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
# Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
# Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
# Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
# Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
# Докажите, что множество программ, допускающих конечное множество слов не разрешимо.
# Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
# Докажите, что множество программ, зависающих на любом входе, не разрешимо.
# Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B,$ где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
# Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
# Множество $A \subset \mathbb{N} \times \mathbb{N}$ разрешимо. Можно ли утверждать, что множество «нижних точек» множества $A$, то есть множество $B = \{\langle x,y\rangle | (\langle x,y\rangle \in A)$ и $(\langle x,z\rangle \not\in A$ для всех $z < y)\}$ является разрешимым? 
# В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha − a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
# Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
# Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
# Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\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. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
# Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
# Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Клеточный автомат представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии, множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$. Исходно все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от 1 до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d  + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$. Докажите, что для некоторого $d \ge 1$ клеточный автомат эквивалентен по вычислительной мощности машине Тьюринга.
# Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы.
# Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные.
# Модифицируем счётчиковую машину: разрешим счётчикам хранить как положительные, так и отрицательные значения (сравнивать можно по прежнему только с нулём). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
# Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
# Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков?
# Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $\delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками.
# Специальное задание. Автоматы Вольфрама. Рассмотрим клеточный автомат с двумя состояниями и $d = 1$. Пусть $n = 1$ и исходно нулевая клетка в состоянии $1$, а остальные клетки в состоянии $0$. Переходы автомата можно задать восемью битами: новым состоянием клетки для всех 8 возможных состояний клеткии её соседей. Можно нарисовать состояние всех клеток после каждого шага в виде двумерного изображения (см, например, https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE_110 для правила 110). Изучите разные правила. Выберите наиболее интересные по вашему мнению правила переходов.
# Специальное задание. Игра "Жизнь" Конвея. Рассмотрим бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по следующему правилу: если у белой клетки ровно три из восьми черных соседа, она становится черной, иначе остаётся белой. Если у черной клетки 2 или 3 из 8 соседей черные, она остаётся черной, иначе она становится белой. Найдите в интернете симулятор игры жизнь и примеры интересных конфигураций. Поэкспериментируйте с ними.
# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим КС-грамматику с одним нетерминалом $S$, алфавитом $\Sigma'$ и $n + 1$ правилом: $S \to \alpha_1 S d_1$,  $S \to \alpha_2 S d_2, \ldots, S \to \alpha_n S d_n$, $S \to \varepsilon$. Язык, порождаемый этой грамматикой, называется языком списка $A$ и обозначается как $L_A$. Опишите все слова языка $L_A$. 
# Докажите, что для любого списка $A$ дополнение до его языка списка $\overline{L_A}$ является КС-языком. Указание: постройте МП-автомат для $\overline{L_A}$.
# Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.
# Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.
# Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.
# Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.
# Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.
# Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.
# Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.
# Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
# Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
# Односторонние исчисления. Рассмотрим rjytxysq набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
# Двусторонние исчисления. Рассмотрим конечный алфавит $\Sigma$ и набор правил вида $\alpha \leftrightarrow \beta$. Будем говорить, что слова $x$ и $y$ эквивалентны с точностью до $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила или $\beta$ для некоторого правила на $\alpha$ для этого правила. Докажите, что множество троек $(P, x, y)$, где $x$ эквивалентен $y$ с точность до $P$ неразрешимо.
# Докажите, существует конкретное множество правил одностороннего исчисления $P$, что для него множество пар $(x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
# Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
# Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$..
@@ Строка 155: / Строка 155: @@
 # Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
 # Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
-# Односторонние исчисления. Рассмотрим конечный набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
+# Односторонние исчисления. Рассмотрим rjytxysq набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
 # Двусторонние исчисления. Рассмотрим конечный алфавит $\Sigma$ и набор правил вида $\alpha \leftrightarrow \beta$. Будем говорить, что слова $x$ и $y$ эквивалентны с точностью до $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила или $\beta$ для некоторого правила на $\alpha$ для этого правила. Докажите, что множество троек $(P, x, y)$, где $x$ эквивалентен $y$ с точность до $P$ неразрешимо.
 # Докажите, существует конкретное множество правил одностороннего исчисления $P$, что для него множество пар $(x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
 # Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
 # Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$..
-# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит палиндром.
-# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова одинаковой длины.
-# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова разной длины.
-# Докажите, что следующее свойство перечислимых языков не является перечислимым: все слова языка имеют различную длину.
-# Докажите, что следующее свойство перечислимых языков не является перечислимым: язык не содержит заданное слово $x$.
-# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) = 1$?
-# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) \ne 1$?
-# Множество $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$ является эффективно неперечислимым.
-# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
-# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
-# Рассмотрим два множества $A$ и $B$. Назовём их вычислимо изоморфными, если существует всюду определенная вычислимая биекция $\varphi : \mathbb{N} \to \mathbb{N}$, такая что $x \in A$ тогда и только тогда, когда $\varphi(x) \in B$. Приведите пример различных бесконечных вычислимо изоморфных множеств.
-# Докажите или опровергните, что любые два бесконечных разрешимых множества, дополнения к которым также бесконечны, являются вычислимо изоморфными.
-# Докажите или опровергните, что любые два бесконечных перечислимых множества, дополнения к которым также бесконечны, являются вычислимо изоморфными.
-# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
-# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
-# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.