Вопросы экзаменатора (мат. логика и теория алгоритмов)

[Wynardtage]

На экзамене по мат. логике и теории алгоритмов задавались интересные вопросы... Приведу часть из них, постараюсь привести дословно.

1. Про машину Тьюринга. Путь есть алфавит $ A = \{a_0,\ \dots,\ a_n\} $, есть множество состояний $ Q = \{q_0,\ \dots,\ q_m\} $. Вопрос экзаменатора: «Сколько существует машин Тьюринга для данных множеств?» (слова «для данных множеств» могут быть неточными). Мой ответ был

$$ 3 (n + 1)^2 (m + 1)^2 $$

, т.к. кол-во элементов матрицы состояний содержит $ (n + 1) (m + 1) $ ячеек, а каждая ячейка матрицы может быть заполнена $ 3 (n + 1) (m + 1) $ способами (3 — кол-во возможных движений головки по ленте — влево, вправо, остаться на месте). В итоге матрицу можно заполнить

$$ 3 (n + 1)^2 (m + 1)^2 $$

способами. Но экзаменатор сказал, что это неверно, правильный ответ

$$ [3 (n + 1) (m + 1)]^{(n + 1)(m + 1)} $$

(вроде так). Как он получил такое число?.. Машина Тьюринга определяется только матрицей состояний, так?

2. Про теорему Яблонского, где говорится, что $ \forall f(x_1,\ \dots,\ x_n) \in P_k $ представима в виде многочлена по модулю $ k $ тогда и только тогда, когда $ k $ — простое. Т.е. вопрос, связанный с k-значной логикой. Вопрос экзаменатора: «А как определить представима ли функция в виде многочлена, если $ k $ не является простым?». А действительно — как?

3. Вопрос экзаменатора: «Сколько существует биективных функций в k-значной логике?». Вопрос привожу со слов одногруппника. Я не понимаю самого вопроса: биекция между чем и чем?

4. Как найти, например, $ | A \cap M | $, где $ A $ — класс афинных булевых функций, а $ M $ — класс монотонных булевых функций?

Буду благодарен за какие-то подсказки.

[cyb12]

2. Есть много разных способов. Если $k$ -- составное, то система $\{0,\ldots,k-1,x+y,x\cdot y\}$ не является полной в $P_k.$ То есть существуют функции, которые не представимы полиномом, например $j_0(x)=\begin{cases}1, \text{если }x = 0,\\0, \text{если }x\neq 0\end{cases}$ (именно эту функцию обычно строят в доказательстве). К таким функциям и надо пытаться сводить данную $f(x_1,\ldots,x_n)$ , если есть предположение о невозможности представления полиномом. Например, рассмотрим $f(x)=5J_7(x)$ в $P_{24},$ где $J_7(x)=\begin{cases}k-1=23, \text{если }x = 7,\\0, \text{если }x\neq 7.\end{cases}$ Пусть $f(x)$ задается полиномом по $\mod$ 24. Тогда полиномом задается и функция $5\cdot f(x)=J_7(x)$ (это нетрудно проверить), а тогда и $J_0(x)=J_7(x+7)$ -- тоже полиномом можно задать. Но тогда и $j_0(x)=(k-1)J_0(x)$ задавалось бы полиномом, противоречие.

Так же можно воспользоваться методом сведения к заведомо полным системам. Например, как доказать, что функция $max(x,y)$ не задается полиномом при составном $k$? Действительно, пусть задается. Но тогда, так как $\overline{x}=x+1$ -- полином, а система Поста $\{max(x,y),\overline{x}\}$ полна в $P_k,$ то любая функция в $P_k$ задается полиномом, но это не так.

Для некоторых функций, наоборот, можно явно выписать многочлен, которым они представляются. Это можно сделать, например, методом неопределенных коэффициентов (по значениям функции строится система уравнений для коэффициентов полинома, любое решение которой задает многочлен, если же решения нет, то и полиномом функция не представима).

[Xaositect]

Wynardtage в сообщении #396772 писал(а):

