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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Минимизация ДКА)
м (→‎Опровержение контекстно-свободности языка)
 
(не показано 148 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
=== Регулярные языки и ДКА ===
 
=== Регулярные языки и ДКА ===
 
<ol>
 
<ol>
−
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] (0.5) </li>
+
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li>
−
<li> [[Регулярные языки: два определения и их эквивалентность]] (0.5) </li>
+
<li> [[Регулярные языки: два определения и их эквивалентность]] </li>
−
# Англоязычные термины
+
<li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li>
−
# Ссылки заменить на источники информации
+
# Оформить красиво табличку
−
# Добавить См. также на ДКА
+
# Оформить подробней и красивей способы представления
−
<li> [[Детерминированные конечные автоматы]] </li>
 
 
<li> [[Прямое произведение ДКА]] </li>
 
<li> [[Прямое произведение ДКА]] </li>
 
</ol>
 
</ol>
Строка 17: Строка 16:
 
<li value="5"> [[Недетерминированные конечные автоматы]] </li>
 
<li value="5"> [[Недетерминированные конечные автоматы]] </li>
 
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>
 
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>
−
<li> [[Автоматы с eps-переходами. Eps-замыкание]] (1) </li>
+
<li> [[Автоматы с eps-переходами. Eps-замыкание]] </li>
−
# Англоязычные термины правильно
+
<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] </li>
−
# Добавить источники информации, см. также
+
<li> '''fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
−
# Написать, где используется алгоритм eps-замыкания
 
−
# Пофиксить знаки неравенств
 
−
# Определение жирным
 
−
# Многоточия на \ldots
 
−
<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] (0.5) </li>
 
−
# Добавить ссылок
 
−
# Поправить форматирование конспекта
 
−
<li> '''взяли''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
 
 
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
 
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
 
# Неплохо бы добавить ссылку на источник доказательства
 
# Неплохо бы добавить ссылку на источник доказательства
 +
# Исправить форматирование
 
</ol>
 
</ol>
  
Строка 35: Строка 27:
 
<ol>
 
<ol>
 
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
 
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
−
<li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] </li>
+
<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li>
−
<li> [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] </li>
+
# Оформить таблички покрасивей и marked на что-нибудь заменить
−
<li> '''взяли''' [[Алгоритм Бржозовского]] (5) </li>
+
# Сделать О-красивое
 +
<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li>
 +
# Отформатировать комментарии и добавить их побольше
 +
# Оформить правильно декларации функций
 +
# Отформатировать по правилам
 +
<li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li>
 
# Добавить доказательство
 
# Добавить доказательство
 
</ol>
 
</ol>
Строка 43: Строка 40:
 
=== Свойства конечных автоматов ===
 
=== Свойства конечных автоматов ===
 
<ol>
 
<ol>
−
<li value="14"> '''взяли''' [[Доказательство нерегулярности языков: лемма о разрастании]] (5) </li>
+
<li value="14"> '''fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </li>
 
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
 
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
 
# Доказательство леммы о накачке в общем виде
 
# Доказательство леммы о накачке в общем виде
−
<li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>
+
# Отформатировать по правилам
 +
<li> ''fixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>
 
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
 
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
 
<li> [[Решение уравнений в регулярных выражениях]] </li>
 
<li> [[Решение уравнений в регулярных выражениях]] </li>
−
<li> '''!!!''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
+
<li> '''fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
 
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
 
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
−
<li> '''взяли''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
+
<li> '''fixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
 
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
 
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
 
# Оформить нормально источники информации
 
# Оформить нормально источники информации
 
# Исправить багу с примечаниями
 
# Исправить багу с примечаниями
 
# Англоязычные термины
 
# Англоязычные термины
−
<li> [[Контексты и синтаксические моноиды]] </li>
+
<li> ''fixed'' [[Контексты и синтаксические моноиды]] (1) </li>
 +
# Оформить примеры красиво
 +
# Оформить красиво двусторонние доказательства
 +
# Отформатировать по правилам
 
</ol>
 
</ol>
  
 
=== Другие автоматы ===
 
=== Другие автоматы ===
 
<ol>
 
<ol>
−
<li value="20"> '''!!!''' [[Локальные автоматы]] (5) </li>
+
<li value="20"> '''fixed''' [[Локальные автоматы]] (5) </li>
 
# Где это нужно и зачем применяется
 
# Где это нужно и зачем применяется
 
<li> [[Двусторонний детерминированный конечный автомат]] </li>
 
<li> [[Двусторонний детерминированный конечный автомат]] </li>
 
<li> [[Квантовые конечные автоматы]] </li>
 
<li> [[Квантовые конечные автоматы]] </li>
−
<li> '''!!!''' [[Автоматы Мура и Мили]] (5) </li>
+
<li> '''fixed''' [[Автоматы Мура и Мили]] (5) </li>
 
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
 
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
 
</ol>
 
</ol>
Строка 72: Строка 73:
 
=== Базовые понятия о грамматиках ===
 
=== Базовые понятия о грамматиках ===
 
<ol>
 
<ol>
−
<li value="1"> '''взяли''' [[Формальные грамматики]] (5) </li>
+
<li value="1"> '''fixed''' [[Формальные грамматики]] (5) </li>
 
# Пояснить пример контекстно-зависимой грамматики
 
# Пояснить пример контекстно-зависимой грамматики
 
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
 
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
Строка 87: Строка 88:
 
# Почистить обсуждения
 
# Почистить обсуждения
 
<li> [[Иерархия Хомского формальных грамматик]] </li>
 
<li> [[Иерархия Хомского формальных грамматик]] </li>
−
<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] (0.5) </li>
+
<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] </li>
−
# Добавить источники информации, ссылок, интервики (на Иерархию)
 
−
# Категория
 
−
# Почистить обсуждения
 
−
# Знаки неравенств
 
 
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
 
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
−
<li> [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] </li>
+
<li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li>
−
<li> '''!!!''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
+
# Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
 +
<li> '''fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
 
# Пропущен - в КС-языках
 
# Пропущен - в КС-языках
 
# Точку в конкатенации лучше опустить
 
# Точку в конкатенации лучше опустить
Строка 101: Строка 99:
 
# Добавить примеры других грамматик
 
# Добавить примеры других грамматик
 
# Добавить ссылок, см. также
 
# Добавить ссылок, см. также
−
<li> '''!!!''' [[Регулярная аппроксимация КС-языков]] (7) </li>
+
<li> '''fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li>
 
# Добавить док-во леммы
 
# Добавить док-во леммы
 
# Отформатировать псевдокод
 
# Отформатировать псевдокод
Строка 115: Строка 113:
 
=== Нормальные формы КС-грамматик ===
 
=== Нормальные формы КС-грамматик ===
 
<ol>
 
<ol>
−
<li value="8"> '''!!!''' [[Удаление бесполезных символов из грамматики]] (6) </li>
+
<li value="8"> '''fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li>
 
# Англоязычных термины нормально оформить
 
# Англоязычных термины нормально оформить
 
# Добавить ссылок
 
# Добавить ссылок
Строка 127: Строка 125:
 
# Категория
 
# Категория
 
<li> [[Удаление длинных правил из грамматики]] </li>
 
<li> [[Удаление длинных правил из грамматики]] </li>
−
<li> '''!!!''' [[Удаление eps-правил из грамматики]] (6) </li>
+
<li> [[Удаление eps-правил из грамматики]] </li>
−
# Англоязычных термины нормально оформить
+
<li> [[Удаление цепных правил из грамматики]] </li>
−
# Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект
+
<li> [[Нормальная форма Хомского]] </li>
−
# Грамматику G заменить на <tex> \Gamma </tex>
+
<li> [[Устранение левой рекурсии]] </li>
−
# Ссылку на НФХ перенести в источники информации
+
<li> '''fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
−
# Написать, почему при удалении длинных правил асимптотика будет линейной
 
−
# Грамматики криво оформлены
 
−
# Пояснить использование очереди
 
−
# Пропущены дефисы после КС местами
 
−
# Категория
 
−
<li> [[Удаление цепных правил из грамматики]] (3) </li>
 
−
# Англоязычные термины оформить нормально
 
−
# Провести в алгоритме аналогию с транзитивным замыканием
 
−
# Грамматика криво криво оформлена
 
−
# Расписать асимптотику алгоритма
 
−
# Ссылку на НФХ перенести в источники информации
 
−
# Категория
 
−
<li> '''!!!''' [[Нормальная форма Хомского]] (5) </li>
 
−
# Англоязычные термины хорошо оформить
 
−
# Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
 
