Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Гипотетические машины - часть 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-циклов.
