Составители:
42
понятие «алгоритма» независимо было разработано математиками
А. Тьюрингом (Великобритания), Э. Постом (США) и А.А. Марковым
(СССР). Для уточнения этого термина применительно к вычислениям
Тьюринг и Пост предложили «абстрактные вычислительные машины».
Обе эти работы велись также независимо, машины были предложены в
1936 году (в мае и октябре соответственно), они эквивалентны, но
машина Поста отличается большей простотой. Нормальный алгоритм
Маркова был предложен в 1940-х и лег в основу логического
программирования.
Машина Поста (1936)
Состоит из каретки (считывающая и записывающая головка) и
разбитой на секции бесконечно ленты, каждая секция ленты либо пустая
(0), либо помечена меткой (1). За шаг каретка может сдвинуться на одну
позицию в сторону, считать, поставить или удалить метку в том месте,
где она стоит. Работа машины задается программой, команд всего 6
(сдвиг вправо, сдвиг влево, запись метки, удаление метки, условный
переход по метке, остановка).
Машина Тьюринга (1936) [3.6]
Состоит из бесконечной ленты, разбитой на ячейки, и
управляющего устройства, перемещающегося по ленте, читающего и
записывающего в ячейки символы некого алфавита (рис. 3.2).
Управляющее устройство способно находиться в одном из множества
состояний (число состояний конечно и точно задано), и работает
согласно правилам перехода, которые и представляют алгоритм,
реализуемый данной машиной.
Рис. 3.2. Машина Тьюринга
Каждое правило перехода предписывает машине, в зависимости от
текущего состояния q
i
и наблюдаемого в текущей клетке символа a
j
,
записать в эту клетку новый символ a
j1
, перейти в новое состояние q
i1
и
переместиться на одну клетку влево или вправо. Некоторые состояния
машины Тьюринга могут быть помечены как терминальные, и переход в
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
