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

Название	Формулировка (надо знать обязательно, кроме раздела «теоремы» может быть проверена в разделе «определения» или «угадайка»)	Доказательство (проверяется в раздеде «теоремы»)
	Всякая 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) также примитивно рекурсивна	В лекциях есть На экз надо знать
	Примитивно-рекурсивные функции эффективно перечислимы	В лекциях есть На экз надо знать
	Множество частично-рекурсивных функций эффективно перечислимо	В лекциях есть На экз надо знать
	Общерекурсивные функции не поддаются эффективному перечислению	В лекциях есть На экз надо знать
	Примитивно-рекурсивные функции не поддаются эффективному распознаванию среди общерекурсивных функций	В лекциях есть На экз надо знать
	Общерекурсивные функции не поддаются эффективному распознаванию среди частично рекурсивных функций	В лекциях есть На экз надо знать

ВАЖНО

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

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

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

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