Составители:
43
любое из них означает конец работы, остановку алгоритма. Для начала
работы необходимо указать конечное и начальное состояния, начальную
конфигурацию на ленте и расположение головки машины. Можно
сказать, что машина Тьюринга представляет собой простейшую
вычислительную машину с линейной памятью.
Машина Тьюринга является расширением конечного автомата,
описывающего пути изменения состояния объекта в зависимости от его
текущего состояния и входных данных, при условии, что общее
возможное количество состояний конечно. Машина Тьюринга способна
имитировать другие исполнители (с помощью задания правил перехода),
каким-либо образом реализующие процесс пошагового вычисления, в
котором каждый шаг вычисления достаточно элементарен.
От машины Тьюринга происходит и понятие «полноты по
Тьюрингу», означающей возможность реализации в вычислителе любой
вычислимой функции.
Тьюринг показал, что не существует «чудесной машины»,
способной решать все математические задачи. Но, продемонстрировав
ограниченность возможностей, он на бумаге построил то, что позволяет
решать очень многое, и что теперь называется словом «компьютер».
Хотя машина Тьюринга не стала реально действующим устройством, она
до настоящего времени постоянно используется в качестве основной
модели для выяснения сущности таких понятий, как «вычислительный
процесс», «алгоритм», а также для выяснения связи между алгоритмом и
вычислительными машинами.
Клеточный автомат Неймана (1948) [3.7]
Фон Нейман, привлеченный в 1947 г. к созданию вычислительных
машин, стал разрабатывать теорию самовоспроизводящихся автоматов и
универсальных вычислительных машин. Такие машины на уровне блок-
схемы близки к машине Тьюринга, а их функционирование во многом
аналогично процессу воспроизведения живой клетки. Нейман довел эту
общую схему до детальной логической конструкции, введя
представление о клеточном автомате, который состоит из
неограниченного числа повторяющихся конечных автоматов-
переключателей, каждый из которых взаимодействует со своими
соседями. Такие идеализированные переключатели с задержками были
получены из идеализированных нейронов, имели несколько
возбуждающих и тормозящих входов, пороговое число и единичную
задержку.
В упрощенном виде каждый конечный элементарный автомат на
каждом такте пребывает в одном из конечного числа состояний r
i
и
имеет два входных канала: левый и правый (рис. 3.3). По каждому из них
на такте t поступает по одному состоянию из r. Состояния элементов в
Страницы
- « первая
- ‹ предыдущая
- …
- 39
- 40
- 41
- 42
- 43
- …
- следующая ›
- последняя »
