Список теорем к экзамену – зима, 2013 г

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

ВАЖНО

Если у теоремы (парадокса) имеется НАЗВАНИЕ, но нет доказательства, или доказательство помечено как необязательное к запоминанию, то формулировка теоремы может быть проверена на экзамене в разделе «Определения» или «Угадайка».

Если у теоремы (парадокса) имеется НАЗВАНИЕ и необходимо знать ДОКАЗАТЕЛЬСТВО, то в билете в разделе «Теоремы» может быть приведено ТОЛЬКО название – формулировка и доказательство должен написать студент. Таких теорем в курсе всего СЕМЬ – сильно рекомендуется обратить на них особое внимание.

Если у теоремы (парадокса) НЕТ названия и необходимо знать ДОКАЗАТЕЛЬСТВО, то в билете в разделе «Теоремы» будет приведена формулировка, возможно с отсутствием ключевого слова (перечислимо/не перечислимо, распознается/не распознается). В этом случае студентом производится уточнение формулировки (обводится нужное ключевое слово) и далее необходимо привести текст доказательства.

Если у теоремы (парадокса) НЕТ названия и нет доказательства, или доказательство помечено как необязательное к запоминанию (т.е. по сути надо знать только формулировку), то на экзамене знание этой формулировки может быть проверено в разделе «Угадайка».