1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.
# Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.
# Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы.
# Модифицируем счётчиковую машину: разрешим счётчикам хранить как положительные, так и отрицательные значения (сравнивать можно по прежнему только с нулём). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
# Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками.
# Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
# Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
# Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные.
# Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков?
# Вещественное число $\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$.
# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел
# (только 34-35) Рассмотрим список слов $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}$.
# (только 34-35) Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.
# Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.
# Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.
# Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.
# Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.
# Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.
# Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.
# Пусть задано два списка $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$ неразрешимо.
# Двусторонние исчисления. Рассмотрим конечный алфавит $\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$.
# Множество $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$ является эффективно неперечислимым.
# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
