представление в бинарном алфавите.
11. Теорема о нормированной вычислимости произвольной вычислимой по Тьюрингу
функции – формулировка и пояснение конструкции машины Тьюринга
(декодировщика), формирующей по бинарной записи списка аргументов и
результата счета представление в исходном конечном алфавите.
12. Теорема о нормированной вычислимости произвольной вычислимой по Тьюрингу
функции – формулировка и пояснение конструкции диаграммы машины Тьюринга,
осуществляющей кодирование, моделирование в
бинарном алфавите и
декодирование в исходный алфавит результатов счета.
13. Теорема о композиции вычислимых по Тьюрингу функций – формулировка и
пояснение конструкции диаграммы результирующей машины Тьюринга.
14. Тезисы Тьюринга и Черча. Статус этих тезисов и взаимосвязь между ними.
15. Характеристическая функция для множества слов в заданном алфавите.
Определение алгоритмически разрешимого множества (проблемы).
16.
Проблема самоприменимости – формулировка, статус проблемы, обоснование.
17. Проблема остановки – формулировка, статус проблемы, обоснование.
18. Метод сведение одной проблемы к другой. Пример его использования.
19.
Проблема остановки на пустой ленте – формулировка, статус проблемы,
обоснование.
20. Униформная проблема остановки и проблема бессмертия – формулировка и статус
проблем.
21. Проблем домино – формулировка, статус проблемы и обоснование.
22.
Проблема соответствия Поста - формулировка и статус проблемы.
23. Универсальная машина Тьюринга U – общее описание U, зоны ленты U, их
назначение. Представление таблицы команд произвольной машины Тьюринга –
пример и пояснение использования.
24. Универсальная машина Тьюринга U – пояснение диаграммы машины Тьюринга,
отвечающей за обновление “текущего” состояния моделируемой машины Тьюринга.
25. Универсальная машина Тьюринга U – пояснение диаграммы машины Тьюринга,
описывающей весь алгоритм работы U.
26. Проблема остановки универсальной машины Тьюринга – формулировка, статус
проблемы, обоснование.
27. Причины введения рекурсивных функций. Определение базовых рекурсивных
функций. Вычислимость этих функций по Тьюрингу.
28. Определение операторов суперпозиции и примитивной рекурсии. Примеры
использования. Определение примитивно рекурсивной функции. Пример
примитивно рекурсивной функции.
29. Определение оператора минимизации. Пример использования. Определение
частично рекурсивной
функции и общерекурсивной функции. Пример частично
рекурсивной и общерекурсивной функций.
30. Теорема о суммировании и мультиплицировании примитивно рекурсивных
функций. Пример использования.
31. Теорема о мажорировании неявно заданной функции через примитивно рекурсивные
функции. Пример использования.
32. Канторовские нумерации числовых наборов: функции свертки набора в номер и
функции проектирования – их основные свойства и статус вычислимости. Примеры
использования на парах и тройках чисел.
33. Геделевская нумерация числовых наборов. Ее отличие от канторовской и
математическое обоснование.
34. Геделевская нумерация числовых наборов. Функция Геделя, ее статус вычислимости
и основное свойство функции Геделя.
35. Определение рекурсивного и примитивно рекурсивного множества. Примеры
рекурсивных и примитивно рекурсивных множеств.
36. Свойства рекурсивных множеств – свойства замкнутости и свойство направленной
функции.
37.
Понятие и определение рекурсивно перечислимого множества. Примеры рекурсивно
перечислимых множеств.
38. Свойства замкнутости рекурсивно перечислимых множеств.
39. Теорема Поста о рекурсивной перечислимости множества и его дополнения.
40. Характеристика рекурсивно перечислимого множества через область значений
функции.
41. Теорема о графике частично рекурсивной функции.
42. Теорема об области определения частично рекурсивной функции.
43. Теорема Клини о нормальной форме частично рекурсивной функции.
44. Функция Аккермана: определение и свойства.
45. Характеризация примитивно-рекурсивной функции посредством функции
Аккермана.
46. Теорема Райса-Успенского: формулировка и смысл теоремы.
47. Определение вычислимости на конечно-порожденных алгебраических структурах и
на множестве вещественных чисел.
48. Содержательное определение сети Петри. Отличительные особенности и области
применения сетей Петри. Примеры сетей Петри.
49. Формальное определение сети Петри. Поведенческие свойства сетей Петри.
Примеры сетей Петри с определенными свойствами.
50. Дерево маркировок сети Петри. Пример дерева маркировок. Структурные свойства
сетей Петри. Примеры сетей Петри с определенными свойствами.
Достарыңызбен бөлісу: