ОБЩАЯ ТЕОРИЯ АЛГОРИТМОВ
Геделевская нумерация объектов
Геделевский номер машины Тьюринга
Геделевский номер машины Тьюринга
Все ли функции вычислимы?
Все ли функции вычислимы?
Проблема остановки машины Тьюринга
Проблема остановки машины Тьюринга
Алгоритмически неразрешимые проблемы
Алгоритмически неразрешимые проблемы
Алгоритмически неразрешимые проблемы
Алгоритмы Маркова
Понятие Марковской подстановки
Нормальный алгоритм Маркова:
Примеры алгоритмов Маркова
Вычислимость функций по Маркову
Принцип нормализации Маркова
Эквивалентность алгоритмических моделей
Эквивалентность алгоритмических моделей
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
1.60M
Категория: ИнформатикаИнформатика

Общая теория алгоритмов

1. ОБЩАЯ ТЕОРИЯ АЛГОРИТМОВ

Глава 5, стр. 114

2.

• Необходимость нумерации произвольных
объектов вызвана, прежде всего,
необходимостью анализа различных задач,
которые должны обрабатывать
алгоритмы в качестве исходной
информации.
• Следовательно, для
того, чтобы рассматривать алгоритмы над
алгоритмами, необходимо представлять
алгоритм (в данной главе — машину
Тьюринга) в виде натуральных чисел.
2

3. Геделевская нумерация объектов

Считается, что введена система Геделевской нумерации для
всех объектов A, принадлежащих некоторому множеству M,
если выполняются следующие два требования:
1. существует натуральное число ng(A), которое однозначно
определяется по A;
2. для всех n, принадлежащих множеству натуральных
чисел N, выполняется одно из двух условий:


либо не существует объекта A, принадлежащего множеству M, такого,
что n = ng(A);
либо существует единственный объект A, принадлежащий M, такой, что
n =ng(A) и этот объект однозначно восстанавливается по n.
3

4. Геделевский номер машины Тьюринга

Известно, что любая машина Тьюринга
English     Русский Правила