Теория автоматов

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Теория автоматов

Сообщение Albus » 15 фев 2022, 20:32

Собственно, как то давно придумал такую задачу
Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое (т.е. для любого состояния найдется сигнал, который это состояние сменит) Как по отклику на входной сигнал определить устройство черного ящика?
P.S. Нам нужно найти все такие алгоритмы для нашего ящика, согласно которым по произвольной входной строке x1x2... мы получали бы точно такую же строку, что и наш исходный черный ящик y1y2..., т.е. имеем функциональную эквивалентность. На языке внутреннего устройства - если подалгоритмы для обоих состояний (1 и 2) одинаковы, то нам не важна динамика переходов между внутренними состояниями.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Теория автоматов

Сообщение Ian » 16 фев 2022, 14:20

По моему небольшому опыту в таких задачах, всегда работает "информационный подход", хотя он не всегда самый короткий.
Сколько существует таких автоматов? Отклики состояния s1 может быть реализована 4-мя способами, s2 -4мя, переходы из s1 (в силу ограничения) 3мя: переход по 0, переход по 1, переход по обоим; и тп. Итого не более 4*4*3*3=144 автоматов, причем с известным упорядочением состояний. То есть если мы определим какой из них сидит в черном ящике, то одно из двух: либо мы знаем, в каком начальном состоянии он находился, либо мы знаем что в обоих состояниях он работает идентично. Далее , чтобы получить эту информацию, выбираем первый ход (0 или 1) как тот , отклики на который (0 или 1) рассекают множество возможных автоматов возможно ровнее, в данном случае первый ход 0 или 1 одинаково оптимален и останется набор из не более чем 72 возможных автоматов, второй ход выбираем по тому же принципу. Можно доказать, что действия по этому подходу всегда приводят к решению задачи, если она разрешима, но оценка сверху числа ходов получается большой. (Оптимальность на очередном ходе не означает оптимальности во всей игре). Ну а оценка снизу видимо не менее [math] ходов


Вернуться в «Математика»

Кто сейчас на форуме

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