2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Черный ящик
Сообщение11.04.2018, 02:13 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 03:00 
Заслуженный участник
Аватара пользователя


11/12/05
7666
Diкий Запад
Sicker в сообщении #1303061 писал(а):
Я думаю так, можно рассмотреть все возможные конфигурации черных ящиков (их здесь вроде 72),
Их 16.
Sicker в сообщении #1303061 писал(а):
и дать им случайную последовательность из нулей и единиц, длиной, скажем, 100 (а можно и 10, хм?)
Достаточно скормить 00110.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 03:37 
Аватара пользователя


13/08/13
3441
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 --

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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:00 
Заслуженный участник
Аватара пользователя


16/07/14
2842
Москва
Dan B-Yallay в сообщении #1303064 писал(а):
Достаточно скормить 00110.
Если автомат по $0$ остается в текущем состоянии, а по $1$ переходит в другое, изначально находится в состоянии $1$, то вы не узнаете, что он выдает, получив $0$ в состоянии $2$.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:03 
Аватара пользователя


13/08/13
3441
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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:09 
Заслуженный участник
Аватара пользователя


11/12/05
7666
Diкий Запад
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 писал(а):
Вот опровержение вашего примера

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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:14 
Аватара пользователя


13/08/13
3441
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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:23 
Заслуженный участник
Аватара пользователя


11/12/05
7666
Diкий Запад
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 хватит?

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:32 
Аватара пользователя


13/08/13
3441
Dan B-Yallay в сообщении #1303072 писал(а):
А вы рядом состояния автомата напишите, а то такое впечатление, что условиие как то не очень соблюдается:

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

-- 11.04.2018, 04:33 --

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

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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:40 
Заслуженный участник
Аватара пользователя


11/12/05
7666
Diкий Запад
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 - переходить в соседнее состояние.
Не понял... :shock:

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 04:43 
Аватара пользователя


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

-- 11.04.2018, 04:43 --

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

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

-- 11.04.2018, 04:45 --

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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 05:04 
Заслуженный участник
Аватара пользователя


11/12/05
7666
Diкий Запад
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 писал(а):
Подали, получили выход. У вас есть какой-нибудь алгоритм для выяснения устройства ящика?
То, насколько детально можно выяснить устройство автомата, зависит от выхода. А в том моём посте слово "достаточно" означает, что более длинные последовательности не дадут вам больше информации.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 05:48 
Аватара пользователя


13/08/13
3441
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 вариантов?

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 06:00 
Аватара пользователя


31/10/08
982
Sicker
Sicker в сообщении #1303080 писал(а):
А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа)
ну и дальше 3*3, а не 2*2)

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

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 06:08 
Аватара пользователя


13/08/13
3441
Pavia в сообщении #1303081 писал(а):
Вы сами написали что у вас 2 состояния и алфавит 2. Итого число переходов $2\cdot2=4$.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 47 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group