 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Операции над машинами Тьюринга
Для понимания того, что конкретная машина решает данную задачу, возникает необходимость в содержательных пояснениях. Для того, чтобы сделать эти пояснения более формальными и точными, будем использовать блок-схемы и некоторые операции над машинами Тьюринга.
Теорема 7. Если функция 
и 
вычислимы по Тьюрингу, то их композиция 
также вычислима по Тьюрингу.
Доказательство. Пусть Т1 – машина, вычисляющая 
, а Т2 – машина, вычисляющая 
и множества их состояний соответственно 
и 
. Построим диаграмму переходов машины Т из диаграммы Т1 и Т2 следующим образом: отождествим начальную вершину 
диаграммы машины Т2 с конечной вершиной 
диаграммы машины Т1 (для систем команд это равносильно тому, что систему команд Т2 приписываем к системе команд Т1 и при этом в командах Т1 заменяем на ). Получим диаграмму с n1 + n2 – 1 состояниями. Начальным состоянием машины Т объявим 
, а заключительным – 
. Для простоты обозначений будем считать f1 и f2 числовыми функциями одной переменной.
Пусть f2(f1(x)) определена. Тогда 
и 
. Машина Т пройдет ту же последовательность конфигураций с той разницей, что вместо 
она перейдет в 
. Эта конфигурация является стандартной начальной конфигурацией для машины Т2, поэтому 
. Но так как все команды Т2 содержатся в Т, то 
и, следовательно, 
.
Если же f2(f1(x)) не определена, то Т1 или Т2 не остановится, а значит, и машина Т не остановится. Следовательно, машина Т вычисляет f2(f1(x)).
Построенную таким образом машину Т будем называть композицией машин Т1 и Т2 и обозначать Т2(Т1), а также изображать блок-схемой (рис. 3.5).
Рис. 3.5. Блок-схема композиции Т2(Т1)
Эта блок-схема всегда предполагает, что исходными данными машины Т2 являются результаты Т1. При этом они уже «готовы к употреблению», так как благодаря вычислимости (которая существенна при композиции) заключительная конфигурация Т1 легко превращается в стандартную начальную конфигурацию Т2.
Так как машина Тьюринга вектор над 
воспринимает как слово в алфавите 
, определение композиции и теорема 7 остается в силе, если Т1 и Т2 вычисляют функции от нескольких переменных. Важно лишь, чтобы данные для Т2 были в обусловленном виде подготовлены машиной Т1. Это хорошо видно на следующем примере.
Поиск по сайту: