Логические и арифметические основы и принципы работы ЭВМ

       

Основные положения машины Тьюринга


  1. Машина Тьюринга (рис.10.1) имеет конечное число знаков si, образующих внешний алфавит, в котором кодируются сведения, подаваемые в МТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак (s1), посылка которого в какую-либо ячейку стирает находившийся в ней знак и оставляет ее пустой.


    Рис. 10.1.  Структура машины Тьюринга

    В зависимости от поданной начальной информации

    (содержащихся на ленте внешней памяти знаков) возможны два случая:

    • после конечного числа тактов машина останавливается (имея информацию ?), подавая сигнал об остановке. В этом случае МТ применима к информации
      и перерабатывает ее в информацию ?;
    • остановка никогда не наступает. В этом случае МТ не применима к начальной информации
      .

  2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке ( R – вправо, L–влево, N– нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте t команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj.

  3. Логический блок МТ имеет конечное число состояний {qi} i=1..m.

    Знаки R, L, N, q1,..,qmобразуют внутренний алфавит машины.

    Переработанный знак sj, записываемый в просматриваемую ячейку, состояние, которое примет машина Тьюринга в следующем такте q(t+1) и выполняемая в данном такте операция перехода к следующей ячейке P(t+1) являются функцией анализируемого в данном такте символа и текущего состояния машины si и q(t):

    si(t+1)=f1(si,q(t)); q(t+1)=f2(si,q(t)); P(t+1)=f3(si,q(t)).

    Программа для МТ определяется тройкой {si, P, q}t.

    Пример записи программы вычисления логической функции "неравнозначность" для машины Тьюринга представлен ниже.

    Символ (si)Состояниеq1q2q3q4
    00, R, q20, N, q41, N, q40, N, q4
    11, R, q31, N, q40, N, q41, N, q4

    Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.

    Данная МТ применима к исходной информации. Останов – состояние q4. Значение si в ячейке y не меняется (сохраняется результат).

    Если программа для МТ будет определена таблицей переходов

    Символ (si)Состояниеq1q2q3q4
    00, R, q20, N, q41, N, q41, N, q4
    11, R, q31, N, q40, N, q40, N, q4

    то данная МТ будет не применима к исходной информации, поскольку в состоянии q4 значение si в ячейке y постоянно меняется на противоположное.



Содержание раздела