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

ВАЖНО

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

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

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

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

Наши рекомендации