Главная / Введение в схемы, автоматы и алгоритмы / Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;
  • Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy ;
  • Пуст - не изменяет аргумент: w ⇐ w
  • с помощью операций последовательного и параллельного применения следующим образом:

    M = Коп# ; par#( Коп* ; Умн, Пуст ); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум

    Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

    вопрос

    Правильный ответ:

    f(x) = 2x2 + 2x
    f(x) = x2 + x
    f(x) = 2x2 + x
    f(x) = x2 + 2x
    ни одну из выше перечисленных
    Сложность вопроса
    50
    Сложность курса: Введение в схемы, автоматы и алгоритмы
    92
    Оценить вопрос
    Очень сложно
    Сложно
    Средне
    Легко
    Очень легко
    Комментарии:
    Аноним
    Это очень простецкий решебник по интуиту.
    16 окт 2018
    Аноним
    Это очень легкий решебник по интуиту.
    23 июн 2016
    Оставить комментарий
    Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.