AAA
Обычный Черный



Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

версия для печатиВерсия для печати



Библиографическая запись: Нормальные алгорифмы Маркова. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/informaczionnye-texnologii/normalnye-algorifmy-markova/ (дата обращения: 19.08.2022)

Нормальные алгорифмы Маркова

Нормальные алгорифмы Маркова

Содержание

    Нормальные алгорифмы Маркова

    Нормальный алгоритм (алгорифм) Маркова (НАМ) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений.

    Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.

    Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам. В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления.

    Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L → D, где L иD — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L →⋅ D, где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы → и →⋅ не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

    Конкатенацией слов

    12.07.2022, 31 просмотр.


    Уважаемые посетители! С болью в сердце сообщаем вам, что этот сайт собирает метаданные пользователя (cookie, данные об IP-адресе и местоположении), что жизненно необходимо для функционирования сайта и поддержания его жизнедеятельности.

    Если вы ни под каким предлогом не хотите предоставлять эти данные для обработки, - пожалуйста, срочно покиньте сайт и мы никому не скажем что вы тут были. С неизменной заботой, администрация сайта.

    Dear visitors! It is a pain in our heart to inform you that this site collects user metadata (cookies, IP address and location data), which is vital for the operation of the site and the maintenance of its life.

    If you do not want to provide this data for processing under any pretext, please leave the site immediately and we will not tell anyone that you were here. With the same care, the site administration.