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

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

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

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

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

14. Машина Тьюринга
15. Лямбда-исчисление
16. Примитивно рекурсивные функции
17. Частично рекурсивные функции
18. Стековые машины, эквивалентность двухстековой машины МТ
19. Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
20. Линейный клеточный автомат, эквивалентность МТ
21. Возможность порождения формальной грамматикой произвольного перечислимого языка
22. Линейный ограниченный автомат
23. Сверхтьюринговые вычисления (гипервычисления)

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

24. m-сводимость
25. Проблема соответствий Поста
26. Однозначность КС-грамматики
27. Неразрешимость задачи об эквивалентности КС-грамматик
28. Задача о замощении полимино
29. Задача о выводе в полусистеме Туэ
30. Неразрешимость исчисления предикатов первого порядка
31. взяли Неразрешимость проблемы существования решения диофантова уравления в целых числах (10)
1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
32. Игра «Жизнь»
33. Неразрешимость игры Braid
34. Теорема Райса-Шапиро