Введение в схемы, автоматы и алгоритмы


Задачи


Задача 9.1. Постройте м.Т. для функции копирования, не увеличивая исходный алфавит ?.

Задача 9.2. Постройте программу м.Т., которая выполняла бы перенос непустого слова в заданное место ленты, т.е. для любого слова w

(? \ {
})* и n > 0 выполняла преобразование конфигураций:
 q_1w \wedge^n \#\ \vdash^*\ \wedge^n q_2\#w\ .

Задача 9.3. Достройте программу м.Т.

{\cal M}^\prime\
из леммы 9.1 на этапах 3 и 4.

Задача 9.4. Докажите, что односторонняя м.Т.

{\cal M}^\prime,\
построенная в лемме 9.2, корректно моделирует исходную м.Т.
{\cal M}.

Задача 9.5. Другой, по сравнению с конструкцией леммы 9.2, подход к моделированию двухсторонней ленты на односторонней заключается в том, чтобы содержимое правой полуленты

\cal M\
хранить в четных ячейках
\cal M^\prime,\
а содержимое левой полуленты - в нечетных, поместив в 1-ю ячейку специальный маркер. Постройте программу, реализующую этот подход (ее достоинство - увеличение алфавита ленты всего на 1 символ).

Задача 9.6. Достройте программу м.Т.

\cal M
из леммы 9.4 на этапах 1, 3 и 5.

Задача 9.7. Построить программы машин Тьюринга, вычисляющих следующие функции.

  • Перевод из двоичной системы в унарную: fbu(n(2))= |n.
  • Сложение и вычитание в двоичной системе: sum(n*m)=n+m и
    sub(n*m)= n \dot - m,\ ( \dot -
    совпадает с - при n
    m и
    n \dot - m =0
    при m > n).
  • Умножение в двоичной системе: mul(n*m)= n ? m. ( Реализуйте алгоритм умножения "в столбик".)
  • Возведение в степень: exp(n*m)= nm.
  • Извлечение квадратного корня:
    sqr(n) =\lfloor\sqrt{n}\rfloor
    .
  • Логарифмирование: log(n)=
    log2n
    .
  • Деление:
    div(n*m) =\lfloor \frac{n}{ m} \rfloor\ (m \neq 0).
  • Остаток от деления: rest(n*m) = n mod m.
  • Функция выбора аргумента:
    I_m^n(|^{x_1}*|^{x_2}*\ldots *|^{x_n})= |^{x_m}\ \ (1\leq m \leq n)
    .

Задача 9.8. Используя машины Тьюринга из предыдущей задачи, построить программы машин Тьюринга, вычисляющих следующие функции.

  1. \begin{array}{lll} f_1(x, y)& =& \left \{\begin{array}{ll} x^2y^3, & \mbox{ если }\ x < y \\ \lfloor (x+y)/2 \rfloor , & \mbox{ в противном случае} \end{array} \right. \\ \end{array}

  2.  \begin{array}{lll} f_2(x, y)& = &\left \{\begin{array}{ll} \lfloor \sqrt{x}\ \rfloor , & \mbox{ если } x+1 \geq y \\ 2(x +y), & \mbox{ в противном случае} \end{array} \right. \\ \end{array}

  3.  \begin{array}{lll} f_3(x, y)& = &\left \{\begin{array}{ll} \lfloor \log_2 (1+ \lfloor \frac{x}{ y} \rfloor)\ \rfloor, & \mbox{ если } x > 2 y\\ xy, & \mbox{ в противном случае} \end{array} \right. \\ \end{array}

  4.  \begin{array}{lll} f(x, y)& = &\left \{\begin{array}{ll} \lfloor \sqrt{x}\ \rfloor , & \mbox{ если } 2x \geq y \\ (x\ mod\ y), & \mbox{ в противном случае} \end{array} \right. \\ \end{array}

Задача 9.9. Докажите, что всякую арифметическую функцию f(x), вычислимую на некоторой м. Т. M = <Q, ?, P,q0, qf>, можно также вычислить на м. Т. M',, алфавит ленты которой содержит лишь два символа

и |. (Указание: используйте для моделирования одного символа из ? блок из нескольких подряд идущих ячеек, содержащих его код в алфавите {
, , | }) и замените каждую команду M группой команд, обрабатывающих соответствующий блок ячеек).




- Начало -  - Назад -  - Вперед -



Книжный магазин