Черный ящик

[Dan B-Yallay]

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

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

Разумеется, и уже это учтено выше.

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

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

Присоединяюсь к призыву: учите матчасть.

-- Вт апр 10, 2018 21:09:19 --

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

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

Бред сейчас несёте именно вы.

-- Вт апр 10, 2018 21:13:00 --

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

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

Даже с этим требованием число различных вариантов, как я написал сразу, равно 16, то есть 4*4. А без него вариантов будет поболее.

[Sicker]

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

Присоединяюсь к призыву: учите матчасть.

ссылку в студию.

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

Бред сейчас несёте именно вы.

(0 1) - (0 1) для состояния P означает, что при подаче 0 оно остается P, а при подаче 1 меняет его на Q, и так далее, что не понятного?

[Dan B-Yallay]

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

ссылку в студию.

Читайте сообщение от Pavia на предидущей стр.

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

(0 1) - (0 1) для состояния P означает, что при подаче 0 оно остается P, а при подаче 1 меняет его на Q, и так далее, что не понятного?

Либо вы пользyетесь моими обозначениями и тогда понимаете что они означают, либо вводите собственные, но тогда обьясняете что они означают. Иначе разговора не получается и BCE непонятно.

[Sicker]

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

Либо вы пользyетесь моими обозначениями и тогда понимаете что они означают, либо вводите собственные, но тогда обьясняете что они означают. Иначе разговора не получается и BCE непонятно.

Так объясните их.
Вот мои ((0 1) 0) - (0 1), ((0 1) 1) - (1 1)
Это один из автоматов, они означают, что если автомат находится в состоянии 0, то при подаче 0 он остается в 0, а при подаче 1 переходит в 1, а если находится в состоянии 1, то при подаче 0 или 1 переходит в 0 - состояние.
И таких 9 штук.

-- 11.04.2018, 06:30 --

третья цифра - номер состояния, первые две - возможные входы, последние две, первая из них реализуется при входе 0, вторая при входе 1.

-- 11.04.2018, 06:30 --

Да, первые две можно не писать
(0) - (0 1), (1) - (1 1)

[Dan B-Yallay]

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

Это один из автоматов, они означают, что если автомат находится в состоянии 0

Нет у вас такого состояния как 0. Нету:

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

Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2,

Я еще несколько постов назад предложил избавиться от неудобного и путающего обозначения. Даже предложил свои.
Тут, похоже дело безнадёжное. Спасибо за беседу.

[Sicker]

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

Я еще несколько постов назад предложил избавиться от неудобного и путающего обозначения. Даже предложил свои.

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

Так объясните их.

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

Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2,

Замените их на 0 и 1 тогда

-- 11.04.2018, 06:55 --

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

Тут, похоже дело безнадёжное.

Мне сейчас дико смешно от того, что кто-то из нас не может разобраться с такой фигней
Вы кстати, так и не ответили на мой вопрос в начале темы)

[Dan B-Yallay]

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

Замените их на 0 и 1 тогда

Хорошо, имеем автомат с двумя возможными состояниями 0,1 а также двумя различными входными данными также обозначенными 0 и 1. Tогда конструируем следующую таблицу:

$$ \begin{bmatrix} \text{Нач. сост } & \text{Вход } & \text{Выход } & \text{Посл Сост}\\ 0 & 0 & x_{00} & y_{00}\\ 0 & 1 & x_{01} & y_{01}\\ 1 & 0 & x_{10} & y_{10}\\ 1 & 1 & x_{11} & y_{11}\\ \end{bmatrix} $$

Произвольно задав значения 0 или 1 для всех выходных значений $x_{ij}$ и состояний $y_{ij}$ получим некоторую "машину Тьюринга". Очевидно, что таких вариантов $2^8=256$.
Это при условии, что снято требование об обязательном переходе между состояниями.

-- Вт апр 10, 2018 22:24:27 --

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

Вы кстати, так и не ответили на мой вопрос в начале темы)

Я не занимаюсь теоретическим программированием или реверс-инжинирингом поэтому не знаю ответа на вопрос о том, какие есть алгоритмы анализа подобных чёрных ящиков. Ждите других, более знающих участников.

-- Вт апр 10, 2018 23:09:39 --

Насчёт изначального требования перехода из одного состояния в другое:

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

Их 16.

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

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

В этом вы правы, получается больше чем 16. А именно $9*16=144$, если опять не вру. Похоже, мне тоже пора идти читать матчасть.

Всё, ухожу из темы.

[Yodine]

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

Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое.

****которые определяют по входящему сигналу (0 или 1)

входящий датчик один, по которому может быть получен сигнал 0 или 1
вход$=(0,1)$

***он имеет два внутренних состояния, $1$ и $2$,

состояние начальное$=(0,1)$

****будет на выходе (0 или 1)

выходящий датчик один, например экран, на котором может быть $0 $ или $1$
выход$=(0,1)$

****в какое состояние перейдет черный ящик

состояние конечное$=(0,1)$

<вход> <состояние_1> <выход> <состояние_2>
(0,1) x (0,1) x (0,1) x (0,1)

<вход> <состояние_1> <выход> <состояние_2>
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1

0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1

1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1

1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

16 вариантов

[Pavia]

Sicker
Извиняюсь не успел с утра написать ответ. И он получился довольно грубым. Но теория автоматов хорошо описана и формулы приведены. Если не в первом, то во-втором учебнике.

Для примера возьмем Трахтенброт Б. А., Барздинь Я. М.-Конечные автоматы (поведение и синтез)-Наука (1970)
на стр 17 в самом конце.

Цитата:

тогда матрица переходов может быть заполнена $k^{mk}$ способами, а матрица выходов $n^{mh}$ способами. Следовательно, общее число автоматов с заданными алфавитами, насчитывающими соответственно $k, m, n$ символов, в точности равно
$(kn)^{mk}$.

Определение автомата :

Конечным автоматом называется система $S = \{ Q,X, Y,\Psi,\Phi\}$, где
$X=\{x_1 ,...x_m \}$ - входной алфавит, $Q=\{q_1 ,...q_k \}$ -состояния автомата,
$Y=\{y_1 ,...y_n \}$- выходной алфавит, $\Psi$ - функция переходов, $\Phi$ -функция выходов.
Поскольку функции $\Psi$ и $\Phi$ определены на конечных множествах,
то их можно задавать таблицами, обычно две таблицы обьединяют в
одну $\Psi \times \Phi :Q\times X \rightarrow Q \times Y$, называемой таблицей переходов автомата. (рис 1.1).


\begin{tabular}{|l|r|r|} \hline & x1 & x2 \\ \hline q1 & q_*, y_* & q_*, y_* \\ \hline q2 & q_*, y_* & q_*, y_* \\ \hline \end{tabular}

Цитата:

тогда матрица переходов может быть заполнена $k^{mk}$ способами, а матрица выходов $n^{mh}$ способами. Следовательно, общее число автоматов с заданными алфавитами, насчитывающими соответственно $k, m, n$ символов, в точности равно
$(kn)^{mk}$.

Признаю что в предыдущем посте ошибся. Подставляем условия в формулу получаем (2*2)^(2*2)=256

Никаких троек.* - тут можно подискутировать но это лучше вынести в отдельная тему.

Что касается основного вопроса следует изучить цепи Маркова. Только на практике их почти не применяют. Предпочитают использовать нейронные сети которые с некоторой погрешностью аппроксимируют неизвестную функцию.

[Yodine]

Pavia сорри, кажется вы неправильно поняли начальные путанные условия задачи, посмотрите плиз мой пост, где я ошибся, если не трудно

[Pavia]

Sicker

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

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

