Большая Советская Энциклопедия (цитаты)

Нормальный алгорифм

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

  Концепция Н специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите - произвольная конечная цепочка букв этого алфавита. Цепочка, вовсе не содержащая букв, также считается словом в данном алфавите (пустое слово). Например, цепочки "ииаам", "книга", "гамма" являются словами в русском алфавите, а также в шестибуквенном алфавите {к, н, и, г, а, м}. Элементарным актом преобразования слов в алгоритмических процессах, задаваемых Н, является т. н. операция "подстановки вместо первого вхождения". Пусть Р, Q, R - слова в некотором алфавите. Результатом подстановки Q вместо первого вхождения Р в R называется слово å (R, Р, Q), получаемое следующим образом. Если Р входит в R, т.е. R представимо в виде 12, то среди таких представлений отыскивается представление с наиболее коротким словом 1 и полагается å (R, Р, Q) = 1QS2. Если же Р не входит в R, то å (R, Р, Q) = R. Так, å (гамма, а, е) = гемма.

  Для задания Н  необходимо фиксировать некоторый алфавит А, не содержащий букв "®" и " · ", и упорядоченный список слов вида Р ® Q (простая формула подстановки) или Р ® · Q (заключит. формула подстановки), где Р и Q - слова в А. Формулы подстановок принято записывать друг под другом в порядке следования, объединяя их слева фигурной скобкой. Получающаяся фигура называется схемой Н Исходными данными и результатами работы Н

  где di  (1 £ i  £ n)   означает "®" или "®", разворачивается следующим образом. Отыскивается наименьшее i, при котором i входит в R. Если все i не входят в R, то работа  можно построить Н , являющийся композицией  и , т. е. реализующий следующий интуитивный алгоритм: "сначала выполнить алгоритм , затем к результату применять ".

  Соотношение между интуитивными алгоритмами и Н описывается выдвинутым А. А. Марковым принципом нормализации: всякий алгоритм, перерабатывающий слова в данном алфавите А в слова в этом же алфавите, может быть реализован посредством Н в некотором расширении А. (Легко указать очень простые алгоритмы в А, не реализуемые Н в A; с другой стороны, всегда можно ограничиться двухбуквенным (и даже однобуквенным) расширением A.) Принцип нормализации эквивалентен тезису Черча и, аналогично последнему, не может быть доказан из-за неточности интуитивной концепции алгоритма.

  Лит.: Марков А. А., Теория алгорифмов, М. - Л., 1954 (Тр. Математического института АН СССР, т. 42); Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.

  Б. А. Кушнер.

 


Для поиска, наберите искомое слово (или его часть) в поле поиска


Новости 08.03.2021 02:57:48
02:27 Цена нефти превысила 70 долларов за баррель
02:22 Россиянин зарезал соседа по общежитию из-за ботинок
02:16 Онколог предупредил о смертельной опасности колбасы
02:10 Привившийся «Спутником V» президент Венесуэлы рассказал о своем самочувствии
01:42 Россиянкам предложили в честь 8 Марта отправить бывших возлюбленных в армию
01:42 Бывший возлюбленный Бузовой на подъемнике поздравил россиянок с 8 Марта
01:12 США заявили о готовности нанести ответный удар после атаки военной базы в Ираке
00:40 Российские космонавты с МКС поздравили женщин с 8 Марта
00:29 Путин поздравил женщин с 8 Марта
Больше новостей
СегодняРоссия «Это делает их мягкими и эмоциональными»Россиянки поколениями воспитывают сыновей в одиночку. Стала ли Россия страной слабых мужчин?
СегодняСиловые структуры «Она притягивала людей как магнит»Как легендарная советская разведчица вербовала офицеров гестапо и добывала атомные секреты США
7 марта 2021Бывший СССР «Преемник — свой человек»Самую закрытую страну бывшего СССР ждут большие перемены. Глава Туркмении готовится передать власть
18:52, 7 марта 2021 Высмеянные за сходство с хинкали кроссовки Канье Уэста раскупили за одну минуту
00:12 «Тоттенхэм» выиграл лондонское дерби благодаря дублям Бэйла и Кейна
00:04 Renault привезла кросс-купе Arkana в Европу: цены удивили
СегодняЭкономика Женская доляМировая экономика ежегодно теряет триллионы долларов из-за мужчин. Как женщины исправят ситуацию?
СегодняКультура «Она влюбилась в нее, как другие девочки влюблялись в парней»Вопросы, страхи и признание: история девушки, которая рассказала о своей ориентации родителям
00:08 Викторию Боню начали шантажировать и запросили миллионы рублей
18:44, 7 марта 2021 Мясников опроверг популярный миф о раке груди
00:01 АвтоВАЗ лишил Lada XRay связки мотора 1.8 и «механики»
3 марта 2021Россия «Мне казалось, что на всем свете я одна такая»Россиянка лишилась лица из-за пожара. Она провела жизнь в нищете и ненависти, но не сдалась
7 марта 2021 Цвет войныОккупированная Украина глазами гитлеровских солдат. Редкие снимки времен Второй мировой
23:51, 7 марта 2021 Рэпер Джиган заказал домой тигренка для своих детей
18:11, 7 марта 2021 Первая партия российского «Спутника V» доставлена в Северную Македонию
23:57, 7 марта 2021 В РФПИ сообщили о планах производства «Спутника V» в Италии
5 марта 2021Россия «Ельцин продул бы с разгромным счетом»Глеб Павловский — о выборах 1996 года, поиске преемника Ельцина и испорченных отношениях с Украиной
7 марта 2021Спорт «Выучи чертовы правила!»Петр Ян совершил роковую ошибку. Один неверный удар лишил его пояса чемпиона
00:05 В США старый ВАЗ-2110 продают по цене двухлетней Mitsubishi
23:23, 7 марта 2021 Французский миллиардер погиб при крушении вертолета
00:02 Кроссовер-бестселлер Changan обновился и подорожал на 35%
6 марта 2021Россия «Терпи, не визжи! Ножки раздвигать приятно было?»Беседы со священниками, угрозы и унижения: как проводят аборты по ОМС в России
7 марта 2021Из жизни Многоженец-феминистКак один мужчина смог завести пять жен и 25 детей и при этом сохранить любовь в семье?
22:56, 7 марта 2021 Власти назвали возможную причину пожара на реке Обь
23:03, 7 марта 2021 Зампрокурора российского города задержали при получении взятки
22:22, 7 марта 2021 При взрыве газа в жилом доме в Подмосковье пострадала 14-летняя девочка
7 марта 2021Ценности «Она стала самой известной женщиной в стране»Как советская революционерка влюбляла в себя чиновников и отчаянно боролась за права женщин
6 марта 2021Мир «Противостояние было неизбежным»75 лет назад Черчилль объявил СССР холодную войну. Готов ли Запад снова опустить железный занавес?
22:49, 7 марта 2021 Кадыров отреагировал на смерть правозащитницы Хеды Саратовой
22:09, 7 марта 2021 Свора бездомных собак покусала четырехлетнюю россиянку
22:38, 7 марта 2021 Путин поздравил Большунова с серебром в марафоне на чемпионате мира
6 марта 2021Культура Я так вижнВедьмы, смех и чертовщина: каким вышел супергеройский сериал Marvel «Ванда/Вижн»
6 марта 2021Силовые структуры «Надо идти на фронт, а то война без нас кончится»Как советский артиллерист стал лучшим истребителем «Тигров» и получил награды от Рузвельта и Сталина
22:06, 7 марта 2021 ЕС предрекли потерю 100 миллиардов евро из-за медленной вакцинации
22:08, 7 марта 2021 Принца Гарри обвинили в «объявлении войны» королевской семье
21:22, 7 марта 2021 Роскомнадзор потребовал от Facebook вернуть доступ к материалам российских СМИ
6 марта 2021Культура Порно с «Медведем»Румынский секс-скандал, колесо фортуны и каратели под Брянском: кто победил на Берлинском фестивале
7 марта 2021 Самые продаваемые и любимые кроссоверы россиянКакие кроссоверы и внедорожники покупали в России в феврале
21:19, 7 марта 2021 Jaguar Land Rover на четверть сократит производство
21:34, 7 марта 2021 Посольство России отреагировало на сообщение о крушении вертолета в ЦАР
21:24, 7 марта 2021 15-матчевая победная серия «Манчестер Сити» в АПЛ прервалась в дерби с МЮ
6 марта 2021Интернет и СМИ Группа захватаКак в мире противостоят огромным технологическим компаниям, захватившим контроль над пользователями
21:08, 7 марта 2021 Белоруссия запустит производство «Спутника V»
21:16, 7 марта 2021 Cadillac планирует выпускать новые модели семейства Blackwing
20:20, 7 марта 2021 Появились подробности крушения вертолета с российскими военными в ЦАР
21:14, 7 марта 2021 В Подмосковье жестоко расправились с женщиной и тремя детьми
20:30, 7 марта 2021 В Германии неизвестные осквернили могилу Бандеры
21:00, 7 марта 2021 «Спартак» разгромил «Краснодар» со счетом 6:1 и вышел на третье место в РПЛ
19:55, 7 марта 2021 Британские военные посетили Донбасс
21:18, 7 марта 2021 GM снова останавливает заводы из-за нехватки полупроводников
21:13, 7 марта 2021 Porsche увеличит свою долю в хорватском производителе гиперкаров Rimac
19:25, 7 марта 2021 Россиянка рассказала на видео об инсценированном ради внимания мужа ограблении
20:10, 7 марта 2021 Во Франции снова заинтересовались российской вакциной «Спутник V»
19:15, 7 марта 2021 «Ливерпуль» дома проиграл новичку АПЛ
19:08, 7 марта 2021 Лига безопасного интернета назвала цензурой блокировку поста ТАСС в Facebook
19:10, 7 марта 2021 США и Китай уступили России в борьбе за контроль над Африкой
19:33, 7 марта 2021 Жителям Швейцарии запретят скрывать лицо
18:30, 7 марта 2021 Раскрыты обвинения против задержанного в Абхазии Героя ДНР
19:00, 7 марта 2021 Большунов отреагировал на дисквалификацию норвежского соперника
18:22, 7 марта 2021 В МВД Украины заявили о зависимости «деокупации» Донбасса от Зеленского
17:59, 7 марта 2021 Большунов решил бойкотировать награждение после мужского марафона
17:31, 7 марта 2021 Большунов расплакался после поражения норвежцам в марафоне на чемпионате мира