Нормальный Алгоритм Маркова Пример
Нормальные алгоритмы Маркова предназначены для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит. Функция, заданная на некотором множестве слов алфавита, называется нормально вычислимой, если найдется такое расширение данного алфавита ( ) и такой нормальный алгоритм в, что каждое. Нормальные алгорифмы Маркова (НАМ) представляются нормальной схемой подстановок, которая состоит из совокупности подстановок, расположенных в определенном порядке. В виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. Рассмотрим примеры на составление программ для МТ, чтобы проде. Нормальные алгоритмы Маркова.
Нормальные Алгоритмы Маркова Примеры Решения Задач
неприменима Для обозначения марковской подстановки math(P,Q)/math используется запись mathP to Q/math. Она называется формулой подстановки math(P,Q)/math. Некоторые подстановки math(P,Q)/math будем называть заключительными (смысл названия станет ясен чуть позже).
Для обозначения таких подстановок будем использовать запись mathP to.,Q/math, называя ее формулой заключительной подстановки. Слово mathP/math называется левой частью, а mathQ/math — правой частью в формуле подстановки. Нормальные алгоритмы и их применение к словам Упорядоченный конечный список формул подстановок. math Lambda Rightarrow a Rightarrow aa Rightarrow aaa Rightarrow aaaa Rightarrow ldots/math Это означает, что к пустому слову данный алгоритм не применим. Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: math499 Rightarrow a499/math (применена последняя формула) math Rightarrow 4a99/math (формула из середины второго столбца) math Rightarrow 49a9 Rightarrow 499b/math (дважды применена формула из конца второго столбца) math Rightarrow 499b/math (предпоследняя формула) math Rightarrow 49b0 Rightarrow 4b00/math (дважды применена предпоследняя формула первого столбца) math Rightarrow 500/math (применена формула из середины первого столбца).
Нормальный Алгоритм Маркова Примеры
Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что math328 Rightarrow 329, 789 Rightarrow 790/math. В рассмотренном примере нормальный алгоритм построен в алфавите mathB/math, являющемся существенным расширением алфавита matha/math (т.е.
mathA subseteq B/math и mathA ne B/math), но данный алгоритм слова в алфавите matha/math перерабатывает снова в слова в алфавите mathA/math. В таком случае говорят, что алгоритм задан над алфавитом mathA/math. Создатель теории нормальных алгоритмов советский математик А.
Марков выдвинул гипотезу, получившую название 'Принцип нормализации Маркова'. Согласно этому принципу, для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима. Сформулированный принцип, как и тезисы Тьюринга и Чёрча, носит внематематический характер и не может быть строго доказан. Он выдвинут на основании математического и практического опыта.
Все, что в предыдущих параграфах было сказано о тезисах Тьюринга и Чёрча, можно с полным правом отнести к принципу нормализации Маркова. Косвенным подтверждением этого принципа служат теоремы следующего пункта, устанавливающие эквивалентность и этой теории алгоритмов теориям машин Тьюринга и рекурсивных функций. Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу Это совпадение будет означать, что понятие нормально вычислимой функции равносильно понятию функции, вычислимой по Тьюрингу, а вместе с ним и понятию частично рекурсивной функции. Теорема 34.10. Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.