Теория вычислимости:Тикеты

Материал из Викиконспекты
Версия от 00:16, 3 июня 2018; Lapenok.aleksej (обсуждение | вклад) (→‎Разрешимые и перечислимые языки)
Перейти к: навигация, поиск

3. Теория вычислимости

Разрешимые и перечислимые языки

  1. Разрешимые (рекурсивные) языки
  2. Перечислимые языки 0.5
    1. добавить см также
  3. Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций 0.5
    1. поправить тех
  4. Вычислимые функции 0.5
    1. добавить см также
  5. Вычислимые числа 0.5
    1. поправить тех
  6. Универсальная функция
  7. Свойства перечислимых языков. Теорема Успенского-Райса 0.5
    1. поправить тех и псевдокод
  8. Неотделимые множества
    1. поправить тех
    2. добавить см также
  9. Иммунные и простые множества
  10. Теорема о рекурсии 0.5
    1. поправить псевдокод
    2. поправить тех
    3. сделать см также на проверяемые конспекты
  11. Квайны 0.5
    1. поправить псевдокод
    2. добавить см также
  12. Busy beaver 0.5
    1. поправить псевдокод
  13. Колмогоровская сложность 0.5
    1. поправить всевдокод

Вычислительные формализмы

  1. Машина Тьюринга
  2. Лямбда-исчисление
  3. Примитивно рекурсивные функции
  4. Частично рекурсивные функции
  5. Стековые машины, эквивалентность двухстековой машины МТ
  6. Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
  7. Линейный клеточный автомат, эквивалентность МТ
  8. Возможность порождения формальной грамматикой произвольного перечислимого языка
  9. Линейный ограниченный автомат
  10. Сверхтьюринговые вычисления (гипервычисления)
  11. Тьюринг-полнота (4)
    1. Провести аналогию с теоремой Геделя о неполноте

Примеры неразрешимых задач

  1. m-сводимость
  2. Проблема соответствий Поста
  3. Однозначность КС-грамматики
  4. Неразрешимость задачи об эквивалентности КС-грамматик
  5. Пустота пересечения КС-грамматик
  6. Задача о замощении полимино
  7. Задача о выводе в полусистеме Туэ
  8. Неразрешимость исчисления предикатов первого порядка
  9. Неразрешимость проблемы существования решения диофантова уравнения в целых числах (10)
    1. дописать, чтобы было классно
  10. Неразрешимость задачи вывода типов в языке с зависимыми типами (3)
    1. [math]\beta[/math]-эквивалентны в интервики
    2. добавить пару примеров вывода типа в данной системе
  11. Игра «Жизнь»
  12. Неразрешимость игры Braid
  13. Теорема Райса-Шапиро
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_вычислимости:Тикеты&oldid=65855»