−
# Константы взять в Tex
 
−
# Пример грамматики криво оформлен
 
−
# Ссылку на НФХ перенести в источники информации
 
−
# Заменить знаки неравенств в Tex
 
−
# Категория
 
−
<li> '''!!!''' [[Устранение левой рекурсии]] (5) </li>
 
−
# Англоязычные термины оформить правильно
 
−
# Кинуть интервики на методы нисходящего разбора (или см. также)
 
−
# Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
 
−
# Отформатировать псевдокод
 
−
# Знаки неравенств заменить
 
−
# Источники информации нормально оформить
 
−
# Категория
 
−
<li> '''!!!''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
 
 
# написать, для чего она нужна
 
# написать, для чего она нужна
 
# Какая асимптотика алгоритма приведения?
 
# Какая асимптотика алгоритма приведения?
Строка 168: Строка 137:
 
# Отформатировать псевдокод
 
# Отформатировать псевдокод
 
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)  
 
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)  
−
<li> [[Нормальная форма Куроды]] (0.5) </li>
+
<li> [[Нормальная форма Куроды]] </li>
−
# Заменить везде G на \Gamma
 
 
</ol>
 
</ol>
  
Строка 175: Строка 143:
 
<ol>
 
<ol>
 
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
 
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
−
<li> '''!!!''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (7) </li>
+
<li> '''взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (10) </li>
 
# Расписать подробней и формальней
 
# Расписать подробней и формальней
 
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
 
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
 
# И желательно расписать динамики через полуинтервалы, а не отрезки
 
# И желательно расписать динамики через полуинтервалы, а не отрезки
 
# Красиво всё оформить
 
# Красиво всё оформить
−
<li> '''!!!''' [[Алгоритм Эрли]] (7) </li>
+
<li> [[Алгоритм Эрли]] </li>
−
# Отформатировать псевдокод
+
<li> '''fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
−
# Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
 
−
# Доказательство плохо отформатировано
 
−
# Оформить красиво источники информации
 
