Черный ящик

[Sicker]

Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Или точнее, его функцию отклика (ведь есть состояния, которые функционально изоморфны).
Я думаю так, можно рассмотреть все возможные конфигурации черных ящиков (их здесь вроде 72), и дать им случайную последовательность из нулей и единиц, длиной, скажем, 100 (а можно и 10, хм?), тогда те из них, которые дают такой же выход, что и наш исходный ящик, и будут его функциональными двойниками.
Можно рассмотреть гораздо более сложный пример со многими состояниями и откликами.
Есть ли какие-нибудь способы изучения таких черных ящиков?

[Dan B-Yallay]

Sicker в сообщении #1303061 писал(а):

Я думаю так, можно рассмотреть все возможные конфигурации черных ящиков (их здесь вроде 72),

Их 16.

Sicker в сообщении #1303061 писал(а):

и дать им случайную последовательность из нулей и единиц, длиной, скажем, 100 (а можно и 10, хм?)

Достаточно скормить 00110.

[Sicker]

Dan B-Yallay в сообщении #1303064 писал(а):

Их 16.

3*3*4*4*2

Dan B-Yallay в сообщении #1303064 писал(а):

Достаточно скормить 00110.

Докажите)

-- 11.04.2018, 03:38 --

3 - число переходов для одного состояния, 4 - число выходных функций для одного состояния, 2 - начальное состояние ящика.

-- 11.04.2018, 03:59 --

на двойку не надо домножать)

[mihaild]

Dan B-Yallay в сообщении #1303064 писал(а):

Достаточно скормить 00110.

Если автомат по $0$ остается в текущем состоянии, а по $1$ переходит в другое, изначально находится в состоянии $1$, то вы не узнаете, что он выдает, получив $0$ в состоянии $2$.

[Sicker]

Dan B-Yallay
Вот опровержение вашего примера
ЧЯ №1
для первого состояния
вход - переход в другое состояние или нет (1 или 0) - выходное значение
0-1-0
1-1-1
для второго состояния
0-1-0
1-1-1
ЧЯ №2
1 состояние
0-1-0
1-1-0
2 состояние
0-1-0
1-0-1
Как мы видим, они на вход 00110 выдают эту же строку, только первый при подаче первой 1 выдает 1, а второй 0

[Dan B-Yallay]

Sicker в сообщении #1303066 писал(а):

3*3*4*4*2

Проверим арифметику:

Sicker в сообщении #1303061 писал(а):

Пусть из любого состояния есть переход в другое.

Это означает, что y чёрного ящика переходы $1 \to 2$ и обратно $2 \to 1$ осуществляется:
а) либо при подаче на вход 0 и 0 соответственно,
б) либо 0 туда, 1 - обратно
в) либо 1 - туда, 0 - обратно
г) оба перехода при подаче единиц.

То есть, имеем 4 типа ящиков.

Теперь, при подаче на вход 0 каждый тип ящика может выдать 0 или 1. Аналогично с подачей на вход 1. Итого 16.

Укажите, какой из вариантов ящиков пропущен.

-- Вт апр 10, 2018 19:10:55 --

mihaild в сообщении #1303068 писал(а):

Если автомат по $0$ остается в текущем состоянии, а по $1$ переходит в другое, изначально находится в состоянии $1$, то вы не узнаете, что он выдает, получив $0$ в состоянии $2$.

Sicker в сообщении #1303069 писал(а):

Вот опровержение вашего примера

Сейчас посчитаю варианты и скажу мнение.

[Sicker]

Dan B-Yallay в сообщении #1303070 писал(а):

либо при подаче на вход 0 и 0 соответственно

Не понял, у нас вход один.
а) при подаче 0 переход в 0, при 1 - в 1
б) при 0 в 1, при 1 - в 0
в) при 0 в 1, при 1 в 1

Dan B-Yallay в сообщении #1303070 писал(а):

Теперь, при подаче на вход 0 каждый тип ящика может выдать 0 или 1. Аналогично с подачей на вход 1.

Итого 4
4*3=12
И не забываем про второе состояние, тогда суммарное число комбинаций 12*12

[Dan B-Yallay]

Sicker в сообщении #1303071 писал(а):

Не понял, у нас вход один.
а) при подаче 0 переход в 0, при 1 - в 1
б) при 0 в 1, при 1 - в 0
в) при 0 в 1, при 1 в 1

А вы рядом состояния автомата напишите, а то такое впечатление, что условиие как то не очень соблюдается:

Sicker в сообщении #1303061 писал(а):

Пусть из любого состояния есть переход в другое.

-- Вт апр 10, 2018 19:25:01 --

Dan B-Yallay в сообщении #1303064 писал(а):

Достаточно скормить 00110.

Признаю, что погорячился. Наверное надо последовательность чуть подлиннее но уж во всяком случае не 100 символов. Может, 001110 или 0011010 хватит?

