Распределенная машина Тьюринга?

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

Одна идея состоит в том, чтобы сделать общую ленту (что-то похожее на Tuple Space ) между TM.

Есть ли формальное представление распределенной системы поверх машины Тьюринга?

В связи с этим обсуждение (см. Ссылку, размещенную Юккой в ​​комментариях) - это способ выглядеть. На мой взгляд, то, как вы будете формально представлять распределенную систему, во многом зависит от того, как вы их просматриваете, и это зависит от «ваших любимых системных предположений» (т. Е. Предположений о синхронности (т. Е. Относительной синхронизации действий в распределенной системе). система), при общении (передача сообщений или совместная память), при сбоях (процессов и / или связей, доброкачественных или византийских и т. д.). Поскольку сообщество не согласно по этому вопросу, также отсутствует согласие в отношении основного формализма ,

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

Я предполагаю, что это вполне возможно, но никто (о котором я знаю) не рассматривал это. Что я знаю о них:

1. Timed IO Automata также используется в книге Lynch's Distributed Computing
2. Связь последовательных процессов
3. Временная логика действий
4. Пи-исчисление (также уже упоминалось Алексом)
5. И еще (были и будут упомянуты здесь) ...

Возможно, вы захотите заглянуть в Пи-исчисление.

http://en.wikipedia.org/wiki/%CE%A0-calculus

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

Я удивлен, что сети Петри еще не упоминались! Расширения сетей Петри, таких как цветные сети Петри или сети Петри с дугами-ингибиторами , завершаются по Тьюрингу.

( Предупреждение: несколько предвзятые взгляды, упрощения и вопиющие обобщения впереди. )

Часто разницу между распределенными вычислениями и параллельными вычислениями можно суммировать следующим образом:

• В распределенных вычислениях основные меры сложности связаны с коммуникацией и информационными потоками : сколько раундов связи («время»); сколько бит передано.
• В параллельных вычислениях основные меры сложности связаны с вычислениями и обработкой информации : сколько элементарных шагов («время»); сколько бит хранится

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

$O(n)$

$X$$X$

$T$$T$

Следовательно, использование машин Тьюринга в качестве отправной точки для моделирования распределенных систем звучит для меня немного неестественно: если это не имеет значения, зачем строить все на нем? С другой стороны, при параллельных вычислениях это было бы естественно (за исключением того, что модель обычно напоминает PRAM вместо машин Тьюринга).

Некоторые утверждают, что в зависимости от вашего взгляда вы могли бы думать о распределенных системах как о чем-то более мощном, чем машина Тьюринга, из-за различных интерпретаций ограниченности недетерминизма и справедливости. По этой ссылке есть интересное обсуждение по теме. Херлихи / Шавит в своей книге «Искусство многопроцессорного программирования» утверждают, что вычислимость по Тьюрингу по своей сути относится к понятию (последовательного) алгоритма и в некотором смысле не подходит для рассуждений о распределенных вычислениях. Следует отметить , что это спорный и неоднозначный , поэтому я надеюсь , что никто не бросает меня камни , потому что я это говорю.