Алгоpифм Маpкова

From

Evgenij Masherov (2:5020/175.2)

To

Serge Petruschenko

Date

2002-12-05T09:51:07Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Dec 03 2002 18:17, Serge Petruschenko wrote to Nick Kovaliov:

 
 AR>>> И делать это надо с помощью алгоpитмов Маpкова.
 NK>> Всё же оно называется алгорифм.

 SP> Кащениты в эхе?

 Вводя для предложенной им системы правил, позволяющей формализовать понятие
алгоритма, термин "алгориФмы", А.А.Марков ориентировался на норму русской
транскрипции, согласно которой греческая "тэта" заменялась русской "фитой" -
буквой Ф, в отличие от транскрипции западной, где использовался диграф th, при
дальнейшем переводе на русский превращавшийся в "т". Основная идея Маркова -
задание последовательности действий НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК -
очередностью правил "что  на  что менять".  Лучше  всего  это  показать на
примере замены слов, тем более, что и сам Марков любую последовательность
букв, какую ни в одном словаре не сыщешь, называл "словами".  Так при наличии
двух подстановок: меняющей "ха" на "ссон" и "мусс" на "сл"  из  "муха"
можно сделать "слон". Это представдение алгоритма конкурирует с рекурсивными
функциями, машиной Тьюринга, машиной Поста и т.п. в том смысле, что можно
доказать их эквивалентность, но удобство для разных задач различно. На идеях
Маркова создан, в частности, алгоритмический язык "РЕФАЛ", предназначенный для
обработки текстов.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)