−
<li> '''!!!''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
 
 
# Отформатировать псевдокод
 
# Отформатировать псевдокод
 
# Грамматику G заменить на \Gamma
 
# Грамматику G заменить на \Gamma
Строка 194: Строка 158:
 
=== Опровержение контекстно-свободности языка ===
 
=== Опровержение контекстно-свободности языка ===
 
<ol>
 
<ol>
−
<li value="20"> '''!!!''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
+
<li value="20"> '''fixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
 
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
 
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
 
# Источники нормально оформить
 
# Источники нормально оформить
 
# Добавить см. также на варианты леммы
 
# Добавить см. также на варианты леммы
 
# Категория
 
# Категория
−
<li> '''!!!''' [[Лемма Огдена]] (7) </li>
+
<li> '''fixed''' [[Лемма Огдена]] (10) </li>
 
# Источники информации добавить
 
# Источники информации добавить
−
# Добавить пример, удовлетворяющий не КС-языка, который удовлетворяет условию этой леммы
+
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы
−
# Категория
 
−
<li> [[Существенно неоднозначные языки]] (0.5) </li>
 
−
# Англоязычные термины оформить правильно
 
−
# Ссылки из См. также перенести в источники информации
 
 
# Категория
 
# Категория
 +
<li> [[Существенно неоднозначные языки]]</li>
 
</ol>
 
</ol>
  
 
=== МП-автоматы ===
 
=== МП-автоматы ===
 
<ol>
 
<ol>
−
<li value="23"> [[Автоматы с магазинной памятью]] (0.5) </li>
+
<li value="23"> ''fixed'' [[Автоматы с магазинной памятью]] (0.5) </li>
 
# Картинки увеличить
 
# Картинки увеличить
 
# Определение жирным
 
# Определение жирным
Строка 218: Строка 179:
 
# Источники информации, См. также
 
# Источники информации, См. также
 
# Категория
 
# Категория
−
<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] (0.5) </li>
+
<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] </li>
−
# Добавить источники информации
+
<li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] </li>
−
# Категория
+
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]] (0.5) </li>
−
<li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] (3) </li>
 
−
# Ссылки и литературу оформить правильно
 
−
# Оформить доказательство красиво
 
−
# Расписать подробней алгоритм
 
−
# Категория
 
−
<li> [[Детерминированные автоматы с магазинной памятью]] (0.5) </li>
 
 
# В пример добавить язык автомата
 
# В пример добавить язык автомата
 
# Англоязычные термины
 
# Англоязычные термины
 
# Категория
 
# Категория
−
<li> [[Детерминированные автоматы с магазинной памятью, до пуск по пустому стеку]] (0.5) </li>
+
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] (0.5) </li>
 
# Категория
 
# Категория
 
# Палку заменить на \mid
 
# Палку заменить на \mid
 
# Источники информации
 
# Источники информации
−
<li> '''!!!''' [[Нормальная форма ДМП-автомата]] (10) </li>
+
<li> '''взяли''' [[Нормальная форма ДМП-автомата]] (10) </li>
 
# Написать!
 
# Написать!
−
<li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] (2) </li>
+
<li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] </li>
−
# Как-то в кучу всё в теореме. Лучше разделить совпадение по пустому стеку и по состоянию для ДМП и сравнить отдельно МП и ДМП
 
−
# Добавить источники информации
 
−
# Категория
 
−
# См. также
 
 
<li> [[ДМП-автоматы и неоднозначность]] </li>
 
<li> [[ДМП-автоматы и неоднозначность]] </li>
 
</ol>
 
</ol>
  
−
== 3. Теория вычислимости (проверяется) ==
+
== 3. Теория вычислимости ==
 
=== Разрешимые и перечислимые языки ===
 
=== Разрешимые и перечислимые языки ===
−
# '''fixed''' [[Разрешимые (рекурсивные) языки]]
+
# [[Разрешимые (рекурсивные) языки]]
−
## Оформить правильно англоязычные термины
+
# ''fixed'' [[Перечислимые языки]] (2)
−
## Отформатировать псевдокод
+
## Добавить содержательный пример коперечислимого языка
−
## Перенести сюда определение вычислимой функции
+
# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (2.5)
−
## Добавить определение разрешимого языка в терминах вычислимой функции
+
## Убрать лишние знаки препинания из списков в теоремах
−
## Заменить источники на источники информации
 
−
## Обернуть if в доказательстве неразрешимого языка в \mathrm
 
−
## Ещё примеров разрешимых языков (желательно не очень тривиальных)
 
−
# '''!!!''' [[Перечислимые языки]]
 
−
## Оформить правильно англоязычные термины
 
−
## Поправить чуть определение полуразрешимого языка
 
−
## Отформатировать псевдокоды
 
−
## Оформить правильно в обе стороны доказательство теоремы
 
−
## Заменить источники на источники информации
 
−
## Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков
 
−
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
 
−
## Чуть-чуть код форматнуть
 
 
## Заменить литературу на источники информации
 
## Заменить литературу на источники информации
 +
## Категории
 +
## Отформатировать по правилам
 
# [[Вычислимые функции]]
 
# [[Вычислимые функции]]
−
## Заменить источники на источники информации
+
# ''fixed'' [[Вычислимые числа]] (2)
−
## Определения вычислимой функции перенести в конспект Разрешимых языков
 
−
## Переименовать конспект и чуть-чуть реструктуризовать
 
−
# [[Вычислимые числа]]
 
 
## Правильно оформить англоязычные термины
 
## Правильно оформить англоязычные термины
 
## Пояснить a(eps) в определении
 
## Пояснить a(eps) в определении
Строка 275: Строка 213:
 
## Ссылки заменить на источники информации
 
## Ссылки заменить на источники информации
 
## Увеличить дроби
 
## Увеличить дроби
−
# [[Универсальная функция]]  
+
## Пояснить подробней мутные места
 +
# ''fixed'' [[Универсальная функция]] (1)
 
## Англоязычные термины правильно оформить  
 
## Англоязычные термины правильно оформить  
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
 
## Заменить дефисы на тире
 
## Заменить дефисы на тире
−
# '''fixed''' [[Свойства перечислимых языков. Теорема Успенского-Райса]]
+
## Пояснить нотацию про U(n, x) и U_n(x)
−
## англоязычные термины
+
## Заголовки внутри конспекта поправить
−
## классы языков в mathrm
+
# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1)
−
## заголовки верхнего уровня в ==, а не =
+
## Почему языком L_g(i,x) будет X? Как i связано с X?
−
## категорию проставить
+
## И вообще доказательство можно сделать чуть менее мутным :)
−
## Добавить источники информации
+
# [[Неотделимые множества]]
−
## Заменить в множестве | на \mid
+
# '''fixed''' [[Иммунные и простые множества]] (7)
−
## Отформатировать псевдокод
 
−
# '''fixed''' [[Неотделимые множества]]
 
−
## английские источиники и термины
 
−
## нормально оформить уже существующий источник
 
−
## написать, зачем оно может пригодиться
 
−
## Добавить категории
 
−
## Интервики
 
−
# '''!!!''' [[Иммунные и простые множества]]
 
 
## английские источиники и термины
 
## английские источиники и термины
 
## ссылки на вики
 
## ссылки на вики
Строка 301: Строка 232:
 
## Подробней расписать доказательства
 
## Подробней расписать доказательства
 
## Ссылки на леммы внутри конспекта
 
## Ссылки на леммы внутри конспекта
−
# '''!!!''' [[Теорема о рекурсии]]
+
# '''fixed''' [[Теорема о рекурсии]] (8)
 
## дать ссылки на английские источники и термины  
 
## дать ссылки на английские источники и термины  
 
## Неформальное пояснение к теореме
 
## Неформальное пояснение к теореме
 
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
 
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
 +
# [[Квайны]]
 
# [[Busy beaver]]
 
# [[Busy beaver]]
−
## Правильно оформить англоязычные термины
+
# [[Колмогоровская сложность]]
−
## Отформатировать псевдокод
 
−
## Нормально оформить см. также, источники информации и вывод из теоремы
 
  
 
=== Вычислительные формализмы ===
 
=== Вычислительные формализмы ===
 
<ol>
 
<ol>
−
<li value="12">'''!!!''' [[Машина Тьюринга]] </li>
+
<li value="14">[[Машина Тьюринга]] </li>
−
# Англоязычные термины
+
<li> [[Лямбда-исчисление]]</li>
−
# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
+
<li> '''fixed''' [[Примитивно рекурсивные функции]] (10) </li>
−
# Выделить машину Тьюринга жирным в определении
 
−
# Алгоритмы примеров красиво оформить
 
−
# Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
 
−
# Добавить в многоленточной, что эмулируется многодорожечной
 
−
# Рассказать весёлую историю про тезис Чёрча-Тьюринга
 
−
# Заменить ссылки на источники информации
 
−
# Добавить категории
 
−
<li> '''fixed''' [[Лямбда-исчисление]]</li>
 
−
# Англоязычные термины
 
−
# Заменить "в разработке" на "nohate"
 
−
# Написать грамматику лямбд адекватно
 
−
# "Аппликация забирает себе всё," - ошибка - абстракция забирает
 
−
# Провести аналогию между связанными переменными и локальными переменными
 
−
# "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?
 
−
# Написать, что alpha-конверсия -- отношение эквивалентности
 
−
# beta-редукция не олицетворяет. Написать определение формально
 
−
# Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней
 
−
# Провести аналогию между нумералами Чёрча и нумерацией Гёделя
 
−
# Убрать маркированный список из чисел, лучше просто отступ оставить
 
−
# "<<числу>>" {{---}} получше оформить
 
−
# Все константы и переменные взять в Tex
 
−
# Добавить примеры выполнения операций сложения, умножения и вычитания
 
−
# "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается
 
−
# Добавить в неподвижной точке про Y-комбинатор
 
−
# Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном
 
−
# Оформить правильно источники информации, см. также
 
−
# Добавить категории
 
−
<li> '''!!!''' [[Примитивно рекурсивные функции]] </li>
 
 
# названия функций надо в \mathrm
 
# названия функций надо в \mathrm
 
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
 
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
−
<li> '''взяли''' [[Частично рекурсивные функции]] </li>
+
<li> ''fixed'' [[Частично рекурсивные функции]] (2) </li>
−
# См. замечания в обсуждениях
+
# Замечание про взаимную рекурсию в обсуждениях
−
# англоязычные термины
+
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
−
# Дефис заменить на тире
 
−
# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом
 
−
# Заменить знаки неравенств
 
−
# "неразрешимость проврк," {{---}} опечатки
 
−
# Оформить правильно источники информации
 
−
# Добавить категории
 
−
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li>
 
−
# Интервики
 
−
# Разбить доказательство на абзацы для читабельности
 
−
# Добавить категории
 
−
# Правильно оформить источники информации
 
 
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
 
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
−
# Оформить правильно источники информации
 
−
# Добавить категории
 
 
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
 
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
−
# Англоязычные термины правильно оформить
 
−
# Переменные взять в Tex
 
−
# Добавить категории
 
−
# Оформить правильно источники информации
 
 
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
 
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
−
# внутренние ссылки
+
<li> [[Линейный ограниченный автомат]]</li>
−
# категории
+
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
−
# Добавить см. также и источники информации
 
 
</ol>
 
</ol>
  
 
=== Примеры неразрешимых задач ===
 
=== Примеры неразрешимых задач ===
 
<ol>
 
<ol>
−
<li value="20"> '''взяли''' [[m-сводимость]] </li>
+
<li value="24"> ''fixed'' [[m-сводимость]] (3) </li>
 
# Англоязычные термины правильно оформить
 
# Англоязычные термины правильно оформить
 
# Добавить примеры m-сведения задач
 
# Добавить примеры m-сведения задач
Строка 383: Строка 267:
 
# Ссылку на ПСП оформить правильно
 
# Ссылку на ПСП оформить правильно
 
# Переменные и константы взять в Tex
 
# Переменные и константы взять в Tex
−
<li> '''fixed''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
+
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
−
# Англоязычные термины правильно оформить
 
