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

1. Формальный степенной ряд $\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$.
2. Формальный степенной ряд $(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}$.
3. Формальный степенной ряд $\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$.
4. Докажите, что $\sin(2s) = 2 \sin(s) \cos(s)$.
5. Пусть $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)$.
6. Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что если $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
7. Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
8. Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
9. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
10. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
11. Последовательность $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}$
12. Последовательность $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$
13. Последовательность $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$
14. Последовательность $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$
15. Последовательность $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$
16. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
17. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
18. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
19. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
20. Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
21. Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
22. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность # Последовательность $1, -2, 3, -4, 5, \ldots$.
23. Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
24. Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
25. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.
26. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 010.
27. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 011.
28. Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
29. То же самое, что в предыдущем задании, но порядок монет не важен.
30. Несложно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
31. Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Каких?
32. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
33. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
34. Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей.
35. Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
36. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0 и не заходящих в отрицательную полупрямую.
37. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
38. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
39. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 5a_{n-1}-6a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
40. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
41. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
42. Петя заинтересовался, что будет, если последовательность, заданная линейным рекуррентным соотношением, имеет производящую фукнцию, в знаменателе которой стоит $Q(t)=(1-ct)(1+ct)$, ведь тогда асимптотическое поведение членов на четных и нечетных позициях разное. Разберитесь.
43. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
44. Пусть рациональная производящая функция имеет вид $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)}$
45. Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
46. Произведением Адамара двух производящих функций $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)$.
47. Найдите произведение Адамара $\frac{1}{1-x}$ и $\frac{1}{1-2x}$.
48. Найдите произведение Адамара $\frac{1}{1-2x}$ и $\frac{1}{1-3x}$.
49. Найдите произведение Адамара $\frac{1}{1+3x-x^2}$ и $\frac{1}{1-2x}$.
50. Найдите произведение Адамара $\frac{1}{(1-3x)^2}$ и $\frac{1}{(1-2x)^2}$.
51. Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
52. Пусть $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$.
53. Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
54. Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.
55. Определим множество "неориентированных последовательностей" $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)}$
56. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.
57. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где расстояние между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.
58. Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.
59. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых нет более $k$ подряд идущих нулей или единиц.
60. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.
61. Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.
62. Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.
63. Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.
64. Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых, порядок слагаемых не важен.
65. Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производяющую функцию для $P^T$.
66. Индекс Хирша. Докажите, что $\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}$.
67. Опишите класс помеченных объектов $seq(cyc(Z))$. Найдите его экспоненциальную производящую функцию.
68. Будем обозначать $seq_T$, $cyc_T$, $set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $set(cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
69. Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.
70. Опишите класс помеченных объектов $set(cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
71. Сюръекции на $r$-элементное множество. Осознайте, что $seq_{=r}(set_{\ge 1}(Z))$ задаёт сюръекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
72. Разбиения на $r$ множеств. Осознайте, что $set_{=r}(set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
73. Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$.
74. Гиперболический синус $\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)$.
75. Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
76. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
77. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
78. Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
79. Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
80. Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
81. Докажите, что для четного N количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.
82. "Произведение с коробочкой": Обозначим $C = A^{\square} \star B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $C_n$.
83. Докажите, что если $C = A^{\square} \star B$, то $C'(z) = A'(z) \cdot B(z)$.
84. Докажите, что объединение перечислимых языков перeчислимо.
85. Докажите, что пересечение перечислимых языков перeчислимо.
86. Докажите, что конкатенация перечислимых языков перeчислима.
87. Докажите, что замыкание Клини перечислимого языка перeчислимо.
88. Докажите, что декартово произведение перечислимых языков перeчислимо.
89. Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
90. Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
91. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
92. Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
93. Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
94. В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
95. Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
96. Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
97. Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
98. Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
99. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
100. Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
101. Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
102. Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
103. Докажите, что множество программ, допускающих конечное множество слов не разрешимо.
104. Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
105. Докажите, что множество программ, зависающих на любом входе, не разрешимо.
106. Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
107. Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B,$ где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
108. Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
109. Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
110. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
111. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
112. Множество $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)\}$ является разрешимым?
113. В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
114. Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha − a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
115. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
116. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
117. Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
118. Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
119. Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
120. Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
121. Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо перечислимого множества $P$. Она всегда перечислима снизу, но будет вычислимой только при разрешимом $P$.)
122. Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
123. Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
124. Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
125. Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
126. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
127. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
128. Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
129. Докажите, что язык программ для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
130. Докажите, что язык программ для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является неразрешимым.
131. Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
132. Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 125-128. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
133. Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
134. Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
135. Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
136. Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
137. Клеточный автомат представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии, множество состояний $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$ клеточный автомат эквивалентен по вычислительной мощности машине Тьюринга.
138. Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы.
139. Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные.
140. Модифицируем счётчиковую машину: разрешим счётчикам хранить как положительные, так и отрицательные значения (сравнивать можно по прежнему только с нулём). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
141. Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
142. Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков?
143. Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $\delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками.
144. Специальное задание. Автоматы Вольфрама. Рассмотрим клеточный автомат с двумя состояниями и $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). Изучите разные правила. Выберите наиболее интересные по вашему мнению правила переходов.
145. Специальное задание. Игра "Жизнь" Конвея. Рассмотрим бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по следующему правилу: если у белой клетки ровно три из восьми черных соседа, она становится черной, иначе остаётся белой. Если у черной клетки 2 или 3 из 8 соседей черные, она остаётся черной, иначе она становится белой. Найдите в интернете симулятор игры жизнь и примеры интересных конфигураций. Поэкспериментируйте с ними.