Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Гипотетические машины - часть 4


(1)        Конечное, полное вычисление (s0, t, #, £) à…à(Se,Г, #, £)

существует точно тогда, когда функция f определена для t и справедливо

f(t) = k,    где k Î Т*.

(2)        Бесконечное вычисление

(s0, t, #, e) à...

существует точно тогда, когда функция f для аргумента t не определена.

Тьюринг-вычислимость может быть перенесена на частичные функции

f: N” à N

путем выбора конкретного представления чисел.

Ниже приводится ряд простых функций, которые являются Т-вычислимыми:

(1)        Константы. Отображения с: N” ->

N, для которых существует b Î N с c(x1, ..., xn) = b для всех x1, ..., xn Î N.

(2)        Функция следующего числа

succ: N àN,   где succ(n) = n+l.

(3)        Всюду определенная функция предыдущего числа

      pre: N ->    N, где

pre(n)=[ 0,         если n = 0; n-1  иначе].

(4)        Частично определенная функция предыдущего числа pred: N à N где pred(n)=[n—1, если n>0; не определено   иначе].

Это примеры для очень простых функций, которые являются Т-вычислимыми.

Более сложные примеры можно получить путем построения Т-машин из заданных. Например, можно построить последовательную композицию Т-машин: пусть TM1 и TM2 - машины Тьюринга с одинаковыми множествами входных знаков Т, с начальными состояниями соответственно s1 и s2,

и пусть множества их состояний S1 и S2 дизъюнктивны. Построить новую Т-машину ТМ0 с множеством входных знаков Т, начальным состоянием s1, множеством состояний s0=S1ÈS2 и функцией переходов r0,специфированрой следующим образом:

r0(s,t)=[r1(s,t),sÎS1Ùr1(s,t)¹Æ;{(s2,t,¯)},sÎS1Ùr1(s,t)=Æ;r2(s,t),sÎS2]

Последовательная композиция двух Т-машин соответствует вычислению, при котором сначала работает машина TM1 с исходным заданным словом, а когда она завершает свою работу, запускается машина ТМ2, которая использует слово на ленте, порожденное машиной TM1. Так построенная Т-машина вычисляет композицию функций, которые вычисляются Т-машинами.




- Начало -  - Назад -  - Вперед -



Книжный магазин