Математическая логика и теория алгоритмов. Стенюшкина В.А. - 61 стр.

     Доказательство следует из построения общерекурсивных функций, не яв-
ляющихся примитивно рекурсивными. Примером такой функции является фун-
кция Аккермана /3/.

       2.2 Регистровые машины. Машина Тьюринга

      Регистр – это типовой блок в ЭВМ, используемый для хранения одного
машинного слова, а также для некоторых манипуляций с этим словом. Регист-
ры всегда входят в состав арифметического устройства, устройства управления,
памяти ЭВМ и многие другие блоки. Регистр состоит из линейной цепочки от-
дельных разрядов, каждый из которых может хранить один бит информации. В
зависимости от того, как работают эти цепи, выделяются много типов регист-
ров: адресный, буферный, индексный, регистр команды и другие. Наиболее ва-
жными моделями вычислительных устройств регистрового типа являются ма-
шина с произвольным доступом к памяти (РАМ – равнодоступная адресная
машина) и машина Тьюринга (МТ). В ходе развития теории алгоритмов у А.
Тьюринга (1936) возникла концепция точного эквивалента для интуитивного
представления об алгоритме в виде абстрактной вычислительной машины. Да-
дим версию машины Тьюринга, восходящую к Э. Посту. Машина Тьюринга со-
держит следующие части (рисунок 2.1).
      1 ) Внешняя память – конечная лента, разбитая на конечное число ячеек.

           aj1     aj2      …        ajk      …          …          ajr
                                     qi

                                      Рисунок 2.1

       В процессе работы машины к существующим ячейкам машина может
пристраивать новые ячейки, так что лента может считаться потенциально нео-
граниченной в обе стороны. Каждая ячейка ленты может находиться в одном из
конечного множества состояний. Совокупность их называется внешним алфа-
витом А={а0,а1,…,аm}. Пустые состояния обозначаются а0. В процессе работы
машины ячейки ленты могут изменять свои состояния. Просмотр ленты осуще-
ствляется слева направо. В каждый такт времени лента имеет некоторую длину
r, то есть r ячеек. Состояние ленты описывается словом aj1 aj2 … ajk …ajr, где aj1
– состояние первой слева ячейки, aj2 – второй и т.д. Пустые символы слева и
справа можно опускать.
       2) Внутренняя память машины – устройство, о котором известно, что в
каждый такт времени оно находится в некотором состоянии. Алфавит внутрен-
них состояний, или внутренний алфавит Q = q0,q1,…,qn, где q0 – стоп-символ,
или символ заключительного состояния, q1, как правило, - символ начального
состояния.
        3) Указатель – устройство, которое может перемещаться вдоль ленты так,
что в каждый такт времени оно указывает на определенную ячейку ленты.