lekcii4 (Лекции), страница 5

Но поскольку при нормированном вычислении часть ленты, расположенная левее несобственной буквы Л„не»осредственио предшествующей первому аргументу функции 1т, не участвует в вычислениях и не влияет на работу машины Ть, то эта часть ленты может быть отрезана. При этом работа машины Т > не изменится.

Теорема доказана. Теорема 2.4.4 позволяет ограничиться рассмотрением машин Тьюринга с лентой, бесконечной только с правого конца, а с левого ограниченной. Если вычисления нормированы, то проблемы перехода за край ленты не возникает, ь> 2.5.5 Предикаты, вычислимые ио Тьюрингу В математической логике важную роль играет понятие предиката. Примером предиката может служить конструкция «>л умеет нрограммировать», где <в — переменная со значениями «Иванов», «Петров», «Сидорова» и т. д. Подставляя значения >и в предикат. мы будем гюлучать высказывания «Иванов умеет программировать», «Петров умеет программировать» и т.

д., которые представляют одно из двух логических значений: И (истина) и Л (ложь) в зависимости от квалификации Иванова, Петрова, Сидоровой и др. Если обозначить рассмотрешпий предикат черсз р(т) и предположить, что Петров умеет программировать. а, Иьанов не умеет. то 1>(Иванов) = .!!, р(Петров) - И. Лпа:>огично конструкция .х умеет д», где х переменная со значениями «Иванов, «Петров» и т.д., а д переменная со значениями «программировать», «оглаживаться», «петь», «свистеть» и т.д., задает предикат р(х, д) от двух переменных х и д. Если Иванов г>рограммист, а Петров эстрадный певец, то р(Иванов, программировать) — И, р (Петров, отлаживаться) Л, р(Петров, свистеть) И и т.д.

Таким образом, предикат 7>(т>,хз,....,х„) опр<',деляется ка,к функция р: (А*,)" !И, Л). В случае и = ! предикат называют свойством, в случае и = 2, 3,... прсдикат задаст п-арное отношение. Предикаты >пироко применяются при описании алгоритмов (в частности, машин Тьюринга). Естественно, что в этом случае требуется, чтооы предикат сам описывался посредством алгоритма, т.е. был вычислимым. Понятия предиката, определяемого машиной Тьюринга, предиката, вычислимого и<> Тьюрингу, и прсдиката, нормированно вычисли- мого по Тьк>рингу, определяются аналогично соответствующим понятиям лля функций (см.

п.2.4.3 и п.2.4А). Приведем определение пр<диката, нормированно вычислимого по 78 Тьюр ингу. Определение 2.5.6. Предикат р: (А,*)"' — ~ (И,Л) называется нормированно вычислимым по Тьюрингу (1!ВТепредикатом), если существует МТ Тр с рабочим алфавитом А, = А, 0 (И, Л), которая вычисляет р (см, определение 2А,З) и при этом удовлетворяет следукицим условиям: 1. сели Х = (им иа, .., и„) ф 77еДр), то мапшна, Т„после применения к Х никогда, нс остапа,вливается; 2.

если Х = (иа, и7,... и„) Е 1де7'(р), и р(иь и7,... и„) =- И, то 7'р [ЛвЛи1 Лиа...Ли,„(Л)Л >==~' [ЛвЛи7Лиа... Ли„ЛИ(Л)Л >, = е А„* 3. если Х = (и,, и7,... и„) Е Ое 1(р), и р(п;„и7..., . и.„) — Л, то 7'„ [Л-Ли| Лиа...Ли„(Л)Л >==~* [Л=Ли;Лиг... Ли„ЛЛ(Л)Л >, . Е А,*, Согласно теореме 2.4.3 любой ВТ вЂ” предикат является НВТ вЂ” предикатом. Лекция 11 2.6 Теоремы о сочетаниях алгоритмов '1еоремы о сочетаниях алгоритмов обосновывают использование уже сконструированных МТ при конструировании новых МТ.

Вместе с тем они определяют правила, которые необходимо соблюдать при объединении нескольких МТ в одну, более сложную МТ. 2.6.1 Теорема о композиции Теорема 2.6.1. (О композиции) Пусть и-мгстная функция г': (А„*)" — ~ А,* определяется равенством: 7'(иьиг; .,'и„) = 6(д7(им ив,, и„),да(и,,иг;, ип):.,д„„(им иг ...,и„)), где д;: (А*,)"' — ~ А„* (! = 1,2,..., т) и 6: (А,') — ~ А,* — ВТ-функции. Тогда, !' является Вт-функцией, причем МТ, вычисляющая функцию !". может быть эффективно построена из МТ, вычисляющих функпии д, (ю'.

= 1, 2,..., 7п) и 6. Замечание, В частном случае, когда т = 1, и = 1, функция 7" = 6(д(1с)) называется суперпозицией функций д и 6. г Из теоремы 4.3,3 следует, что ВТ-функции д,, (г = 1,2,...,7п) и 6 являются НВ"1'- функциями. Пусть 7' (! = 1,2,....т) и т, -- МТ, реализующие нормированное вычисление функций д, (! = 1,2...., т) и 6 соответственно. Построим МТ К„, реализующую действие к„ [Ли7,Л7га... Лю„(Л)Л >==~' [ЛийЛыа...

Ли~„Л7е1(Л)Л > 79 .