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

Материал из Викиконспекты
Перейти к: навигация, поиск
(1. Автоматы и регулярные языки)
м (Опровержение контекстно-свободности языка)
 
(не показано 214 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
 
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
__TOC__
+
 
 
== 1. Автоматы и регулярные языки ==
 
== 1. Автоматы и регулярные языки ==
# [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
+
=== Регулярные языки и ДКА ===
# [[Регулярные языки: два определения и их эквивалентность]]
+
<ol>
## Англоязычные термины
+
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li>
# [[Детерминированные конечные автоматы]]
+
<li> [[Регулярные языки: два определения и их эквивалентность]] </li>
## Английские термины
+
<li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li>
## Добавить ссылку на факт про эквивалентность автоматных и регулярных
+
# Оформить красиво табличку
## Англоязычные источники (хотя бы википедия)
+
# Оформить подробней и красивей способы представления
# '''fixed''' [[Прямое произведение ДКА]]
+
<li> [[Прямое произведение ДКА]] </li>
## Написать, как построить автомат для пересечения языков (с картинками)
+
</ol>
## Добавить фактов про прямое произведение (задание 4.2.14 из ХМУ)
+
 
## Источники информации, см. также
+
=== НКА ===
# [[Недетерминированные конечные автоматы]]
+
<ol>
## Английские термины
+
<li value="5"> [[Недетерминированные конечные автоматы]] </li>
## Отрефакторить псевдокод
+
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>
## Источники информации
+
<li> [[Автоматы с eps-переходами. Eps-замыкание]] </li>
# '''взяли''' [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
+
<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] </li>
## Отрефакторить псевдокод
+
<li> '''fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
## Добавить ссылки, см. также
+
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
## Исправить tex в знаках неравенств
+
# Неплохо бы добавить ссылку на источник доказательства
## Какой-то абсолютно нечитабельный конспект. Словесное описание не помешало бы в начале
+
# Исправить форматирование
## Можно добавить простое альтернативное доказательство
+
</ol>
# [[Автоматы с eps-переходами. Eps-замыкание]]
+
 
## Добавить источники информации, см. также
+
=== Минимизация ДКА ===
## Написать, где используется алгоритм eps-замыкания
+
<ol>
# [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
+
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
## Добавить ссылок
+
<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li>
# '''!!!''' [[Решение уравнений в регулярных выражениях]]
+
# Оформить таблички покрасивей и marked на что-нибудь заменить
## Исправить неясный переход во второй части утверждения (да и вообще лучше доказательство поясней написать)
+
# Сделать О-красивое
## Добавить ссылки
+
<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li>
## Добавить ещё что-нибудь про то, где используются такие системы (кроме теоремы Клини)
+
# Отформатировать комментарии и добавить их побольше
# '''!!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
+
# Оформить правильно декларации функций
## Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини
+
# Отформатировать по правилам
# '''!!!''' [[Замкнутость регулярных языков относительно различных операций]]
+
<li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li>
## Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
+
# Добавить доказательство
# '''!!!''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
+
</ol>
## Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
+
 
## Оформить нормально источники информации
+
=== Свойства конечных автоматов ===
## Исправить багу с примечаниями
+
<ol>
## Англоязычные термины
+
<li value="14"> '''fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </li>
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
+
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
+
# Доказательство леммы о накачке в общем виде
# '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
+
# Отформатировать по правилам
## Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
+
<li> ''fixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>
## Доказательство леммы о накачке в общем виде
+
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
# '''!!!''' [[Эквивалентность состояний ДКА]]
+
<li> [[Решение уравнений в регулярных выражениях]] </li>
## Добавить ссылок
+
<li> '''fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
## Добавить алгоритм проверки на эквивалентность не через минимизацию
+
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
# '''!!!''' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
+
<li> '''fixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
## Структурно написать алгоритм
+
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
## Таблички оформить прилично
+
# Оформить нормально источники информации
## Добавить ссылок
+
# Исправить багу с примечаниями
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
+
# Англоязычные термины
# '''!!!''' [[Контексты и синтаксические моноиды]]
+
<li> ''fixed'' [[Контексты и синтаксические моноиды]] (1) </li>
## Добавить примеры контекстов
+
# Оформить примеры красиво
## Добавить правку про <state> \cdot <word> из обсуждений
+
# Оформить красиво двусторонние доказательства
## Картинки (автомата правых контекстов хотя бы)
+
# Отформатировать по правилам
## Кривое начало рассуждения в лемме о конечности двухсторонних контекстов
+
</ol>
## Да и вообще всё рассуждение какое-то сумбурное и нечёткое {{---}} переписать
+
 
 +
=== Другие автоматы ===
 +
<ol>
 +
<li value="20"> '''fixed''' [[Локальные автоматы]] (5) </li>
 +
# Где это нужно и зачем применяется
 +
<li> [[Двусторонний детерминированный конечный автомат]] </li>
 +
<li> [[Квантовые конечные автоматы]] </li>
 +
<li> '''fixed''' [[Автоматы Мура и Мили]] (5) </li>
 +
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
 +
</ol>
  
 
== 2. Контекстно-свободные грамматики ==
 
== 2. Контекстно-свободные грамматики ==
# [[Формальные грамматики]]
+
=== Базовые понятия о грамматиках ===
## Пояснить пример контекстно-зависимой грамматики
+
<ol>
## Можно ещё примеров различных интересных грамматик добавить
+
<li value="1"> '''fixed''' [[Формальные грамматики]] (5) </li>
# '''!!!''' [[Иерархия Хомского формальных грамматик]]
+
# Пояснить пример контекстно-зависимой грамматики
## добавить англоязычные термины
+
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
+
# Заменить многоточия на \ldots
## интервики, ссылка на автоматные граммматики, например, которые есть на вики
+
# Оформить правильно источники инфрмации, добавить См. также
## на машину Тьюринга можно внутреннюю ссылку сделать
+
# Категория
## Ссылку на вики заменить на ссылку примечанием
+
# Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
## Добавить интервики на другие факты (добавить См. также)
+
# Примеры обозначений
## Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)
+
# Вертикальную черту заменить на \mid
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
+
# В определениях скобки в Tex
## Добавить источники информации, ссылок, интервики (на Иерархию)
+
# Интервики на рефлексивно-транзитивное замыкание
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
+
# Убрать ; из определения
## Англоязычные термины
+
# Выводы в примерах оформить красивей
## Источник бесполезен без конкретного указания, где искать
+
# Почистить обсуждения
## Добавить интервики
+
<li> [[Иерархия Хомского формальных грамматик]] </li>
# '''!!!''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
+
<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] </li>
## нормально оформить уже существующий источник
+
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
## добавить англоязычные термины
+
<li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li>
## интервики
+
# Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
## Симольные скобки взять в tex
+
<li> '''fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)
+
# Пропущен - в КС-языках
## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
+
# Точку в конкатенации лучше опустить
## Добавить заголовков
+
# Half некрасивый, c маленькой буквы его
## Перерисовать картинку
+
# Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
# '''!!!''' [[Замкнутость КС-языков относительно различных операций]]
+
# Добавить примеры других грамматик
## Пропущен - в КС-языках
+
# Добавить ссылок, см. также
## Точку в конкатенации лучше опустить
+
<li> '''fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li>
## Half некрасивый, c маленькой буквы его
+
# Добавить док-во леммы
## Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
+
# Отформатировать псевдокод
## Добавить примеры других грамматик
+
# Tex правильно оформить
## Добавить ссылок, см. также
+
# Описание перед псевдокодом перенести
# '''!!!''' [[Регулярная аппроксимация КС-языков]]
+
# Картинки убого расположены
## Добавить док-во леммы
+
# "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте
## Отформатировать псевдокод
+
# Расшифровать RTN (то же с MT)
## Tex правильно оформить
+
# Источники информации нормально оформить
## Описание перед псевдокодом перенести
+
# См. обсуждения
## Картинки убого расположены
+
</ol>
## "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте
+
 
## Расшифровать RTN (то же с MT)
+
=== Нормальные формы КС-грамматик ===
## Источники информации нормально оформить
+
<ol>
# '''!!!''' [[Удаление бесполезных символов из грамматики]]
+
<li value="8"> '''fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li>
## Англоязычных термины нормально оформить
+
# Англоязычных термины нормально оформить
## Добавить ссылок
+
# Добавить ссылок
## Добавить интервики
+
# Добавить интервики
## Грамматики оформлены криво
+
# Грамматики оформлены криво
## Написать, что такое <tex> | \Gamma | </tex>
+
# Написать, что такое <tex> | \Gamma | </tex>
## Написать, откуда берутся такие асимптотики, и как добавить очередь
+
# Написать, откуда берутся такие асимптотики, и как добавить очередь
## Аналогично про обход в глубину
+
# Аналогично про обход в глубину
## Ссылку на НФХ перенести в источники информации
+
# Ссылку на НФХ перенести в источники информации
## Алгоритмы оформить отдельным подзаголовком
+
# Алгоритмы оформить отдельным подзаголовком
# [[Удаление длинных правил из грамматики]]
+
# Категория
## Добавить источники информации
+
<li> [[Удаление длинных правил из грамматики]] </li>
## Подробней расписать время работы
+
<li> [[Удаление eps-правил из грамматики]] </li>
## Лишняя запятая в алгоритме после многоточия
+
<li> [[Удаление цепных правил из грамматики]] </li>
# '''!!!''' [[Удаление eps-правил из грамматики]]
+
<li> [[Нормальная форма Хомского]] </li>
## Англоязычных термины нормально оформить
+
<li> [[Устранение левой рекурсии]] </li>
## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект
+
<li> '''fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
## Грамматику G заменить на <tex> \Gamma </tex>
+
# написать, для чего она нужна
## Ссылку на НФХ перенести в источники информации
+
# Какая асимптотика алгоритма приведения?
## Написать, почему при удалении длинных правил асимптотика будет линейной
+
# Добавить источники информации
## Грамматики криво оформлены
+
# Добавить примеры
## Пояснить использование очереди
+
# Англоязычные термины нормально оформить
## Пропущены дефисы после КС местами
+
# Отформатировать псевдокод
# [[Удаление цепных правил из грамматики]]
+
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
## Англоязычные термины оформить нормально
+
<li> [[Нормальная форма Куроды]] </li>
## Провести в алгоритме аналогию с транзитивным замыканием
+
</ol>
## Грамматика криво криво оформлена
+
 
## Расписать асимптотику алгоритма
+
=== Алгоритмы разбора ===
## Ссылку на НФХ перенести в источники информации
+
<ol>
# '''!!!''' [[Нормальная форма Хомского]]
+
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
## Англоязычные термины хорошо оформить
+
<li> '''взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (10) </li>
## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
+
# Расписать подробней и формальней
## Константы взять в Tex
+
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
## Пример грамматики криво оформлен
+
# И желательно расписать динамики через полуинтервалы, а не отрезки
## Ссылку на НФХ перенести в источники информации
+
# Красиво всё оформить
## Заменить знаки неравенств в Tex
+
<li> [[Алгоритм Эрли]] </li>
# '''!!!''' [[Устранение левой рекурсии]]
+
<li> '''fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
## Англоязычные термины оформить правильно
+
# Отформатировать псевдокод
## Кинуть интервики на методы нисходящего разбора (или см. также)
+
# Грамматику G заменить на \Gamma
## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
+
# Перенести описание алгоритма перед псевдокодом
## Отформатировать псевдокод
+
# Хотелось бы адекватные доказательства читать (см. обсуждения)
## Знаки неравенств заменить
+
</ol>
## Источники информации нормально оформить
+
 
# '''!!!!!''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]]
+
=== Опровержение контекстно-свободности языка ===
## написать, для чего она нужна
+
<ol>
## Какая асимптотика алгоритма приведения?
+
<li value="20"> '''fixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
## Добавить источники информации
+
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
## Добавить примеры
+
# Источники нормально оформить
## Англоязычные термины нормально оформить
+
# Добавить см. также на варианты леммы
## Отформатировать псевдокод
+
# Категория
# '''!!!''' [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
+
<li> '''fixed''' [[Лемма Огдена]] (10) </li>
## Аккуратно помёрджить с аналогичным конспектом первого курса
+
# Источники информации добавить
# '''!!!''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
+
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы
## Расписать подробней и формальней
+
# Категория
# '''взяли''' [[Алгоритм Эрли]]
+
<li> [[Существенно неоднозначные языки]]</li>
## Отформатировать псевдокод
+
</ol>
## Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
+
 
