Многоголовочный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 1
Мода - это форма уродства столь невыносимого, что нам приходится менять ее каждые шесть месяцев. Законы Мерфи (еще...)

Многоголовочный автомат

Cтраница 1


Многоголовочный автомат может быть получен из многоленточного автомата требованием, чтобы его ленты были идентичными. Ясно, что такая машина может рассматриваться как одноленточный автомат, головки которого не-зайисимо Друг от друга считывают ленту и вначале все находятся над исходной позицией ленты.  [1]

Многоленточный или многоголовочный автомат А определяется заданием некоторого алфавита S ( s, s2, , sn, конечного множества состояний Q и таблицы переходов.  [2]

Вопрос разрешимости эквивалентности схем программ тесно связан с существованием упрощающих алгоритмов. Если проблема эквивалентности разрешима, то в принципе существует алгоритм для сведения схемы к простейшей ( в некотором смысле) возможной форме. В разделах 4 и 5 мы показываем, что для почти всякого разумного - понятия эквивалентности между машинными программами оба вопроса: об эквивалентности и о неэквивалентности пары схем не являются частично разрешимыми. Здесь под частичной разрешимостью понимается рекурсивная перечислимость, а именно: отношение г ( а, Ъ) частично разрешимо, но не разрешимо, если существует алгоритм для порождения списка всех пар ( а, Ь), таких, что г ( а, Ъ) выполняется, но не существует алгоритма, перечисляющего все такие пары, для которых г ( а, Ь) не выполняется. Отсюда следует, что не существует оптимизирующих алгоритмов для полного сведения схемы &, так сказать, к кратчайшей возможной форме. Фактически, как будет показано, таких алгоритмов не существует даже в случае строго ограниченных классов схем. Доказательства используют некоторые свойства многоголовочных автоматов; последние рассматриваются в разд.  [3]



Страницы:      1