Как он получил такое число?..

Комбинаторика, правило умножения. $(n+1)(m+1)$ ячеек, в каждой $3(n+1)(m+1)$ варианта. 1 ячейка - $3(n+1)(m+1)$ варианта, 2 ячейки - $\left[3(n+1)(m+1)\right]^2$, 3 ячейки - $\left[3(n+1)(m+1)\right]^3$...

[cyb12]

Wynardtage в сообщении #396772 писал(а):

1. Про машину Тьюринга. Путь есть алфавит $ A = \{a_0,\ \dots,\ a_n\} $, есть множество состояний $ Q = \{q_0,\ \dots,\ q_m\} $. Вопрос экзаменатора: «Сколько существует машин Тьюринга для данных множеств?» (слова «для данных множеств» могут быть неточными). Мой ответ был

$$ 3 (n + 1)^2 (m + 1)^2 $$

, т.к. кол-во элементов матрицы состояний содержит $ (n + 1) (m + 1) $ ячеек, а каждая ячейка матрицы может быть заполнена $ 3 (n + 1) (m + 1) $ способами (3 — кол-во возможных движений головки по ленте — влево, вправо, остаться на месте). В итоге матрицу можно заполнить

$$ 3 (n + 1)^2 (m + 1)^2 $$

способами. Но экзаменатор сказал, что это неверно, правильный ответ

$$ [3 (n + 1) (m + 1)]^{(n + 1)(m + 1)} $$

(вроде так). Как он получил такое число?.. Машина Тьюринга определяется только матрицей состояний, так?

Да, Вы правы, МТ определяется своей программой. Но если каждую ячейку можно заполнить $r$ способами, а всего их $(n+1)(m+1),$ то число различных матриц = число слов длины $(n+1)(m+1)$ в алфавите из $r$ символов - то есть $r^{(n+1)(m+1)},$ и экзаменатор прав.

[Xaositect]

Wynardtage в сообщении #396772 писал(а):

3. Вопрос экзаменатора: «Сколько существует биективных функций в k-значной логике?». Вопрос привожу со слов одногруппника. Я не понимаю самого вопроса: биекция между чем и чем?

Между $E_k$ и $E_k$, очевидно. Это если спрашивалось про биективные, а не про бинарные. :)

-- Сб янв 08, 2011 21:23:30 --

Wynardtage в сообщении #396772 писал(а):

4. Как найти, например, $ | A \cap M | $, где $ A $ — класс афинных булевых функций, а $ M $ — класс монотонных булевых функций?

По определению. Выбрать из всех аффинных функций монотонные. Для этого выписать все афинные функции для $n\leq 3$, отметить среди них монотонные, догадаться, как сформулировать общее свойство и доказать его.

-- Сб янв 08, 2011 21:25:46 --

Wynardtage в сообщении #396772 писал(а):

Вопрос экзаменатора: «А как определить представима ли функция в виде многочлена, если не является простым?». А действительно — как?

Ну как вариант - перебрать все полиномы от такого же кол-ва переменных и сравнить их с функцией :)

[Wynardtage]

Извиняюсь, что долго не отвечал.

За первые два пункта спасибо Xaositect и cyb12.

3-й пункт: $ k ! $ значит?

4-й пункт: у аффинных б.ф. вроде бы первые $ \frac{n}{2} $ значений — нули, а затем — единицы (проверил программой, может ошибся), таким образом все аффинные — монотонные, т.е. $ | A \cap M | = | A | = 2^{n + 1} $. Верно?

[Wynardtage]

Нет, я вру. $ | A \cap M | = 2 $. Монотонными функциями получаются только функции-константы:

