Операции над машинами Тьюринга.

Пусть машины и имеют соответственно программы и . Предположим, что внутренние алфавиты этих машин не пересекаются и что — некоторое заключительное состояние машины , a — какое-либо начальное состояние машины Заменим всюду в программе состояние на состояние и полученную программу объединим с программой . Новая программа П определяет машину T, назы­ваемую композицией машин и (по паре состояний ) и обозначаемую через или более подробно: - Внешний алфавит композиции является объединением внешних алфавитов машин и .

Пусть q' — некоторое заключительное состояние машины Г, а q"; — какое-либо состояние машины T, не являющееся заключитель­ным. Заменим всюду в программе П машины T символ q' на q". Получим программу П ', определяющую машину T'(q', q"). Маши­на T' называется итерацией машины T (по паре состояний

Пусть машины Тьюринга , и задаются программами , и соответственно. Считаем, что внутренние алфавиты этих ма­шин попарно не пересекаются. Пусть и — какие-либо различные заключительные состояния машины . Заменим всюду в програм­ме состояние некоторым начальным состоянием машины , а состояние некоторым начальным состоянием машины . Затем новую программу объединим с программами и . Получим программу П, задающую машину Тьюринга . Эта машина называется разветвлением машин и , управляемым машиной .

При задании сложных машин Тьюринга часто применяют так называемую операторную запись алгоритма, которая представляет собой строку, состоящую из символов, обозначающих машины, сим­волов перехода (вида и ), а также символов α и ω;, служащих для обозначения соответственно начала и окончания работы алгоритма. В операторной записи (некоторого алгоритма) выраже­ние ,обозначает разветвление машин и , управляемое машиной , причем заключительное состояние ма­шины заменяется начальным состоянием машины , а всякое другое заключительное состояние машины заменяется начальным состоянием машины (одним и тем же). Если машина имеет одно заключительное состояние, то символы и служат для обозначения безусловного перехода. Там, где не могут возникнуть недоразумения, символы и опускаются.

Пример 3. Операторная схема

описывает следующий «процесс вычисления». Начинает работу ма­шина . Если она заканчивает работу в состоянии , то начинает работать машина , а по окончании работы машины вновь «вы­полняет работу» машина . Если же машина останавливается в некотором заключительном состоянии, отличном от то «работу продолжает» машина Если приходит в заключительное состо­яние , то начинает работу машина ; если же заканчивает ра­боту в некотором заключительном состоянии, отличном от , то «работу продолжает» машина . Если машина когда-либо оста­новится, то процесс вычисления на этом заканчивается.