748
правок
Изменения
Новая страница: «== 3. Теория вычислимости == === Разрешимые и перечислимые языки === # [[Разрешимые (рекурсивны...»
== 3. Теория вычислимости ==
=== Разрешимые и перечислимые языки ===
# [[Разрешимые (рекурсивные) языки]]
# [[Перечислимые языки]]
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
# [[Вычислимые функции]]
# [[Вычислимые числа]]
# [[Универсальная функция]]
# [[Свойства перечислимых языков. Теорема Успенского-Райса]]
# [[Неотделимые множества]]
# [[Иммунные и простые множества]]
# [[Теорема о рекурсии]]
# [[Квайны]]
# [[Busy beaver]]
# [[Колмогоровская сложность]]
=== Вычислительные формализмы ===
<ol>
<li value="14">[[Машина Тьюринга]] </li>
<li> [[Лямбда-исчисление]]</li>
<li>[[Примитивно рекурсивные функции]] </li>
<li> [[Частично рекурсивные функции]] </li>
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
<li> [[Линейный ограниченный автомат]]</li>
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
</ol>
=== Примеры неразрешимых задач ===
<ol>
<li value="24"> [[m-сводимость]] </li>
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
<li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
<li> [[Игра «Жизнь»]] </li>
<li> [[Неразрешимость игры Braid]] </li>
<li> [[Теорема Райса-Шапиро]] </li>
</ol>
=== Разрешимые и перечислимые языки ===
# [[Разрешимые (рекурсивные) языки]]
# [[Перечислимые языки]]
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
# [[Вычислимые функции]]
# [[Вычислимые числа]]
# [[Универсальная функция]]
# [[Свойства перечислимых языков. Теорема Успенского-Райса]]
# [[Неотделимые множества]]
# [[Иммунные и простые множества]]
# [[Теорема о рекурсии]]
# [[Квайны]]
# [[Busy beaver]]
# [[Колмогоровская сложность]]
=== Вычислительные формализмы ===
<ol>
<li value="14">[[Машина Тьюринга]] </li>
<li> [[Лямбда-исчисление]]</li>
<li>[[Примитивно рекурсивные функции]] </li>
<li> [[Частично рекурсивные функции]] </li>
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
<li> [[Линейный ограниченный автомат]]</li>
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
</ol>
=== Примеры неразрешимых задач ===
<ol>
<li value="24"> [[m-сводимость]] </li>
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
<li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
<li> [[Игра «Жизнь»]] </li>
<li> [[Неразрешимость игры Braid]] </li>
<li> [[Теорема Райса-Шапиро]] </li>
</ol>
