Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Способы композиции машин Тьюринга





1. Последовательное подключение одной машины Тьюринга к другой. Пусть и – две машины Тьюринга над алфавитом {0,1}, множества состояний машин не пересекаются. Перенумеруем 0,1,…, l- 1 все команды с программы . Пусть p (x) – предикат на множестве {0,1,…, l -1}. Последовательное подключение к (относительно предиката p (x)) – это машина Тьюринга , которая получается следующим образом. Первая половина таблицы для совпадает с таблицей для тех клеток, в которых нет команды с .

Если p (n)=1, то в клетке n – команда , – номер строки (0 или 1), где находится клетка n, – начальное состояние .

Если p (n)=0, то в клетке n – команда с . Вторая половина таблицы Т полностью совпадает с таблицей .

 

 
     
     

 

В частном случае, если – начальное состояние машины , а – начальное состояние , заменим в программе состояние на состояние , и полученную программу объединим с программой . В результате мы получим программу для машины , которая является композицией машин и по паре состояний (, ).

 

2. Итерация машины Тьюринга. Пусть – машина Тьюринга над алфавитом {0,1}. Перенумеруем 0,1,…, l -1 все команды с программы . Пусть p (x) – предикат на множестве {0,1,…, l -1}. Итерация машины Тьюринга относительно предиката p (x) – это машина Тьюринга Т, которая получается следующим образом. Таблица Т совпадает с таблицей для тех клеток, в которых нет команды не с .

Если p (n)=1, то в клетке n – команда , a – номер строки, где находится клетка n, – начальное состояние .

Если p (n)=0, то в клетке n – команда с .

Действительно, имеет место итерация, т.е. многократная работа машины .

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

Отметим, что начальных и заключительных состояний может быть несколько.

 

В Содержание.

 

Date: 2015-09-24; view: 848; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию