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


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


Эта конструкция может быть обобщена. Для этой цели определяется общая композиция для частичных функций. Пусть

g: N” à N,

hi: N” à N, 1<i<n, являются частичными функциями. Тогда функция

      f: Nnà N;

описанная ниже, определена через композицию

функций h1, ..., hn и g. Примененяется функция f для всех аргументов (x1, ..., хm) следующим образом;

      f(x1,...,xm)=g(h1(x1,...,xm),...,hn(x1,…,xm)),

      если для всех i, 1 £ i £ m,

применение функции hi(x1, ...,xm) определено и также                определено применение функции g к аргументам

(h1(x1, ..., xm), ..., hn(x1, ...,xm)). Функция f для аргументов (x1,...,хm)  не определена, если

·         хотя бы для одного i, 1 £  i £ m, значение функции hi(xi, ..., xm) не определено или

·         для всех i, 1£ i £ m, применение функции hi(x1, ..., хm) определено, но применениефункции g к аргументам

(h1(x1, ..., xm), ..., hn(x1, ..., xm)) не определено.

Тогда для функции f  пишется выражение g.[h1,..., hnJ.

Фнкция f является тотальной (т. е. всюду определенной), если все функции h1, ..., hn и g тотальны (всюду определены).

С помощью обобщения только что описанного вида композиции ТМ получается следующая теорема.

Теорема (обобщенная композиция ТМ). Если

g: NnàN

hi: N’”à N,      где 1£ i£ n,

есть Т-вычислимые частичные функции, то функция

f: N’”à N,

определенная через композицию функций h1,..., hn и g:

f=g.[h1,..., hn],

также является Т-вычислимой функцией.

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

Имеются и другие варианты машин Тьюринга, например:

·         машины с лентой, бесконечной только с одной стороны (и конечной лентой с другой стороны);

·         Т-машины со многими лентами.




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



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