 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Пример 6
Рис. 3.6. Диаграмма переходов машины 
Машина, диаграмма которой приведена на рис. 3.6, – это машина Т+(Ткоп). Она вычисляет функцию f(x)=2x для 
. При том машина Ткоп строит двухкомпонентный вектор, а Т+ вычисляет функцию от двух переменных.
Для удобства последующих построений установим следующий важный факт.
Теорема 8. Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой. Иначе говоря, для любой машины Тьюринга Т существует эквивалентная ей машина TR с правой полулентой (аналогичная теорема формулируется для левой полуленты).
Рассмотрим теперь вычисление предикатов на машинах Тьюринга. Говорят, что машина Тьюринга вычисляет предикат 
(
– слово в 
), если 
, где 
Т, когда истинно, и 
F, когда ложно. Если не определен, то машина Тьюринга не останавливается. При обычном вычислении предиката уничтожается , что не всегда удобно, особенно если после Т должна работать другая машина. Поэтому введем понятие вычисления с восстановлением. Говорят, что машина Тьюринга вычисляет с восстановлением, если 
.
Лемма. Если существует машина Тьюринга (
), вычисляющая , то существует и 
, вычисляющая с восстановлением.
Доказательство. Вычисление с восстановлением можно представить следующей последовательностью конфигураций:
.
Первая часть этой последовательности реализуется машиной Ткоп; вторая – простым сдвигом головки до маркера *; третья – машиной ТR, вычисляющей на правой полуленте(одного копирования мало для восстановления, так как копию может испортить основная машина Т, нужна машина, не заходящая влево от ); четвертая – переносом 
в крайнее левое положение. Машина Т является композицией указанных четырех машин.
Поиск по сайту: