436
правок
Изменения
м
---- *# [[Машина Тьюринга]]*# [[Лямбда-исчисление]]*# [[Примитивно рекурсивные функции]]*## названия функций надо в \mathrm или \mathtt## привести пример использования теоремы о примитивной рекурсивности# [[Частично рекурсивные функции]]*## англоязычные термины## [[Стековые машины, эквивалентность двухстековой машины МТ]]*# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]*# [[Линейный клеточный автомат, эквивалентность МТ]]*# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]## внутренние ссылки=== Примеры неразрешимых задач ===## категории*# '''взяли''' [[m-сводимость]]*## англоязычные термины## ссылка на английскую википедию, у существующих источников ссылки на номер страницы## написать еще про сведение по Тьюрингу и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюринга# '''взяли''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]*## англоязычные термины## {{tick}} англоязычные источники, в частности, википедия## {{tick}} Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название## {{tick}} "Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?## {{tick}} "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо## {{tick}} побольше интервики## {{tick}} форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.## {{tick}} Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.## вообще в целов привести к более адекватному и понятному виду# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]*# '''взяли''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]*## замечания в обсуждении# '''взяли''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]*## замечения в обсуждении# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]*## написать. Это очень просто на самом деле, если немного помнить матлогику# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления уравнения в целых числах]]## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.*# [[Теорема Райса-Шапиро]]
Napisal po-russky
__TOC__
== 1. Автоматы и регулярные языки ==
# '''взяли fixed !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
# [[Прямое произведение ДКА]]
## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
# '''fixed''' [[Недетерминированные конечные автоматы]]
## Английские термины
## Англоязычные источники (хотя бы википедия)
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
# [[Автоматы с eps-переходами. Eps-замыкание]]
# '''fixed''' [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
## Опять классы языков курсивом
## Внутренние ссылки на автоматные и регулярные языки
# [[Замкнутость регулярных языков относительно различных операций]]
#: см. 1
# ''fixed'' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
# [[Решение уравнений в регулярных выражениях]]
# '''взяли написан !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
#: фиг знает что это, но надо написать, видимо
# [[Эквивалентность состояний ДКА]]
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
# '''взяли !!!''' [[Контексты и синтаксические моноиды]]## добавить английских терминов, ссылку на англоязычную вики
## доказательство последнего утверждения
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо, ну или хотя бы еще пару интересных примеров про синтактические моноиды каких-нибудь классов языков, например.
== 2. Контекстно-свободные грамматики ==
# [[Лемма о разрастании для КС-грамматик]]
# [[Лемма Огдена]]
# ''взяли'' [[Существенно неоднозначные языки]]
## добавить английские термины
## добавить всякое интервики
# [[Автоматы с магазинной памятью]]
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
# '''fixed'''[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.
## Картинка. Что она означает?
## ссылки на википедию
# [[Вычислимые числа]]
# '''!!!взяли''' [[Диагональный метод]]
## объяснить, что такое универсальная функция неформально, и нафига она нужна.
## англоязычные термины
## ссылки на вики
## а зачем оно нужно?
# '''!!!взяли''' [[Теорема о рекурсии]]
## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
## дать ссылки на английские источники и термины
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
# '''!!!взяли''' [[Теорема о рекурсии]]
#: Добавить примеры простых доказательств с использованием теоремы о рекурсии:
## Теоремы Успенского-Райса
## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
# [[Busy beaver]]
