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

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

Текущая версия на 22:19, 9 марта 2019

1 Производящие функции

  1. Производящая функция
  2. Арифметические действия с формальными степенными рядами
  3. Производящие функции нескольких переменных
  4. Разложение рациональной функции в ряд
  5. Задача о счастливых билетах
  6. Произведение Адамара
  7. Интегрирование/дифференцирование производящих функций
  8. Производящая функция Дирихле

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

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

  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=70251»