$$ \begin{array}{c} f(x_1, x_2) = 0 \oplus 0 \cdot x_1 \oplus 0 \cdot x_2\\ 0 \oplus 0 \cdot 0 \oplus 0 \cdot 0 = 0 \\ 0 \oplus 0 \cdot 0 \oplus 0 \cdot 1 = 0 \\ 0 \oplus 0 \cdot 1 \oplus 0 \cdot 0 = 0 \\ 0 \oplus 0 \cdot 1 \oplus 0 \cdot 1 = 0 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 0 \oplus 0 \cdot x_1 \oplus 1 \cdot x_2\\ 0 \oplus 0 \cdot 0 \oplus 1 \cdot 0 = 0 \\ 0 \oplus 0 \cdot 0 \oplus 1 \cdot 1 = 1 \\ 0 \oplus 0 \cdot 1 \oplus 1 \cdot 0 = 1 \\ 0 \oplus 0 \cdot 1 \oplus 1 \cdot 1 = 0 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 0 \oplus 1 \cdot x_1 \oplus 0 \cdot x_2\\ 0 \oplus 1 \cdot 0 \oplus 0 \cdot 0 = 0 \\ 0 \oplus 1 \cdot 0 \oplus 0 \cdot 1 = 0 \\ 0 \oplus 1 \cdot 1 \oplus 0 \cdot 0 = 1 \\ 0 \oplus 1 \cdot 1 \oplus 0 \cdot 1 = 0 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 0 \oplus 1 \cdot x_1 \oplus 1 \cdot x_2\\ 0 \oplus 1 \cdot 0 \oplus 1 \cdot 0 = 0 \\ 0 \oplus 1 \cdot 0 \oplus 1 \cdot 1 = 1 \\ 0 \oplus 1 \cdot 1 \oplus 1 \cdot 0 = 0 \\ 0 \oplus 1 \cdot 1 \oplus 1 \cdot 1 = 0 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 1 \oplus 0 \cdot x_1 \oplus 0 \cdot x_2\\ 1 \oplus 0 \cdot 0 \oplus 0 \cdot 0 = 1 \\ 1 \oplus 0 \cdot 0 \oplus 0 \cdot 1 = 1 \\ 1 \oplus 0 \cdot 1 \oplus 0 \cdot 0 = 1 \\ 1 \oplus 0 \cdot 1 \oplus 0 \cdot 1 = 1 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 1 \oplus 0 \cdot x_1 \oplus 1 \cdot x_2\\ 1 \oplus 0 \cdot 0 \oplus 1 \cdot 0 = 1 \\ 1 \oplus 0 \cdot 0 \oplus 1 \cdot 1 = 0 \\ 1 \oplus 0 \cdot 1 \oplus 1 \cdot 0 = 0 \\ 1 \oplus 0 \cdot 1 \oplus 1 \cdot 1 = 1 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 1 \oplus 1 \cdot x_1 \oplus 0 \cdot x_2\\ 1 \oplus 1 \cdot 0 \oplus 0 \cdot 0 = 1 \\ 1 \oplus 1 \cdot 0 \oplus 0 \cdot 1 = 1 \\ 1 \oplus 1 \cdot 1 \oplus 0 \cdot 0 = 0 \\ 1 \oplus 1 \cdot 1 \oplus 0 \cdot 1 = 1 \\ \end{array} $$

$$ \begin{array}{c} f(x_1, x_2) = 1 \oplus 1 \cdot x_1 \oplus 1 \cdot x_2\\ 1 \oplus 1 \cdot 0 \oplus 1 \cdot 0 = 1 \\ 1 \oplus 1 \cdot 0 \oplus 1 \cdot 1 = 0 \\ 1 \oplus 1 \cdot 1 \oplus 1 \cdot 0 = 1 \\ 1 \oplus 1 \cdot 1 \oplus 1 \cdot 1 = 1 \\ \end{array} $$

От количества аргументов не зависит.

[Xaositect]

Wynardtage в сообщении #403679 писал(а):

3-й пункт: $k!$ значит?

Да.

Wynardtage в сообщении #403730 писал(а):

Монотонными функциями получаются только функции-константы

А как же тождественная функция $x$? У Вас ошибка в табличке.
С учетом ее верно, но это надо доказать. "Пусть аффинная функция существенно зависит от более чем одной переменной. Тогда можно подобрать два набора, на которых монотонность нарушается" И описываете эти наборы.