Пусть машина Тьюринга M построена из следующих - Ответ на вопрос по любому предмету №1171064

Вопрос

Пусть машина Тьюринга 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#( Умн, Сум); par#( Коп* ; Сум , Пуст ); Зам(#,?); СумКакую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

• f(x) = 2x2 + 2x
• f(x) = x2 + 2x
• f(x) = x2 + x
• f(x) = 2x2 + x
• ни одну из выше перечисленных

Ответ