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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Разрешимые и перечислимые языки)
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 32: Строка 32:
 
<ol>
 
<ol>
 
<li value="14">[[Машина Тьюринга]] </li>
 
<li value="14">[[Машина Тьюринга]] </li>
−
<li> [[Лямбда-исчисление]]</li>
+
<li> [[Лямбда-исчисление]] 0.5</li>
−
<li>[[Примитивно рекурсивные функции]] </li>
+
# Поправить тех
 +
<li>[[Примитивно рекурсивные функции]] 0.5 </li>
 +
# Поправить тех
 
<li> [[Частично рекурсивные функции]]  </li>
 
<li> [[Частично рекурсивные функции]]  </li>
−
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
+
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] 0.5 </li>
−
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
+
# Добавить см также
−
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
+
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] 0.5 </li>
−
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
+
# Добавить см также
 +
# поправить тех
 +
<li> [[Линейный клеточный автомат, эквивалентность МТ]] 0.5 </li>
 +
# добавить см также
 +
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] 0.5 </li>
 +
# поправить тех
 
<li> [[Линейный ограниченный автомат]]</li>
 
<li> [[Линейный ограниченный автомат]]</li>
−
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
+
<li> [[Сверхтьюринговые вычисления (гипервычисления)]] 0.5</li>
 +
# увеличить дроби
 
<li> [[Тьюринг-полнота]] (4)</li>
 
<li> [[Тьюринг-полнота]] (4)</li>
 
# Провести аналогию с теоремой Геделя о неполноте
 
# Провести аналогию с теоремой Геделя о неполноте
Строка 50: Строка 58:
 
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
 
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
 
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
 
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
−
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
+
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]] 0.5</li>
−
<li> [[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]] </li>
+
# поправить тех
 +
# добавить см также
 +
# добавить источники информации
 +
<li> [[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]] 0.5 </li>
 +
# поправить тех
 
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
 
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
 
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
 
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>

Текущая версия на 19:38, 4 сентября 2022

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

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

  1. Разрешимые (рекурсивные) языки
  2. Перечислимые языки 0.5
    1. добавить см также
  3. Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций 0.5
    1. поправить тех
  4. Вычислимые функции 0.5
    1. добавить см также
  5. Вычислимые числа 0.5
    1. поправить тех
  6. Универсальная функция
  7. Свойства перечислимых языков. Теорема Успенского-Райса 0.5
    1. поправить тех и псевдокод
  8. Неотделимые множества
    1. поправить тех
    2. добавить см также
  9. Иммунные и простые множества
  10. Теорема о рекурсии 0.5
    1. поправить псевдокод
    2. поправить тех
    3. сделать см также на проверяемые конспекты
  11. Квайны 0.5
    1. поправить псевдокод
    2. добавить см также
  12. Busy beaver 0.5
    1. поправить псевдокод
  13. Колмогоровская сложность 0.5
    1. поправить всевдокод

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

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

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

  1. m-сводимость
  2. Проблема соответствий Поста
  3. Однозначность КС-грамматики
  4. Неразрешимость задачи об эквивалентности КС-грамматик 0.5
    1. поправить тех
    2. добавить см также
    3. добавить источники информации
  5. Пустота пересечения КС-грамматик 0.5
    1. поправить тех
  6. Задача о замощении полимино
  7. Задача о выводе в полусистеме Туэ
  8. Неразрешимость исчисления предикатов первого порядка
  9. Неразрешимость проблемы существования решения диофантова уравнения в целых числах (10)
    1. дописать, чтобы было классно
  10. Неразрешимость задачи вывода типов в языке с зависимыми типами (3)
    1. [math]\beta[/math]-эквивалентны в интервики
    2. добавить пару примеров вывода типа в данной системе
  11. Игра «Жизнь»
  12. Неразрешимость игры Braid
  13. Теорема Райса-Шапиро
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_вычислимости:Тикеты&oldid=85699»