Математическая логика и теория алгоритмов. Сергиевская И.М. - 47 стр.

6) f ( x1 , x2 , x3 ) = x13 + 3 x2 .
7) f ( x1 , x2 , x3 ) = 2 x1 + x2 .
8) f ( x1 , x2 , x3 ) = 2( x2 − x1 ) .
9) f ( x1 , x2 , x3 ) = x1x2 .
         f ( x1 , x2 , x3 ) = x1 ( x2 − 1) .
                                         2
10)

В Ответы и указания.
В Содержание.




Глава 9. Машины Тьюринга.

        Машина Тьюринга – это модель алгоритма, которая иллюстрирует процессы,
происходящие при реализации алгоритма. Машина Тьюринга                    является
гипотетической машиной. Ее составляют следующие компоненты.

• Управляющее устройство, которое в каждый данный момент времени может
  находиться в одном и только одном из некоторого множества состояний.
  Состояния обозначаются буквами так называемого внутреннего алфавита
  Q = {q0 , q1 ,K, q m }. Состояние q1 , как правило, считают начальным состоянием,
  а состояние q0 – конечным (заключительным). Во внутренний алфавит
  включают также символы сдвига : R – вправо, L – влево, E – на месте.

• Лента, разделенная на ячейки и предполающаяся потенциально бесконечной в
  обе стороны (имеется в виду, что в каждый момент времени лента содержит
  конечное число ячеек, но при необходимости число ячеек можно увеличивать). В
  каждой ячейке может быть записан один и только один символ некоторого
  внешнего алфавита A = {a0 , a1 ,K, an }. Символ a0 принято считать пустым
  символом. Он обозначает пустую ячейку. По умолчанию, во всех ячейках, в
  которых не записаны символы a1 , a2 ,…, an , записан символ a0 . В данной главе в
  качестве внешнего алфавита мы будем рассматривать алфавит E = {0,1}, 0
  соответствует пустому символу.

• Считывающая и пишущая головка, которая в каждый данный момент времени
  обозревает одну ячейку.



                                               52