## Доказательство плохо отформатировано
+
=== МП-автоматы ===
## Оформить красиво источники информации
+
<ol>
# '''!!!''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
+
<li value="23"> ''fixed'' [[Автоматы с магазинной памятью]] (0.5) </li>
## Отформатировать псевдокод
+
# Картинки увеличить
## Грамматику G заменить на \Gamma
+
# Определение жирным
## Перенести описание алгоритма перед псевдокодом
+
# ; в определении заменить на ,
## Хотелось бы адекватные доказательства читать (см. обсуждения)
+
# Англоязычные термины правильно оформить, убрать дублирования
# '''!!!''' [[Лемма о разрастании для КС-грамматик]]
+
# Источники информации, См. также
## Добавить пример не КС-языка, который удовлетворяют условию леммы
+
# Категория
## Источники нормально оформить
+
<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] </li>
## Добавить см. также на варианты леммы
+
<li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] </li>
# [[Лемма Огдена]]
+
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]] (0.5) </li>
## Источники информации добавить
+
# В пример добавить язык автомата
## '''!!!''' Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы
+
# Англоязычные термины
# [[Существенно неоднозначные языки]]
+
# Категория
## Англоязычные термины оформить правильно
+
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] (0.5) </li>
## Ссылки из См. также перенести в источники информации
+
# Категория
# [[Автоматы с магазинной памятью]]
+
# Палку заменить на \mid
## Картинки увеличить
+
# Источники информации
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
+
<li> '''взяли''' [[Нормальная форма ДМП-автомата]] (10) </li>
## Добавить источники информации
+
# Написать!
# [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
+
<li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] </li>
## Ссылки и литературу оформить правильно
+
<li> [[ДМП-автоматы и неоднозначность]] </li>
# [[Детерминированные автоматы с магазинной памятью]]
+
</ol>
## В пример добавить язык автомата
 
## Англоязычные термины
 
# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 
# '''!!!!!''' [[Нормальная форма ДМП-автомата]]
 
## Написать!
 
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 
## Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?
 
## Добавить источники информации
 
  
 
== 3. Теория вычислимости ==
 
== 3. Теория вычислимости ==
# '''!!!''' [[Разрешимые (рекурсивные) языки]]
+
=== Разрешимые и перечислимые языки ===
## Оформить правильно англоязычные термины
+
# [[Разрешимые (рекурсивные) языки]]
## Отформатировать псевдокод
+
# ''fixed'' [[Перечислимые языки]] (2)
## Перенести сюда определение вычислимой функции
+
## Добавить содержательный пример коперечислимого языка
## Добавить определение разрешимого языка в терминах вычислимой функции
+
# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (2.5)
## Заменить источники на источники информации
+
## Убрать лишние знаки препинания из списков в теоремах
## Обернуть if в доказательстве неразрешимого языка в \mathrm
 
## Ещё примеров разрешимых языков (желательно не очень тривиальных)
 
# '''!!!''' [[Перечислимые языки]]
 
## Оформить правильно англоязычные термины
 
## Поправить чуть определение полуразрешимого языка
 
## Отформатировать псевдокоды
 
## Оформить правильно в обе стороны доказательство теоремы
 
## Заменить источники на источники информации
 
## Добавить примеры перечислимых и коперечеслимых языков
 
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
 
## Чуть-чуть код форматнуть
 
 
## Заменить литературу на источники информации
 
## Заменить литературу на источники информации
 +
## Категории
 +
## Отформатировать по правилам
 
# [[Вычислимые функции]]
 
# [[Вычислимые функции]]
## Заменить источники на источники информации
+
# ''fixed'' [[Вычислимые числа]] (2)
## Определения вычислимой функции перенести в конспект Разрешимых языков
 
## Переименовать конспект и чуть-чуть реструктуризовать
 
# [[Вычислимые числа]]
 
 
## Правильно оформить англоязычные термины
 
## Правильно оформить англоязычные термины
 
## Пояснить a(eps) в определении
 
## Пояснить a(eps) в определении
Строка 224: Строка 213:
 
## Ссылки заменить на источники информации
 
## Ссылки заменить на источники информации
 
## Увеличить дроби
 
## Увеличить дроби
# [[Универсальная функция]]  
+
## Пояснить подробней мутные места
 +
# ''fixed'' [[Универсальная функция]] (1)
 
## Англоязычные термины правильно оформить  
 
## Англоязычные термины правильно оформить  
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
 
## Заменить дефисы на тире
 
## Заменить дефисы на тире
# '''!!!''' [[Свойства перечислимых языков. Теорема Успенского-Райса]]
+
## Пояснить нотацию про U(n, x) и U_n(x)
## англоязычные термины
+
## Заголовки внутри конспекта поправить
## классы языков в mathrm
+
# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1)
## заголовки верхнего уровня в ==, а не =
+
## Почему языком L_g(i,x) будет X? Как i связано с X?
## категорию проставить
+
## И вообще доказательство можно сделать чуть менее мутным :)
## Добавить источники информации
+
# [[Неотделимые множества]]
## Заменить в множестве | на \mid
+
# '''fixed''' [[Иммунные и простые множества]] (7)
## Отформатировать псевдокод
 
# '''!!!''' [[Неотделимые множества]]
 
## английские источиники и термины
 
## нормально оформить уже существующий источник
 
## написать, зачем оно может пригодиться
 
## Добавить категории
 
## Интервики
 
# '''!!!''' [[Иммунные и простые множества]]
 
 
## английские источиники и термины
 
## английские источиники и термины
 
## ссылки на вики
 
## ссылки на вики
Строка 250: Строка 232:
 
## Подробней расписать доказательства
 
## Подробней расписать доказательства
 
## Ссылки на леммы внутри конспекта
 
## Ссылки на леммы внутри конспекта
# '''!!!''' [[Теорема о рекурсии]]
+
# '''fixed''' [[Теорема о рекурсии]] (8)
 
## дать ссылки на английские источники и термины  
 
## дать ссылки на английские источники и термины  
 
## Неформальное пояснение к теореме
 
## Неформальное пояснение к теореме
 
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
 
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
 +
# [[Квайны]]
 
# [[Busy beaver]]
 
# [[Busy beaver]]
## Правильно оформить англоязычные термины
+
# [[Колмогоровская сложность]]
## Отформатировать псевдокод
+
 
## Нормально оформить см. также, источники информации и вывод из теоремы
+
=== Вычислительные формализмы ===
# '''!!!''' [[Машина Тьюринга]]
+
<ol>
## Англоязычные термины
+
<li value="14">[[Машина Тьюринга]] </li>
## Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
+
<li> [[Лямбда-исчисление]]</li>
## Выделить машину Тьюринга жирным в определении
+
<li> '''fixed''' [[Примитивно рекурсивные функции]] (10) </li>
## Алгоритмы примеров красиво оформить
+
# названия функций надо в \mathrm
## Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
+
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
## Добавить в многоленточной, что эмулируется многодорожечной
+
<li> ''fixed'' [[Частично рекурсивные функции]] (2) </li>
## Рассказать весёлую историю про тезис Чёрча-Тьюринга
+
# Замечание про взаимную рекурсию в обсуждениях
## Заменить ссылки на источники информации
+
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
## Добавить категории
+
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
# '''!!!''' [[Лямбда-исчисление]] ''(можно получить 10 баллов суммарно)''
+
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
## Англоязычные термины
+
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
## Заменить "в разработке" на "nohate"
+
<li> [[Линейный ограниченный автомат]]</li>
## Написать грамматику лямбд адекватно
+
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
## "Аппликация забирает себе всё," - ошибка - абстракция забирает
+
</ol>
## Провести аналогию между связанными переменными и локальными переменными
+
 