−
# Заменить дефисы на тире
 
−
# Заменить знаки неравенств
 
−
# Все переменные и константы взять в Tex
 
−
# Добавить примеров решения задач ПСП
 
−
# Отфомартировать псевдокод
 
−
# Добавить больше подзаголовков нижнего уровня
 
−
# Больше интервики
 
−
# Заменить источники на источники информации
 
−
# Добавить категории, см. также
 
 
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
 
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
−
# Источники информации
+
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
−
# Добавить см. также
+
<li> '''fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
−
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]</li>
 
−
# Добавить см. также
 
−
<li> '''!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
 
 
# Оформить правильно англоязычные термины
 
# Оформить правильно англоязычные термины
 
# Написать более подробное и понятное доказательство
 
# Написать более подробное и понятное доказательство
Строка 405: Строка 276:
 
# Добавить категории
 
# Добавить категории
 
# Добавить см. также
 
# Добавить см. также
−
<li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
+
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
−
# Англоязычные термины оформить правильно
 
−
# Заменить дефисы на тире
 
−
# Заменить прим. на более адекватный аналог
 
−
# Заменить источники на источники информации
 
−
# Добавить информацию по последнему замечанию из обсуждений
 
−
# Добавить см. также
 
 
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
 
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
−
# Добавить см. также
+
<li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>
−
# Заменить ссылки на источники информации
 
−
<li> '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] </li>
 
 
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
 
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
−
<li> '''!!!''' [[Теорема Райса-Шапиро]] </li>
+
<li> [[Игра «Жизнь»]] </li>
 +
<li> [[Неразрешимость игры Braid]] </li>
 +
<li> '''fixed''' [[Теорема Райса-Шапиро]] (8) </li>
 
# Англоязычные термины
 
# Англоязычные термины
 
# Отформатировать псевдокоды
 
# Отформатировать псевдокоды

Текущая версия на 20:16, 18 января 2017

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

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

Регулярные языки и ДКА

  1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
  2. Регулярные языки: два определения и их эквивалентность
  3. fixed Детерминированные конечные автоматы (2)
    1. Оформить красиво табличку
    2. Оформить подробней и красивей способы представления
  4. Прямое произведение ДКА

НКА

  1. Недетерминированные конечные автоматы
  2. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  3. Автоматы с eps-переходами. Eps-замыкание
  4. Теорема Клини (совпадение классов автоматных и регулярных языков)
  5. fixed Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) (5)
    1. Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
    2. Неплохо бы добавить ссылку на источник доказательства
    3. Исправить форматирование

Минимизация ДКА

  1. Эквивалентность состояний ДКА
  2. fixed Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний (2)
    1. Оформить таблички покрасивей и marked на что-нибудь заменить
    2. Сделать О-красивое
  3. fixed Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) (2.5)
    1. Отформатировать комментарии и добавить их побольше
    2. Оформить правильно декларации функций
    3. Отформатировать по правилам
  4. fixed Алгоритм Бржозовского (5)
    1. Добавить доказательство

