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

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

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

Регистровые машины

Регистровые машины (короче, R-машины) являются гипотетическими машинами, которые по своей структуре сильнее приближаются к употребительным в настоящее время ЭВМ. Рассматриваются R-машины с конечном числом регистров, однако с неограниченным их размером, чтобы регистры могли принимать сколь угодно большие натуральные числа.

Регистровая машина с п регистрами (короче, n-R-машина) имеет n регистров для хранения неограниченно больших натуральных чисел и программу. Множество программ для n-R-машины определим индуктивно следующим образом:

(0) е есть программа (пустая программа);

(1)        succj есть программа (1£i£n);

(2)        predi есть программа (1£i£n);

(3)        если mi и M2 - программы, то M1; М2 также есть программа;

(4)        если М - программа, то while(M) также есть программа (1 £ i £n).

Множество программ для n-R-машины обозначим через n-PROG.

Конфигурация n-R-машины состоит из пары

- (s, р) е N” х n-PROG.

На множестве конфигураций специфицируется отношение переходов состояний —> следующими правилами:

(s, slicci) à ((s1, ..., si-i, si+l, si+i, ..., sn), e),

(s, predj,) -> ((s1, ..., sj-i, b, sj+1, ..., sn), e),

где

k=0, если si = 0, sj=0

si-l,sj-1 инач

Для конфигурации (s,e) следующая конфигурация не определена, поскольку E есть пустая программа.

Вычисление n-R-машины с исходной конкретизацией памяти s для программы р есть конечная или бесконечная последовательность конфигураций с c0 = (s, р) и для

i Î

N:

сi -> Ci+i.

Конфигурация с называется терминальной,

если не существует такой: конфигурации с

Для терминальной конфигурации с =( s, р) всегда р = e

Вычисление называется полным,

если последовательность ко^фигура-1 ций бесконечна или же она конечна и последняя конфигурация сk терминальна. Тогда n-R-машина с программой р вычисляет выход (результат) s для входа s.

Наряду с n-R-машинами рассматриваются также R-машины с неограниченным числом регистров, а также R-машины с командами перехода. Регистровые машины соответствуют простой форме while-программ, состоящих из операторов присваивания, условных операторов, последовательной композиции операторов и while-циклов.