Машина Тьюринга: какую функцию вычисляет?

[Anexroid]

Какую функцию $f(x)$ вычисляет машина Тьюринга $T$ со следующей программой команд
$q_10 \rightarrow q_20R, q_11 \rightarrow q_01, q_20 \rightarrow q_01, q_21 \rightarrow q_21R$
Задачник Лаврова и Максимовой, раздел машины Тьюринга, №1

Ответ знаю, как получить решение - нет.

Например, берем $f(0)$
Значит, на ленте получаем 0 и после преобразований получится 01
$f(1)$, исходный - 01, после преобразований 01 или 011? Если 011, ответ - функция x+1 получаем. Но я не могу понять почему мы получаем 011, а не 01

[Maslov]

А как у Вас 01 из 01 получается?

Начальное состояние: $q_1010$
После первого шага ($q_10 \to q_20R$): $0q_210$

Как дальше будет работать машина?

[Anexroid]

А почему начальное $q_1010$ а не $q_101$?

В вашем случае, дальше будет $(q_21 \rightarrow q_21R):01q_21$ и получаем верный ответ.

[Maslov]

Прочитайте вступительную часть раздела "Машины Тьюринга" в задачнике. Обратите внимание на определение "Говорим, что машина Тьюринга вычисляет n-местную частичную числовую функцию ..." и на то, как в этом определении задаются аргументы функции.

[Anexroid]

Спасибо, кажется понял

-- Ср окт 05, 2011 00:58:32 --

Но в таком случае мне совсем не понятен следующий номер.
Программа $q_10 \rightarrow q_00$
Какие функции $f_1(x), f_2(x_1,x_2), ..., f_n(x_1, ..., x_n)$ реализует эта функция.

По сути, данная машина никак не меняет входные данные. Почему же тогда ответ $x, x_1 + x_2, ..., x_1 + ... x_n$ ?

-- Ср окт 05, 2011 01:00:31 --

Или ответ - это просто количество единичек в результате? Если так, то понятно.

[Maslov]

Anexroid в сообщении #489545 писал(а):

Или ответ - это просто количество единичек в результате?

Да.

Еще раз обращаю Ваше внимание на уже упоминавшееся определение:

Цитата:

... при этом слово $Aq_0B$ содержит $f(x_1, ..., x_n)$ вхождений символа $1$.