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