Мегаобучалка Главная | О нас | Обратная связь


Основные положения машины Тьюринга



2015-12-07 856 Обсуждений (0)
Основные положения машины Тьюринга 0.00 из 5.00 0 оценок




1. Машина Тьюринга имеет конечное число знаков si, образующих внешний алфавит, в котором кодируются сведения, подаваемые в МТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак (s1), посылка которого в какую-либо ячейку стирает находившийся в ней знак и оставляет ее пустой.

В зависимости от поданной начальной информации (содержащихся на ленте внешней памяти знаков) возможны два случая:

o после конечного числа тактов машина останавливается (имея информацию β), подавая сигнал об остановке. В этом случае МТ применима к информации и перерабатывает ее в информацию β;

o остановка никогда не наступает. В этом случае МТ не применима к начальной информации .

2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке ( R – вправо, L–влево, N– нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте t команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj.

3. Логический блок МТ имеет конечное число состояний {qi} i=1..m.

Знаки R, L, N, q1,..,qmобразуют внутренний алфавит машины.
Переработанный знак sj, записываемый в просматриваемую ячейку, состояние, которое примет машина Тьюринга в следующем такте q(t+1) и выполняемая в данном такте операция перехода к следующей ячейке P(t+1) являются функцией анализируемого в данном такте символа и текущего состояния машины si и q(t):
si(t+1)=f1(si,q(t));
q(t+1)=f2(si,q(t));
P(t+1)=f3(si,q(t)).
Программа для МТ определяется тройкой {si, P, q}t.

По принципу обработки информации вычислительное устройство, предложенное Нейманом (автомат Неймана – АН), существенно отличается от машины Тьюринга.

В автомате Неймана число одновременно обрабатываемых ячеек может неограниченно расти, оставаясь в каждый момент конечным.
Элемент Неймана (ЭН) – это устройство, которое на каждом такте пребывает в одном из конечного числа состояний ri R, образующих его алфавит. ЭН имеет два входных канала: левый и правый; по каждому из них на такте t также поступает по одному состоянию из R (рис. 2).

Рис. 2. Элемент Неймана
Элемент реализует функцию zt+1= (ri, rj, rm)t, то есть в такте t+1 переходит в состояние z, определяемое его состоянием в текущий момент времени и значениями, поступившими по входным каналам.
Состояния элементов Неймана в момент времени t определяют конфигурацию автомата Неймана (рис. 3) в момент t: K(t).


Рис. 3. Структура автомата Неймана
Функционирование АН – это переход от состояния К(t) к состояниям K(t+1), K(t+2)...
За один такт свое состояние может менять большое число элементов Неймана, что фактически приводит к параллельной обработке информации.



2015-12-07 856 Обсуждений (0)
Основные положения машины Тьюринга 0.00 из 5.00 0 оценок









Обсуждение в статье: Основные положения машины Тьюринга

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (856)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.008 сек.)