вход Вход Регистрация



 

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

Нормальный алгоритм задается конечной таблицей подстановок слов в данном алфавите.

Пример: существует алфавит ; таблица подстановок:

1. ;

2. ;

3. .

Пусть задано слово . Алгоритм преобразования:

1) ;

2) ;

3) ;

4) далее не применима ни одна формула.

Результат: .

Установлено, что любой алгоритм эквивалентен некоторому нормальному алгоритму.

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру