| Название | Формулировка (надо знать обязательно, кроме раздела «теоремы» может быть проверена в разделе «определения» или «угадайка») | Доказательство (проверяется в раздеде «теоремы») |
| Всякая k -ленточная машина Тьюринга М может быть преобразована в эквивалентную машину М* с одной лентой. | В лекциях есть На экз надо знать | |
| Теорема Шеннона №1 | Всякая машина Тьюринга А может быть преобразована в эквивалентную машину В не более чем с двумя внутренними состояниями. | В лекциях есть На экз не будет |
| Теорема Шеннона №2 | Всякая машина Тьюринга А может быть преобразована в эквивалентную машину С не более чем с двумя знаками внешнего алфавита. | В лекциях есть На экз не будет |
| Задача об остановке произвольной машины Тьюринга на произвольном входном слове алгоритмически неразрешима. | В лекциях есть На экз надо знать | |
| Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима | В лекциях есть На экз надо знать | |
| Задача о печатании данного символа на чистой ленте точно один раз алгоритмически неразрешима | В лекциях есть На экз надо знать | |
| Задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима | В лекциях есть На экз надо знать | |
| Задача о печатании данного символа на чистой ленте хотя бы один раз алгоритмически неразрешима | В лекциях есть На экз надо знать | |
| Теорема Райса | Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует алгоритма, позволяющего для любой машины Тьюринга узнать, обладает ли она этим свойством | Без доказательства |
| Множество машин Тьюринга эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество алгоритмов Маркова эффективно перечислимо | В лекциях есть На экз надо знать | |
| Теорема Поста | Если множество А эффективно перечислимо, то подмножество В эффективно распознается в А тогда и только тогда, когда В и А\В оба эффективно перечислимы | В лекциях есть На экз надо знать |
| Множество останавливающихся машин Тьюринга эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество не останавливающихся машин Тьюринга невозможно эффективно перечислить | В лекциях есть На экз надо знать | |
| Парадокс Галилея | Хотя большинство натуральных чисел не является квадратами, всех натуральных чисел не больше, чем квадратов (если сравнивать эти множества по мощности) | В лекциях есть На экз надо знать |
| Парадокс Гильберта | Если гостиница с бесконечным количеством номеров полностью заполнена, в неё можно поселить ещё посетителей, даже бесконечное число | В лекциях есть На экз надо знать |
| Множество целых чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество упорядоченных пар натуральных чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество упорядоченных n-ок натуральных чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество конечных комплексов натуральных чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество рациональных чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество алгебраических чисел счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Множество элементов, которые можно представить с помощью конечного числа счетной системы знаков, счетно | Без доказательства | |
| Множество действительных чисел несчётно | В лекциях есть На экз надо знать | |
| Множество комплексных чисел несчетно | В лекциях есть На экз надо знать | |
| Множество иррациональных чисел несчетно | В лекциях есть На экз надо знать | |
| Множество трансцендентных чисел несчетно | В лекциях есть На экз надо знать | |
| Между любыми двумя различными рациональными числами всегда найдется множество иррациональных чисел мощности континуума | В лекциях есть На экз не будет | |
| Между любыми двумя различными иррациональными числами всегда найдется счетное множество рациональных чисел | В лекциях есть На экз не будет | |
| Теорема Кантора | Для любого кардинального числа α справедливо α<2α | В лекциях есть На экз надо знать |
| Для любого множества А найдется множество В, мощность которого больше А | В лекциях есть На экз не будет | |
| Парадокс Кантора | Кардинальное число множества всех подмножеств P(U) множества всех множеств U не больше чем |U| | В лекциях есть На экз не будет |
| Парадокс Рассела | Пусть В – множество всех множеств, которые не содержат самих себя в качестве своих собственных элементов. Тогда можно доказать две теоремы: В принадлежит В и В не принадлежит В | В лекциях есть На экз не будет |
| Множество вычислимых действительных чисел счетно | В лекциях есть На экз надо знать | |
| Существуют невычислимые действительные числа и их несчетное множество | На экз надо знать | |
| Множество арифметических функций n-переменных несчетно | В лекциях есть На экз надо знать | |
| Множество вычислимых арифметических функций счетно | В лекциях есть На экз надо знать | |
| Теорема Тьюринга | Множество вычислимых арифметических функций n переменных не поддается эффективному перечислению | В лекциях есть На экз надо знать |
| Множество невычислимых арифметических функций несчетно | В лекциях есть На экз надо знать | |
| Множество арифметических функций, описываемых конечным числом слов, счетно и эффективно перечислимо | В лекциях есть На экз не будет | |
| Множество частичных арифметических функций несчетно | В лекциях есть На экз надо знать | |
| Множество вычислимых частичных арифметических функций счетно и эффективно перечислимо | В лекциях есть На экз надо знать | |
| Невозможно эффективно распознать функции-константы среди вычислимых арифметических функций | В лекциях есть На экз надо знать | |
| Вычислимые арифметические функции не поддаются эффективному сравнению | В лекциях есть На экз надо знать | |
| Невозможно эффективно распознать функции-тождества среди вычислимых арифметических функций | В лекциях есть На экз надо знать | |
| Невозможно эффективно распознать вычислимые арифметические функции среди вычислимых частичных арифметических функций | В лекциях есть На экз надо знать | |
| Теорема Черча | Невозможно эффективно распознать точки неопределенности вычислимой частичной арифметической функции | В лекциях есть На экз надо знать |
| Теорема о мажорируемых неявных функциях | Пусть g(x1,…,xn, y), a(x1,…,xn) – такие примитивно-рекурсивные функции, что уравнение g(x1,…,xn, y)=0 для каждых x1,…,xn имеет по меньшей мере одно решение и μy(g(x1,…,xn, y)=0) ≤ a(x1,…,xn) для любых x1,…,xn. Тогда функция f(x1,…,xn)= μy(g(x1,…,xn, y)=0) также примитивно рекурсивна | В лекциях есть На экз надо знать |
| Примитивно-рекурсивные функции эффективно перечислимы | В лекциях есть На экз надо знать | |
| Множество частично-рекурсивных функций эффективно перечислимо | В лекциях есть На экз надо знать | |
| Общерекурсивные функции не поддаются эффективному перечислению | В лекциях есть На экз надо знать | |
| Примитивно-рекурсивные функции не поддаются эффективному распознаванию среди общерекурсивных функций | В лекциях есть На экз надо знать | |
| Общерекурсивные функции не поддаются эффективному распознаванию среди частично рекурсивных функций | В лекциях есть На экз надо знать |
ВАЖНО
Если у теоремы (парадокса) имеется НАЗВАНИЕ, но нет доказательства, или доказательство помечено как необязательное к запоминанию, то формулировка теоремы может быть проверена на экзамене в разделе «Определения» или «Угадайка».
Если у теоремы (парадокса) имеется НАЗВАНИЕ и необходимо знать ДОКАЗАТЕЛЬСТВО, то в билете в разделе «Теоремы» может быть приведено ТОЛЬКО название – формулировка и доказательство должен написать студент. Таких теорем в курсе всего СЕМЬ – сильно рекомендуется обратить на них особое внимание.
Если у теоремы (парадокса) НЕТ названия и необходимо знать ДОКАЗАТЕЛЬСТВО, то в билете в разделе «Теоремы» будет приведена формулировка, возможно с отсутствием ключевого слова (перечислимо/не перечислимо, распознается/не распознается). В этом случае студентом производится уточнение формулировки (обводится нужное ключевое слово) и далее необходимо привести текст доказательства.
Если у теоремы (парадокса) НЕТ названия и нет доказательства, или доказательство помечено как необязательное к запоминанию (т.е. по сути надо знать только формулировку), то на экзамене знание этой формулировки может быть проверено в разделе «Угадайка».
