Участник:Shersh/Тикеты к 5ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(2. Контекстно-свободные грамматики)
(3. Теория вычислимости)
Строка 275: Строка 275:
  
 
=== Вычислительные формализмы ===
 
=== Вычислительные формализмы ===
# '''!!!''' [[Машина Тьюринга]]
+
<ol>
## Англоязычные термины
+
<li value="12">'''!!!''' [[Машина Тьюринга]] </li>
## Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
+
# Англоязычные термины
## Выделить машину Тьюринга жирным в определении
+
# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
## Алгоритмы примеров красиво оформить
+
# Выделить машину Тьюринга жирным в определении
## Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
+
# Алгоритмы примеров красиво оформить
## Добавить в многоленточной, что эмулируется многодорожечной
+
# Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
## Рассказать весёлую историю про тезис Чёрча-Тьюринга
+
# Добавить в многоленточной, что эмулируется многодорожечной
## Заменить ссылки на источники информации
+
# Рассказать весёлую историю про тезис Чёрча-Тьюринга
## Добавить категории
+
# Заменить ссылки на источники информации
# '''!!!''' [[Лямбда-исчисление]] ''(можно получить 10 баллов суммарно)''
+
# Добавить категории
## Англоязычные термины
+
<li> '''!!!''' [[Лямбда-исчисление]] ''(можно получить 10 баллов суммарно)'' </li>
## Заменить "в разработке" на "nohate"
+
# Англоязычные термины
## Написать грамматику лямбд адекватно
+
# Заменить "в разработке" на "nohate"
## "Аппликация забирает себе всё," - ошибка - абстракция забирает
+
# Написать грамматику лямбд адекватно
## Провести аналогию между связанными переменными и локальными переменными
+
# "Аппликация забирает себе всё," - ошибка - абстракция забирает
## "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?
+
# Провести аналогию между связанными переменными и локальными переменными
## Написать, что alpha-конверсия -- отношение эквивалентности
+
# "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?
## beta-редукция не олицетворяет. Написать определение формально
+
# Написать, что alpha-конверсия -- отношение эквивалентности
## Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней
+
# beta-редукция не олицетворяет. Написать определение формально
## Провести аналогию между нумералами Чёрча и нумерацией Гёделя
+
# Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней
## Убрать маркированный список из чисел, лучше просто отступ оставить
+
# Провести аналогию между нумералами Чёрча и нумерацией Гёделя
## "<<числу>>" {{---}} получше оформить
+
# Убрать маркированный список из чисел, лучше просто отступ оставить
## Все константы и переменные взяь в Tex
+
# "<<числу>>" {{---}} получше оформить
## Добавить примеры выполнения операций сложения, умножения и вычитания
+
# Все константы и переменные взяь в Tex
## "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается
+
# Добавить примеры выполнения операций сложения, умножения и вычитания
## Добавить в неподвижной точке про Y-комбинатор
+
# "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается
## Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном
+
# Добавить в неподвижной точке про Y-комбинатор
## Оформить правильно источники информации, см. также
+
# Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном
## Добавить категории
+
# Оформить правильно источники информации, см. также
# '''!!!''' [[Примитивно рекурсивные функции]]
+
# Добавить категории
## названия функций надо в \mathrm
+
<li> '''!!!''' [[Примитивно рекурсивные функции]] </li>
## Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
+
# названия функций надо в \mathrm
# '''!!!''' [[Частично рекурсивные функции]]
+
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
## См. замечания в обсуждениях
+
<li> '''!!!''' [[Частично рекурсивные функции]] </li>
## англоязычные термины
+
# См. замечания в обсуждениях
## Дефис заменить на тире
+
# англоязычные термины
## "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом
+
# Дефис заменить на тире
## Заменить знаки неравенств  
+
# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом
## "неразрешимость проврк," {{---}} опечатки
+
# Заменить знаки неравенств  
## Оформить правильно источники информации
+
# "неразрешимость проврк," {{---}} опечатки
## Добавить категории
+
# Оформить правильно источники информации
# [[Стековые машины, эквивалентность двухстековой машины МТ]]
+
# Добавить категории  
## Интервики
+
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li>
## Разбить доказательство на абзацы для читабельности
+
# Интервики
## Добавить категории
+
# Разбить доказательство на абзацы для читабельности
## Правильно оформить источники информации
+
# Добавить категории
# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
+
# Правильно оформить источники информации
## Оформить правильно источники информации
+
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
## Добавить категории
+
# Оформить правильно источники информации
# [[Линейный клеточный автомат, эквивалентность МТ]]
+
# Добавить категории  
## Англоязычные термины правильно оформить
+
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
## Переменные взять в Tex
+
# Англоязычные термины правильно оформить
## Добавить категории
+
# Переменные взять в Tex
## Оформить правильно источники информации
+
# Добавить категории
# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
+
# Оформить правильно источники информации
## внутренние ссылки
+
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
## категории
+
# внутренние ссылки
## Добавить см. также и источники информации
+
# категории
 +
