Основные положения машины Тьюринга
1. Машина Тьюринга имеет конечное число знаков si, образующих внешний алфавит, в котором кодируются сведения, подаваемые в МТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак (s1), посылка которого в какую-либо ячейку стирает находившийся в ней знак и оставляет ее пустой. В зависимости от поданной начальной информации (содержащихся на ленте внешней памяти знаков) возможны два случая: o после конечного числа тактов машина останавливается (имея информацию β), подавая сигнал об остановке. В этом случае МТ применима к информации и перерабатывает ее в информацию β; o остановка никогда не наступает. В этом случае МТ не применима к начальной информации . 2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке ( R – вправо, L–влево, N– нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте t команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj. 3. Логический блок МТ имеет конечное число состояний {qi} i=1..m. Знаки R, L, N, q1,..,qmобразуют внутренний алфавит машины. По принципу обработки информации вычислительное устройство, предложенное Нейманом (автомат Неймана – АН), существенно отличается от машины Тьюринга. В автомате Неймана число одновременно обрабатываемых ячеек может неограниченно расти, оставаясь в каждый момент конечным.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (856)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |