Эквивалентны ли централизованное и децентрализованное упр-ие

[_hum_]

Раздела кибернетика не нашел, поэтому постчу здесь.

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

И, может, кто литературу на эту тему подскажет?

[AlexDem]

Мне кажется, в классическом случае это следует из эквивалентности клеточных автоматов и машины Тьюринга:

Цитата:

было доказано, что в «Жизни» существует универсальный конструктор (машина Тьюринга), а в 2002 году универсальный конструктор был построен.

[Circiter]

2_hum_

Цитата:

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

Мне кажется, что ряд моментов сводится к вопросам надежности доставки сигналов в децентрализованной среде. Если сообщения могут перехватываться или портиться, то как известно (cf. парадокс двух генералов), это приводит к проблемам синхронизации работы отдельных частей такой сети. Также, в достаточно большой децентрализованной сети, за счет процессов самоорганизации, централизованность может появиться сама -- некоторые узлы могут координировать работу других.

С другой стороны, абсолютная надежная рассылка ваших предписаний, очевидно, эквивалентна централизованному управлению.

2AlexDem

Цитата:

Мне кажется, в классическом случае это следует из эквивалентности клеточных автоматов и машины Тьюринга

Но не всякий набор правил приводит к такой вычислительной универсальности.

[_hum_]

2AlexDem
Спасибо. Кое-чего для себя почерпнул. Правда, так и не нашел, что имелось в виду под существованием универсального конструктора. А хотелось бы, если говорить в рамках теории клеточных автоматов, узнать следующее:
пусть $F$ клеточное поле размером $m\times n$, в клетки которого помещены одинаковые конечные автоматы с состояниями из некоторого конечного множества $S$, воспринимающие текущие состояния своих ближайших соседей в качестве внешнего сигнала.
Вопрос:
для всяких ли функций $G: S^{m\times n}\times \mathbb{N} \rightarrow S^{m\times n}$ (здесь $S^{m\times n}$ - множество матриц с элементами из $S$) существует такая конструкция конечного клеточного автомата, что для всякого набора начальных состояний $||s^0_{i,j}|| \in S^{m\times n}$ этих конечных автоматов последовательность состояний $||s^t_{i,j}||, t = 1,2,...,$ проходимых автоматами во времени будут в точности соответствовать значениям $G\big(||s^0_{i,j}||, t\big), t = 1,2,...$.

Поле $F$ содержательно можно рассматривать как набор фиксированных мест в окрестностях перекрестка. Конечные автоматы - водители, которые могут обозревать только своих ближайших соседей. Их состояния "двигается", "стоит", "намеревается совершить маневр такой-то", "находится в конфликтной точке" и проч., проч. Вопрос, можно ли подобрать таким образом правила дорожного движения, чтобы обходясь без светофоров реализовать, например, поведение: если по главной дороге поток большой и со второстепенной выезд затруднен, то на главной дороге все останавливаются на некоторое время и пропускают некоторое количество машин со второстепенного направления.

В общем-то, вопрос вырос вот откуда: до появления светофоров порядок проезда определялся по общему правилу "помехи справа" (ну с доп. условием пропуска пешехода и рельсового транспорта). Вопрос: есть ли какая-то сущностная (неизбежная) необходимость появления светофоров, и если да, то в чем ее суть. В первую очередь бросается в глаза, что светофоры реализуют центральное управление (подача общей для всех информации). Значит, возможно, что именно тут "собака зарыта". Может быть, не всякое поведение можно организовать через (одни и те же для всех) предписания поведения в локальной ситуации (наподобие правила "помехи справа")?

[AlexDem]

_hum_ в сообщении #530506 писал(а):

Вопрос:
для всяких ли функций $G: S^{m\times n}\times \mathbb{N} \rightarrow S^{m\times n}$ (здесь $S^{m\times n}$ - множество матриц с элементами из $S$) существует такая конструкция конечного клеточного автомата, что для всякого набора начальных состояний $||s^0_{i,j}|| \in S^{m\times n}$ этих конечных автоматов последовательность состояний $||s^t_{i,j}||, t = 1,2,...,$ проходимых автоматами во времени будут в точности соответствовать значениям $G\big(||s^0_{i,j}||, t\big), t = 1,2,...$.

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

_hum_ в сообщении #530506 писал(а):

Правда, так и не нашел, что имелось в виду под существованием универсального конструктора

Я тоже не разбирался в деталях, но если клеточный автомат позволяет моделировать машину Тьюринга, то очевидно, что любой алгоритм для МТ можно переложить для КА, в том числе и тот, что осуществляет управление.

Circiter в сообщении #530451 писал(а):

Но не всякий набор правил приводит к такой вычислительной универсальности.

Это само собой...

[_hum_]

AlexDem в сообщении #530980 писал(а):

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

Согласен. Нужно какие-то ограничения ставить (учитывающие однородность поля; или избавляться от нее).

AlexDem в сообщении #530980 писал(а):

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

Я что-то пропустил? Где говорилось, что он может моделировать машину Тьюринга? И под МТ понималась универсальная МТ или какая-то частная? Если последнее, то

AlexDem в сообщении #530980 писал(а):

то очевидно, что любой алгоритм для МТ можно переложить для КА, в том числе и тот, что осуществляет управление.

неверно. Класс МТ, моделируемых КА, может быть более узким, чем множество всех МТ.

[AlexDem]

см.: Гарднер М. Крестики - нолики. - М.: Мир, 1988. C. 338:

Цитата:

В февральском номере Scientific American за 1971 г. я поднял вопрос о том, позволяют ли правила игры "Жизнь" построить универсальную вычислительную машину, а уже в следующем номере сообщил читателям, что игра "Жизнь" в самом деле является универсальной. Дело в том, что независимо друг от друга Госпер в Массачусетсом технологическом институте и Конуэй в Кембридже "универсализировали" пространство игры "Жизнь", подтвердив возможность использования "глайдеров" в качестве носителей информации с целью моделирования машины Тьюринга.

[Alik]

Насколько я понимаю, теме топика посвящена книжка В.И. Варшавский, Д.А. Поспелов "Оркестр играет без дирижера"

[_hum_]

AlexDem, спасибо, гляну.

Alik, спасибо, по-видимому, то, что нужно; бум читать (правда, год смущает - 1984 :) ).