# Добавить см. также и источники информации
 +
</ol>
 
=== Примеры неразрешимых задач ===
 
=== Примеры неразрешимых задач ===
# '''!!!''' [[m-сводимость]]
+
<ol>
## Англоязычные термины правильно оформить
+
<li value="20"> '''!!!''' [[m-сводимость]] </li>
## Добавить примеры m-сведения задач
+
# Англоязычные термины правильно оформить
## Заменить знаки неравенств
+
# Добавить примеры m-сведения задач
## Добавить категории
+
# Заменить знаки неравенств
## Ссылку на ПСП оформить правильно
+
# Добавить категории
## Переменные и константы взять в Tex
+
# Ссылку на ПСП оформить правильно
# '''!!!''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
+
# Переменные и константы взять в Tex
## Англоязычные термины правильно оформить
+
<li> '''!!!''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
## Заменить дефисы на тире
+
# Англоязычные термины правильно оформить
## Заменить знаки неравенств
+
# Заменить дефисы на тире
## Все переменные и константы взять в Tex
+
# Заменить знаки неравенств
## Добавить примеров решения задач ПСП
+
# Все переменные и константы взять в Tex
## Отфомартировать псевдокод
+
# Добавить примеров решения задач ПСП
## Добавить больше подзаголовков нижнего уровня
+
# Отфомартировать псевдокод
## Больше интервики
+
# Добавить больше подзаголовков нижнего уровня
## Заменить источники на источники информации
+
# Больше интервики
## Добавить категории, см. также
+
# Заменить источники на источники информации
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
+
# Добавить категории, см. также
## Источники информации
+
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
## Добавить см. также
+
# Источники информации
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
+
# Добавить см. также
## Добавить см. также
+
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]</li>
# '''!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
+
# Добавить см. также
## Оформить правильно англоязычные термины
+
<li> '''!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
## Написать более подробное и понятное доказательство
+
# Оформить правильно англоязычные термины
## Заменить ссылки на источники информации
+
# Написать более подробное и понятное доказательство
## Добавить категории
+
# Заменить ссылки на источники информации
## Добавить см. также
+
# Добавить категории
# '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
+
# Добавить см. также
## Англоязычные термины оформить правильно
+
<li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
## Заменить дефисы на тире
+
# Англоязычные термины оформить правильно
## Заменить прим. на более адекватный аналог
+
# Заменить дефисы на тире
## Заменить источники на источники информации
+
# Заменить прим. на более адекватный аналог
## Добавить информацию по последнему замечанию из обсуждений
+
# Заменить источники на источники информации
## Добавить см. также
+
# Добавить информацию по последнему замечанию из обсуждений
# [[Неразрешимость исчисления предикатов первого порядка]]
+
# Добавить см. также
## Добавить см. также
+
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
## Заменить ссылки на источники информации
+
# Добавить см. также
# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
+
# Заменить ссылки на источники информации
## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
+
<li> '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] </li>
# '''!!!''' [[Теорема Райса-Шапиро]]
+
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
## Англоязычные термины
+
<li> '''!!!''' [[Теорема Райса-Шапиро]] </li>
## Отформатировать псевдокоды
+
# Англоязычные термины
## Дать более формальное и понятное определение образца
+
# Отформатировать псевдокоды
## Разбить доказательство на две части, чтобы это было видно
+
# Дать более формальное и понятное определение образца
## Написать строгую формулировку теоремы
+
# Разбить доказательство на две части, чтобы это было видно
## "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие
+
# Написать строгую формулировку теоремы
## Лучше явно написать разрешитель для K
+
# "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие
## "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
+
# Лучше явно написать разрешитель для K
## Добавить категории, см. также
+
# "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
## Заменить литературу на источники информации
+
# Добавить категории, см. также
 +
# Заменить литературу на источники информации
 +
</ol>

Версия 14:17, 23 декабря 2014

Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе

1. Автоматы и регулярные языки

  1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
  2. Регулярные языки: два определения и их эквивалентность
    1. Англоязычные термины
  3. fixed Детерминированные конечные автоматы
    1. Английские термины
    2. Добавить ссылку на факт про эквивалентность автоматных и регулярных
    3. Англоязычные источники (хотя бы википедия)
    4. Добавить про изоморфизм автоматов вместе с алгоритмом
  4. fixed Прямое произведение ДКА
    1. Написать, как построить автомат для пересечения языков (с картинками)
    2. Добавить фактов про прямое произведение (задание 4.2.14 из ХМУ)
    3. Источники информации, см. также
  5. fixed Недетерминированные конечные автоматы
    1. Английские термины
    2. Отрефакторить псевдокод
    3. Источники информации
  6. взяли Построение по НКА эквивалентного ДКА, алгоритм Томпсона
    1. Отрефакторить псевдокод
    2. Добавить ссылки, см. также
    3. Исправить tex в знаках неравенств
    4. Какой-то абсолютно нечитабельный конспект. Словесное описание не помешало бы в начале
    5. Можно добавить простое альтернативное доказательство
  7. Автоматы с eps-переходами. Eps-замыкание
    1. Добавить источники информации, см. также
    2. Написать, где используется алгоритм eps-замыкания
  8. Теорема Клини (совпадение классов автоматных и регулярных языков)
    1. Добавить ссылок
  9. !!! Решение уравнений в регулярных выражениях
    1. Исправить неясный переход во второй части утверждения (да и вообще лучше доказательство поясней написать)
    2. Добавить ссылки
    3. Добавить ещё что-нибудь про то, где используются такие системы (кроме теоремы Клини)
  10. !!! Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
    1. Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини
  11. !!! Замкнутость регулярных языков относительно различных операций
    1. Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
  12. взяли Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
    1. Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
    2. Оформить нормально источники информации
    3. Исправить багу с примечаниями
    4. Англоязычные термины
  13. Интерпретация булевых формул с кванторами как игр для двух игроков
    вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
  14. !!! Доказательство нерегулярности языков: лемма о разрастании
    1. Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
    2. Доказательство леммы о накачке в общем виде
  15. fixed Эквивалентность состояний ДКА
    1. Добавить ссылок
    2. Добавить алгоритм проверки на эквивалентность не через минимизацию
    3. Добавить см. также, источники информации (если есть)
  16. fixed Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
    1. Структурно написать алгоритм
    2. Таблички оформить прилично
    3. Добавить ссылок
  17. взяли Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
    1. Отформатировать псевдокоды — там путается Tex и \mathtt, выглядит иногда не очень красиво
    2. Пояснить подробней "очевидные" факты
    3. Исправить знаки неравенств
    4. Сделать пары угловыми скобками
    5. Обернуть while в тексте в \mathrm
    6. Заменить литературу на источники информации
    7. Добавить более простой алгоритм через hashset'ы и hashmap'ы (по возможности)
    8. Исправить ошибки в конспекте
  18. fixed Контексты и синтаксические моноиды
    1. Добавить примеры контекстов
    2. Добавить правку про <state> \cdot <word> из обсуждений
    3. Картинки (автомата правых контекстов хотя бы)
    4. Кривое начало рассуждения в лемме о конечности двухсторонних контекстов
    5. Да и вообще всё рассуждение какое-то сумбурное и нечёткое — переписать

2. Контекстно-свободные грамматики

  1. Формальные грамматики
    1. Пояснить пример контекстно-зависимой грамматики
    2. Можно ещё примеров различных интересных грамматик добавить
  2. fixed Иерархия Хомского формальных грамматик
    1. добавить англоязычные термины
    2. добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
    3. интервики, ссылка на автоматные граммматики, например, которые есть на вики
    4. на машину Тьюринга можно внутреннюю ссылку сделать
    5. Ссылку на вики заменить на ссылку примечанием
    6. Добавить интервики на другие факты (добавить См. также)
    7. Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)
  3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
    1. Добавить источники информации, ссылок, интервики (на Иерархию)
  4. fixed Правоконтекстные грамматики, эквивалентность автоматам
    1. Англоязычные термины
    2. Источник бесполезен без конкретного указания, где искать
    3. Добавить интервики
  5. fixed Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
    1. нормально оформить уже существующий источник
    2. добавить англоязычные термины
    3. интервики
    4. Симольные скобки взять в tex
    5. а еще тут стрелки одинаковые и в правилах (надо [math]\to[/math]) и в выводе (надо [math]\Rightarrow[/math])
    6. пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
    7. Добавить заголовков
    8. Перерисовать картинку
  6. !!! Замкнутость КС-языков относительно различных операций
    1. Пропущен - в КС-языках
    2. Точку в конкатенации лучше опустить
    3. Half некрасивый, c маленькой буквы его
    4. Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
    5. Добавить примеры других грамматик
    6. Добавить ссылок, см. также
  7. !!! Регулярная аппроксимация КС-языков
    1. Добавить док-во леммы
    2. Отформатировать псевдокод
    3. Tex правильно оформить
    4. Описание перед псевдокодом перенести
    5. Картинки убого расположены
    6. "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
    7. Расшифровать RTN (то же с MT)
    8. Источники информации нормально оформить
  8. взяли Удаление бесполезных символов из грамматики
    1. Англоязычных термины нормально оформить
    2. Добавить ссылок
    3. Добавить интервики
    4. Грамматики оформлены криво
    5. Написать, что такое [math] | \Gamma | [/math]
    6. Написать, откуда берутся такие асимптотики, и как добавить очередь
    7. Аналогично про обход в глубину
    8. Ссылку на НФХ перенести в источники информации
    9. Алгоритмы оформить отдельным подзаголовком
  9. fixed Удаление длинных правил из грамматики
    1. Добавить источники информации
    2. Подробней расписать время работы
    3. Лишняя запятая в алгоритме после многоточия
  10. !!! Удаление eps-правил из грамматики
    1. Англоязычных термины нормально оформить
    2. Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже — реструктуризовать конспект
    3. Грамматику G заменить на [math] \Gamma [/math]
    4. Ссылку на НФХ перенести в источники информации
    5. Написать, почему при удалении длинных правил асимптотика будет линейной
    6. Грамматики криво оформлены
    7. Пояснить использование очереди
    8. Пропущены дефисы после КС местами
  11. Удаление цепных правил из грамматики
    1. Англоязычные термины оформить нормально
    2. Провести в алгоритме аналогию с транзитивным замыканием
    3. Грамматика криво криво оформлена
    4. Расписать асимптотику алгоритма
    5. Ссылку на НФХ перенести в источники информации
  12. взяли Нормальная форма Хомского
    1. Англоязычные термины хорошо оформить
    2. Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
    3. Константы взять в Tex
    4. Пример грамматики криво оформлен
    5. Ссылку на НФХ перенести в источники информации
    6. Заменить знаки неравенств в Tex
  13. !!! Устранение левой рекурсии
    1. Англоязычные термины оформить правильно
    2. Кинуть интервики на методы нисходящего разбора (или см. также)
    3. Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
    4. Отформатировать псевдокод
    5. Знаки неравенств заменить
    6. Источники информации нормально оформить
  14. !!!!! Приведение грамматики к ослабленной нормальной форме Грейбах
    1. написать, для чего она нужна
    2. Какая асимптотика алгоритма приведения?
    3. Добавить источники информации
    4. Добавить примеры
    5. Англоязычные термины нормально оформить
    6. Отформатировать псевдокод
  15. fixed Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
    1. Аккуратно помёрджить с аналогичным конспектом первого курса
  16. !!! Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
    1. Расписать подробней и формальней
    2. А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
    3. И желательно расписать динамики через полуинтервалы, а не отрезки
  17. !!! Алгоритм Эрли
    1. Отформатировать псевдокод
    2. Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
    3. Доказательство плохо отформатировано
    4. Оформить красиво источники информации
  18. !!! Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
    1. Отформатировать псевдокод
    2. Грамматику G заменить на \Gamma
    3. Перенести описание алгоритма перед псевдокодом
    4. Хотелось бы адекватные доказательства читать (см. обсуждения)
  19. !!! Лемма о разрастании для КС-грамматик
    1. Добавить пример не КС-языка, который удовлетворяют условию леммы
    2. Источники нормально оформить
    3. Добавить см. также на варианты леммы
  20. Лемма Огдена
    1. Источники информации добавить
    2. !!! Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы
  21. Существенно неоднозначные языки
    1. Англоязычные термины оформить правильно
    2. Ссылки из См. также перенести в источники информации
  22. Автоматы с магазинной памятью
    1. Картинки увеличить
  23. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
    1. Добавить источники информации
  24. !!! Совпадение множества языков МП-автоматов и контекстно-свободных языков
    1. Ссылки и литературу оформить правильно
    2. Оформить доказательство нормально, расписать подробно алгоритм
  25. Детерминированные автоматы с магазинной памятью
    1. В пример добавить язык автомата
    2. Англоязычные термины
  26. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  27. !!!!! Нормальная форма ДМП-автомата
    1. Написать!
  28. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
    1. Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?
    2. Добавить источники информации

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

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

  1. !!! Разрешимые (рекурсивные) языки
    1. Оформить правильно англоязычные термины
    2. Отформатировать псевдокод
    3. Перенести сюда определение вычислимой функции
    4. Добавить определение разрешимого языка в терминах вычислимой функции
    5. Заменить источники на источники информации
    6. Обернуть if в доказательстве неразрешимого языка в \mathrm
    7. Ещё примеров разрешимых языков (желательно не очень тривиальных)
  2. !!! Перечислимые языки
    1. Оформить правильно англоязычные термины
    2. Поправить чуть определение полуразрешимого языка
    3. Отформатировать псевдокоды
    4. Оформить правильно в обе стороны доказательство теоремы
    5. Заменить источники на источники информации
    6. Добавить примеры перечислимых и коперечеслимых языков
  3. Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
    1. Чуть-чуть код форматнуть
    2. Заменить литературу на источники информации
  4. Вычислимые функции
    1. Заменить источники на источники информации
    2. Определения вычислимой функции перенести в конспект Разрешимых языков
    3. Переименовать конспект и чуть-чуть реструктуризовать
  5. Вычислимые числа
    1. Правильно оформить англоязычные термины
    2. Пояснить a(eps) в определении
    3. Единообразно оформить множество рациональных чисел
    4. Все переменные и константы занести в Tex
    5. Ссылки заменить на источники информации
    6. Увеличить дроби
  6. Универсальная функция
    1. Англоязычные термины правильно оформить
    2. Оформить правильно источники информации
    3. Заменить дефисы на тире
  7. взяли Свойства перечислимых языков. Теорема Успенского-Райса
    1. англоязычные термины
    2. классы языков в mathrm
    3. заголовки верхнего уровня в ==, а не =
    4. категорию проставить
    5. Добавить источники информации
    6. Заменить в множестве | на \mid
    7. Отформатировать псевдокод
  8. !!! Неотделимые множества
    1. английские источиники и термины
    2. нормально оформить уже существующий источник
    3. написать, зачем оно может пригодиться
    4. Добавить категории
    5. Интервики
  9. !!! Иммунные и простые множества
    1. английские источиники и термины
    2. ссылки на вики
    3. а зачем оно нужно?
    4. Интервики
    5. Добавить категории
    6. Подробней расписать доказательства
    7. Ссылки на леммы внутри конспекта
  10. !!! Теорема о рекурсии
    1. дать ссылки на английские источники и термины
    2. Неформальное пояснение к теореме
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
  11. Busy beaver
    1. Правильно оформить англоязычные термины
    2. Отформатировать псевдокод
    3. Нормально оформить см. также, источники информации и вывод из теоремы

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

  1. !!! Машина Тьюринга
    1. Англоязычные термины
    2. Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
    3. Выделить машину Тьюринга жирным в определении
    4. Алгоритмы примеров красиво оформить
    5. Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
    6. Добавить в многоленточной, что эмулируется многодорожечной
    7. Рассказать весёлую историю про тезис Чёрча-Тьюринга
    8. Заменить ссылки на источники информации
    9. Добавить категории
  2. !!! Лямбда-исчисление (можно получить 10 баллов суммарно)
    1. Англоязычные термины
    2. Заменить "в разработке" на "nohate"
    3. Написать грамматику лямбд адекватно
    4. "Аппликация забирает себе всё," - ошибка - абстракция забирает
    5. Провести аналогию между связанными переменными и локальными переменными
    6. "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?
    7. Написать, что alpha-конверсия -- отношение эквивалентности
    8. beta-редукция не олицетворяет. Написать определение формально
    9. Написать подробней про нотацию Де Брёйна — что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней
    10. Провести аналогию между нумералами Чёрча и нумерацией Гёделя
    11. Убрать маркированный список из чисел, лучше просто отступ оставить
    12. "<<числу>>" — получше оформить
    13. Все константы и переменные взяь в Tex
    14. Добавить примеры выполнения операций сложения, умножения и вычитания
    15. "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" — пробел не отображается
    16. Добавить в неподвижной точке про Y-комбинатор
    17. Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном
    18. Оформить правильно источники информации, см. также
    19. Добавить категории
  3. !!! Примитивно рекурсивные функции
    1. названия функций надо в \mathrm
    2. Помёрджить с конспектом математической логики Рекурсивные функции, представимость в формальной арифметике
  4. !!! Частично рекурсивные функции
    1. См. замечания в обсуждениях
    2. англоязычные термины
    3. Дефис заменить на тире
    4. "функция g(x_1,\ldots,x_k) = минимальное y" — плохо, когда смешиваются формулы с текстом
    5. Заменить знаки неравенств
    6. "неразрешимость проврк," — опечатки
    7. Оформить правильно источники информации
    8. Добавить категории
  5. Стековые машины, эквивалентность двухстековой машины МТ
    1. Интервики
    2. Разбить доказательство на абзацы для читабельности
    3. Добавить категории
    4. Правильно оформить источники информации
  6. Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
    1. Оформить правильно источники информации
    2. Добавить категории
  7. Линейный клеточный автомат, эквивалентность МТ
    1. Англоязычные термины правильно оформить
    2. Переменные взять в Tex
    3. Добавить категории
    4. Оформить правильно источники информации
  8. Возможность порождения формальной грамматикой произвольного перечислимого языка
    1. внутренние ссылки
    2. категории
    3. Добавить см. также и источники информации

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

  1. !!! m-сводимость
    1. Англоязычные термины правильно оформить
    2. Добавить примеры m-сведения задач
    3. Заменить знаки неравенств
    4. Добавить категории
    5. Ссылку на ПСП оформить правильно
    6. Переменные и константы взять в Tex
  2. !!! Проблема соответствий Поста
    1. Англоязычные термины правильно оформить
    2. Заменить дефисы на тире
    3. Заменить знаки неравенств
    4. Все переменные и константы взять в Tex
    5. Добавить примеров решения задач ПСП
    6. Отфомартировать псевдокод
    7. Добавить больше подзаголовков нижнего уровня
    8. Больше интервики
    9. Заменить источники на источники информации
    10. Добавить категории, см. также
  3. Однозначность КС-грамматики
    1. Источники информации
    2. Добавить см. также
  4. Однозначность КС-грамматики
    1. Добавить см. также
  5. !!! Задача о замощении полимино
    1. Оформить правильно англоязычные термины
    2. Написать более подробное и понятное доказательство
    3. Заменить ссылки на источники информации
    4. Добавить категории
    5. Добавить см. также
  6. !!! Задача о выводе в полусистеме Туэ
    1. Англоязычные термины оформить правильно
    2. Заменить дефисы на тире
    3. Заменить прим. на более адекватный аналог
    4. Заменить источники на источники информации
    5. Добавить информацию по последнему замечанию из обсуждений
    6. Добавить см. также
  7. Неразрешимость исчисления предикатов первого порядка
    1. Добавить см. также
    2. Заменить ссылки на источники информации
  8. !!! Неразрешимость проблемы существования решения диофантова уравления в целых числах
    1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
  9. !!! Теорема Райса-Шапиро
    1. Англоязычные термины
    2. Отформатировать псевдокоды
    3. Дать более формальное и понятное определение образца
    4. Разбить доказательство на две части, чтобы это было видно
    5. Написать строгую формулировку теоремы
    6. "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
    7. Лучше явно написать разрешитель для K
    8. "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
    9. Добавить категории, см. также
    10. Заменить литературу на источники информации