Свойства конечных автоматов

  1. fixed Доказательство нерегулярности языков: лемма о разрастании (6)
    1. Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
    2. Доказательство леммы о накачке в общем виде
    3. Отформатировать по правилам
  2. fixed Интерпретация булевых формул с кванторами как игр для двух игроков (1)
    • Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
  3. Решение уравнений в регулярных выражениях
  4. fixed Замкнутость регулярных языков относительно различных операций (6)
    1. Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
  5. fixed Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов) (5)
    1. Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
    2. Оформить нормально источники информации
    3. Исправить багу с примечаниями
    4. Англоязычные термины
  6. fixed Контексты и синтаксические моноиды (1)
    1. Оформить примеры красиво
    2. Оформить красиво двусторонние доказательства
    3. Отформатировать по правилам

Другие автоматы

  1. fixed Локальные автоматы (5)
    1. Где это нужно и зачем применяется
  2. Двусторонний детерминированный конечный автомат
  3. Квантовые конечные автоматы
  4. fixed Автоматы Мура и Мили (5)
    1. Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)

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

Базовые понятия о грамматиках

  1. fixed Формальные грамматики (5)
    1. Пояснить пример контекстно-зависимой грамматики
    2. Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
    3. Заменить многоточия на \ldots
    4. Оформить правильно источники инфрмации, добавить См. также
    5. Категория
    6. Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
    7. Примеры обозначений
    8. Вертикальную черту заменить на \mid
    9. В определениях скобки в Tex
    10. Интервики на рефлексивно-транзитивное замыкание
    11. Убрать ; из определения
    12. Выводы в примерах оформить красивей
    13. Почистить обсуждения
  2. Иерархия Хомского формальных грамматик
  3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
  4. Правоконтекстные грамматики, эквивалентность автоматам
  5. fixed Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора (1)
    1. Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
  6. fixed Замкнутость КС-языков относительно различных операций (5)
    1. Пропущен - в КС-языках
    2. Точку в конкатенации лучше опустить
    3. Half некрасивый, c маленькой буквы его
    4. Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
    5. Добавить примеры других грамматик
    6. Добавить ссылок, см. также
  7. fixed Регулярная аппроксимация КС-языков (7)
    1. Добавить док-во леммы
    2. Отформатировать псевдокод
    3. Tex правильно оформить
    4. Описание перед псевдокодом перенести
    5. Картинки убого расположены
    6. "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
    7. Расшифровать RTN (то же с MT)
    8. Источники информации нормально оформить
    9. См. обсуждения

Нормальные формы КС-грамматик

  1. fixed Удаление бесполезных символов из грамматики (6)
    1. Англоязычных термины нормально оформить
    2. Добавить ссылок
    3. Добавить интервики
    4. Грамматики оформлены криво
    5. Написать, что такое [math] | \Gamma | [/math]
    6. Написать, откуда берутся такие асимптотики, и как добавить очередь
    7. Аналогично про обход в глубину
    8. Ссылку на НФХ перенести в источники информации
    9. Алгоритмы оформить отдельным подзаголовком
    10. Категория
  2. Удаление длинных правил из грамматики
  3. Удаление eps-правил из грамматики
  4. Удаление цепных правил из грамматики
  5. Нормальная форма Хомского
  6. Устранение левой рекурсии
  7. fixed Приведение грамматики к ослабленной нормальной форме Грейбах (8)
    1. написать, для чего она нужна
    2. Какая асимптотика алгоритма приведения?
    3. Добавить источники информации
    4. Добавить примеры
    5. Англоязычные термины нормально оформить
    6. Отформатировать псевдокод
    7. Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
  8. Нормальная форма Куроды

Алгоритмы разбора

  1. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
  2. взяли Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики (10)
    1. Расписать подробней и формальней
    2. А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
    3. И желательно расписать динамики через полуинтервалы, а не отрезки
    4. Красиво всё оформить
  3. Алгоритм Эрли
  4. fixed Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики (5)
    1. Отформатировать псевдокод
    2. Грамматику G заменить на \Gamma
    3. Перенести описание алгоритма перед псевдокодом
    4. Хотелось бы адекватные доказательства читать (см. обсуждения)

Опровержение контекстно-свободности языка

  1. fixed Лемма о разрастании для КС-грамматик (6)
    1. Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
    2. Источники нормально оформить
    3. Добавить см. также на варианты леммы
    4. Категория
  2. fixed Лемма Огдена (10)
    1. Источники информации добавить
    2. Добавить пример не КС-языка, который удовлетворяет условию этой леммы
    3. Категория
  3. Существенно неоднозначные языки

МП-автоматы

  1. fixed Автоматы с магазинной памятью (0.5)
    1. Картинки увеличить
    2. Определение жирным
    3.  ; в определении заменить на ,
    4. Англоязычные термины правильно оформить, убрать дублирования
    5. Источники информации, См. также
    6. Категория
  2. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  3. Совпадение множества языков МП-автоматов и контекстно-свободных языков
  4. fixed Детерминированные автоматы с магазинной памятью (0.5)
    1. В пример добавить язык автомата
    2. Англоязычные термины
    3. Категория
  5. fixed Детерминированные автоматы с магазинной памятью, допуск по пустому стеку (0.5)
    1. Категория
    2. Палку заменить на \mid
    3. Источники информации
  6. взяли Нормальная форма ДМП-автомата (10)
    1. Написать!
  7. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
  8. ДМП-автоматы и неоднозначность

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

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

  1. Разрешимые (рекурсивные) языки
  2. fixed Перечислимые языки (2)
    1. Добавить содержательный пример коперечислимого языка
  3. fixed Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций (2.5)
    1. Убрать лишние знаки препинания из списков в теоремах
    2. Заменить литературу на источники информации
    3. Категории
    4. Отформатировать по правилам
  4. Вычислимые функции
  5. fixed Вычислимые числа (2)
    1. Правильно оформить англоязычные термины
    2. Пояснить a(eps) в определении
    3. Единообразно оформить множество рациональных чисел
    4. Все переменные и константы занести в Tex
    5. Ссылки заменить на источники информации
    6. Увеличить дроби
    7. Пояснить подробней мутные места
  6. fixed Универсальная функция (1)
    1. Англоязычные термины правильно оформить
    2. Оформить правильно источники информации
    3. Заменить дефисы на тире
    4. Пояснить нотацию про U(n, x) и U_n(x)
    5. Заголовки внутри конспекта поправить
  7. fixed Свойства перечислимых языков. Теорема Успенского-Райса (1)
    1. Почему языком L_g(i,x) будет X? Как i связано с X?
    2. И вообще доказательство можно сделать чуть менее мутным :)
  8. Неотделимые множества
  9. fixed Иммунные и простые множества (7)
    1. английские источиники и термины
    2. ссылки на вики
    3. а зачем оно нужно?
    4. Интервики
    5. Добавить категории
    6. Подробней расписать доказательства
    7. Ссылки на леммы внутри конспекта
  10. fixed Теорема о рекурсии (8)
    1. дать ссылки на английские источники и термины
    2. Неформальное пояснение к теореме
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
  11. Квайны
  12. Busy beaver
  13. Колмогоровская сложность

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

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

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

  1. fixed m-сводимость (3)
    1. Англоязычные термины правильно оформить
    2. Добавить примеры m-сведения задач
    3. Заменить знаки неравенств
    4. Добавить категории
    5. Ссылку на ПСП оформить правильно
    6. Переменные и константы взять в Tex
  2. Проблема соответствий Поста
  3. Однозначность КС-грамматики
  4. Неразрешимость задачи об эквивалентности КС-грамматик
  5. fixed Задача о замощении полимино (6)
    1. Оформить правильно англоязычные термины
    2. Написать более подробное и понятное доказательство
    3. Заменить ссылки на источники информации
    4. Добавить категории
    5. Добавить см. также
  6. Задача о выводе в полусистеме Туэ
  7. Неразрешимость исчисления предикатов первого порядка
  8. взяли Неразрешимость проблемы существования решения диофантова уравления в целых числах (10)
    1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
  9. Игра «Жизнь»
  10. Неразрешимость игры Braid
  11. fixed Теорема Райса-Шапиро (8)
    1. Англоязычные термины
    2. Отформатировать псевдокоды
    3. Дать более формальное и понятное определение образца
    4. Разбить доказательство на две части, чтобы это было видно
    5. Написать строгую формулировку теоремы
    6. "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
    7. Лучше явно написать разрешитель для K
    8. "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
    9. Добавить категории, см. также
    10. Заменить литературу на источники информации
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_5ому_терму&oldid=60030»