[Sicker]

Dan B-Yallay в сообщении #1303072 писал(а):

А вы рядом состояния автомата напишите, а то такое впечатление, что условиие как то не очень соблюдается:

Пусть будет любое, 0 или 1, 0 - это оставаться на месте, 1 - переходить в соседнее состояние.

-- 11.04.2018, 04:33 --

Dan B-Yallay в сообщении #1303072 писал(а):

0011010

Подали, получили выход. У вас есть какой-нибудь алгоритм для выяснения устройства ящика?

[Dan B-Yallay]

Sicker в сообщении #1303071 писал(а):

Не понял, у нас вход один.

Так как с вашими обозначениями можно спутать вход 1 и состояние автомата 1, я использую для состояний буквы:

$$\begin{align*} 0: (P \to Q) & \qquad 0: (Q \to P)\\ 0: (P \to Q) & \qquad 1: (Q \to P)\\ 1: (P \to Q) & \qquad 0: (Q \to P)\\ 1: (P \to Q) & \qquad 1: (Q \to P) \end{align*}$$

Еще раз, укажите где вы видите ошибку или "недостачу". После этого можно двигаться далее.

-- Вт апр 10, 2018 19:41:46 --

Sicker в сообщении #1303073 писал(а):

Пусть будет любое, 0 или 1, 0 - это оставаться на месте, 1 - переходить в соседнее состояние.

Не понял...

[Sicker]

Dan B-Yallay
А почему у вас соседние повторяются, и где выход?

-- 11.04.2018, 04:43 --

Dan B-Yallay в сообщении #1303076 писал(а):

Не понял...

Обычная машина Тьюринга

-- 11.04.2018, 04:45 --

Dan B-Yallay
Может быть вы не учитываете, что функция перехода автомата из состояния в состояние еще зависит от текущего состояния.

[Dan B-Yallay]

Sicker в сообщении #1303077 писал(а):

А почему у вас соседние повторяются, и где выход?

Охоспади. Повторяю последний раз. Имеем автомат. У него два состояния $P, \ Q$ между которыми он обязан переключаться либо при подаче 0 либо подаче 1. И плевать сейчас на то, что он выдаeт на выходе -- разберёмся с этим позже.

Вопрос: переключается ли он из состояния $P$ в $Q$ при подаче на вход 0? Если да, то назовём его автоматом типа 0-х. Если не переключается, тогда он ОБЯЗАН переключаться при подаче на вход 1, и тогда назовём его автоматом типа 1-х.

Далее эти типы автоматов делятся на подтипы: переключается ли автомат типа 0-х обратно из $Q$ в $P$ при подаче на вход 0? Если да, тогда это автомат подтипа 0-0. Если нет, то он ОБЯЗАН быть автоматом подтипа 0-1. Аналогично с автоматами типа 1-х: они делятся на подтипы 1-0 и 1-1.

Итого 4 (под)типа автоматов: 0-0; 0-1; 1-0; 1-1. Согласны или нет?

Sicker в сообщении #1303077 писал(а):

Может быть вы не учитываете, что функция перехода автомата из состояния в состояние еще зависит от текущего состояния.

Укажите, где я это делаю, где не учитываю.

-- Вт апр 10, 2018 20:43:17 --

Sicker в сообщении #1303073 писал(а):

Подали, получили выход. У вас есть какой-нибудь алгоритм для выяснения устройства ящика?

То, насколько детально можно выяснить устройство автомата, зависит от выхода. А в том моём посте слово "достаточно" означает, что более длинные последовательности не дадут вам больше информации.

[Sicker]

Dan B-Yallay в сообщении #1303079 писал(а):

он обязан переключаться либо при подаче 0 либо подаче 1.

тут не исключающее либо.

Dan B-Yallay в сообщении #1303079 писал(а):

Вопрос: переключается ли он из состояния $P$ в $Q$ при подаче на вход 0? Если да, то назовём его автоматом типа 0-х.

А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа)
ну и дальше 3*3, а не 2*2)

-- 11.04.2018, 05:50 --

Хорошо, если я исключу требование переключаемости, тогда вы согласны что было бы 4*4 вариантов?

[Pavia]

Sicker

Sicker в сообщении #1303080 писал(а):

А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа)
ну и дальше 3*3, а не 2*2)

Идите учите матчасть. Вы сами написали что у вас 2 состояния и алфавит 2. Итого число переходов $2\cdot2=4$.
И возможных ящиков $2^4=16$

[Sicker]

Pavia в сообщении #1303081 писал(а):

Вы сами написали что у вас 2 состояния и алфавит 2. Итого число переходов $2\cdot2=4$.

Че за бред вы несете?. Вот все возможности (0 1) - (0 1), (0 1) - (1 0), (0 1) - (1 1) для одного состояния, вы согласны?