## "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?
+
=== Примеры неразрешимых задач ===
## Написать, что alpha-конверсия -- отношение эквивалентности
+
<ol>
## beta-редукция не олицетворяет. Написать определение формально
+
<li value="24"> ''fixed'' [[m-сводимость]] (3) </li>
## Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней
+
# Англоязычные термины правильно оформить
## Провести аналогию между нумералами Чёрча и нумерацией Гёделя
+
# Добавить примеры m-сведения задач
## Убрать маркированный список из чисел, лучше просто отступ оставить
+
# Заменить знаки неравенств
## "<<числу>>" {{---}} получше оформить
+
# Добавить категории
## Все константы и переменные взяь в Tex
+
# Ссылку на ПСП оформить правильно
## Добавить примеры выполнения операций сложения, умножения и вычитания
+
# Переменные и константы взять в Tex
## "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается
+
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
## Добавить в неподвижной точке про Y-комбинатор
+
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
## Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном
+
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
## Оформить правильно источники информации, см. также
+
<li> '''fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
## Добавить категории
+
# Оформить правильно англоязычные термины
# '''!!!''' [[Примитивно рекурсивные функции]]
+
# Написать более подробное и понятное доказательство
## названия функций надо в \mathrm
+
# Заменить ссылки на источники информации
## Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
+
# Добавить категории
# '''!!!''' [[Частично рекурсивные функции]]
+
# Добавить см. также
## См. замечания в обсуждениях
+
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
## англоязычные термины
+
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
## Дефис заменить на тире
+
<li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>
## "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом
+
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
## Заменить знаки неравенств
+
<li> [[Игра «Жизнь»]] </li>
## "неразрешимость проврк," {{---}} опечатки
+
<li> [[Неразрешимость игры Braid]] </li>
## Оформить правильно источники информации
+
<li> '''fixed''' [[Теорема Райса-Шапиро]] (8) </li>
## Добавить категории
+
# Англоязычные термины
# [[Стековые машины, эквивалентность двухстековой машины МТ]]
+
# Отформатировать псевдокоды
## Интервики
+
# Дать более формальное и понятное определение образца
## Разбить доказательство на абзацы для читабельности
+
# Разбить доказательство на две части, чтобы это было видно
## Добавить категории
+
# Написать строгую формулировку теоремы
## Правильно оформить источники информации
+
# "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие
# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
+
# Лучше явно написать разрешитель для K
## Оформить правильно источники информации
+
# "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
## Добавить категории
+
# Добавить категории, см. также
# [[Линейный клеточный автомат, эквивалентность МТ]]
+
# Заменить литературу на источники информации
## Англоязычные термины правильно оформить
+
</ol>
## Переменные взять в Tex
 
## Добавить категории
 
## Оформить правильно источники информации
 
# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
## внутренние ссылки
 
## категории
 
## Добавить см. также и источники информации
 
# '''!!!''' [[m-сводимость]]
 
## Англоязычные термины правильно оформить
 
## Добавить примеры m-сведения задач
 
## Заменить знаки неравенств
 
## Добавить категории
 
## Ссылку на ПСП оформить правильно
 
## Переменные и константы взять в Tex
 
# '''!!!''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
 
## Англоязычные термины правильно оформить
 
## Заменить дефисы на тире
 
## Заменить знаки неравенств
 
## Все переменные и константы взять в Tex
 
## Добавить примеров решения задач ПСП
 
## Отфомартировать псевдокод
 
## Добавить больше подзаголовков нижнего уровня
 
## Больше интервики
 
## Заменить источники на источники информации
 
## Добавить категории, см. также
 
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
 
## Источники информации
 
## Добавить см. также
 
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
 
## Добавить см. также
 
# '''!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
 
## Оформить правильно англоязычные термины
 
## Написать более подробное и понятное доказательство
 
## Заменить ссылки на источники информации
 
## Добавить категории
 
## Добавить см. также
 
# '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
 
## Англоязычные термины оформить правильно
 
## Заменить дефисы на тире
 
## Заменить прим. на более адекватный аналог
 
## Заменить источники на источники информации
 
## Добавить информацию по последнему замечанию из обсуждений
 
## Добавить см. также
 
# [[Неразрешимость исчисления предикатов первого порядка]]
 
## Добавить см. также
 
## Заменить ссылки на источники информации
 
# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
 
## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
 
# '''!!!''' [[Теорема Райса-Шапиро]]
 
## Англоязычные термины
 
## Отформатировать псевдокоды
 
## Дать более формальное и понятное определение образца
 
## Разбить доказательство на две части, чтобы это было видно
 
## Написать строгую формулировку теоремы
 
## "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие
 
## Лучше явно написать разрешитель для K
 
## "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
 
## Добавить категории, см. также
 
## Заменить литературу на источники информации
 

Текущая версия на 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. Заменить литературу на источники информации