Без переключение это переход состояния в себя такие автоматы эквиваленты поэтому 3 не возникает.
$q1\rightarrow q1$
$q2\rightarrow q2$
А вот если автомат не выдаёт данные в некотором состояние. То тогда в выходной алфавит можно добавить $\varepsilon$

[arseniiv]

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

Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик.

Это не машина Тьюринга, это конечный автомат (ой, уже написали). Боже, когда вы уже познаете пользу аккуратности и предварительных приготовлений…

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

Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Или точнее, его функцию отклика (ведь есть состояния, которые функционально изоморфны).

Например, для байесовских сетей и подобных моделей есть алгоритмы вывода состояния неизвестных переменных. В самом плохом случае здесь могло бы подойти аналогичное.

Кроме того, можно моделировать сразу все возможные автоматы, отсекая несоответствующие парам (вход, выход) данного, генерируя входные символы в случае неоднозначности случайно. Когда в пуле останется мало автоматов, всё чаще будут встречаться ситуации, когда поведение всех автоматов по одному из входных символов уже известно, и потому можно будет выбрать детерминированно другой. Это не обязательно оптимальный алгоритм, но лёгкий в реализации и для вашего количества (255) должен быстро давать ответ, особенно если подбирать вероятность выбора очередного входного символа при неоднозначности аккуратно (а не просто 0,5).

[Sicker]

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

Произвольно задав значения 0 или 1 для всех выходных значений $x_{ij}$ и состояний $y_{ij}$ получим некоторую "машину Тьюринга". Очевидно, что таких вариантов $2^8=256$.
Это при условии, что снято требование об обязательном переходе между состояниями.

Полностью согласен

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

В этом вы правы, получается больше чем 16. А именно $9*16=144$, если опять не вру. Похоже, мне тоже пора идти читать матчасть.

У меня тоже самое)

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

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

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

Признаю что в предыдущем посте ошибся. Подставляем условия в формулу получаем (2*2)^(2*2)=256

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

Никаких троек.* - тут можно подискутировать но это лучше вынести в отдельная тему.

Мы выше уже разобрались

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

Что касается основного вопроса следует изучить цепи Маркова. Только на практике их почти не применяют. Предпочитают использовать нейронные сети которые с некоторой погрешностью аппроксимируют неизвестную функцию.

Мне тоже первое что пришло в голову это использовать нейронные сети.

arseniiv в сообщении #1303204 писал(а):

Например, для байесовских сетей
и подобных моделей есть алгоритмы вывода состояния неизвестных переменных. В самом плохом случае здесь могло бы подойти аналогичное.

Спасибо, почитаю)

arseniiv в сообщении #1303204 писал(а):

Кроме того, можно моделировать сразу все возможные автоматы, отсекая несоответствующие парам (вход, выход) данного, генерируя входные символы в случае неоднозначности случайно. Когда в пуле останется мало автоматов, всё чаще будут встречаться ситуации, когда поведение всех автоматов по одному из входных символов уже известно, и потому можно будет выбрать детерминированно другой. Это не обязательно оптимальный алгоритм, но лёгкий в реализации и для вашего количества (255) должен быстро давать ответ, особенно если подбирать вероятность выбора очередного входного символа при неоднозначности аккуратно (а не просто 0,5).

Это по сути, то что я в начале предложил.

[Dan B-Yallay]

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

У меня тоже самое)

Не уверен, что то же самое:

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

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

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

3*3*4*4*2

$$ 144 \ne 72 \ne 3*3*4*4*2 $$

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

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

$144 = 12*12$

[arseniiv]

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

Это по сути, то что я в начале предложил.

Но вы не указали, когда этому алгоритму рано, а когда пора заканчивать. Впрочем, я тоже. И ещё у меня там опечатка — разумеется, 256, а не 255.

А вот сможете ли вы найти для произвольных $n,i,o$ количество классов эквивалентности автоматов с $n$ состояниями (одно из которых маркировано — стартовое), $i$ входными символами и $o$ выходными?